# Privacy-Preserving Authentication Based on PUF for VANETs
## 3 Preliminaries
### Route Planning  
To improve the V2I authentication efficiency when a vehicle is roaming among different RSUs' coverage, the vehicle plans its route in advance before driving, knowing the RSU set that it will pass by, namely \(\overrightarrow{PA_{v}}=\{RSU_{n_{1}}^{1},RSU_{n_{2}}^{2},\cdots,RSU_{n_{u}}^{ a},\cdots,RSU_{n_{k}}^{k}\}\); here, the superscript of each RSU represents its sequence number in the path, and the subscript represents its sequence number in the CA. Then, the vehicle sends a message to request for these RSUs' authentication key from CA. In order to prevent CA from tracking the vehicle's driving path, OT technology is used here. The interactive implementation process between the vehicle and CA is shown in Figure 4, and the details are as follows. 1. The vehicle generates a timestamp \(t_{1}\), calculates \(Auth_{v}=H(Rep(PUF(C_{v}),P_{Fv}))\) (here, the \(Rep\) function of FE is used to eliminate the noise of PUF), and selects \(k\) random numbers \(\overrightarrow{X_{v}}=\{x_{a}\in Z_{q}^{*}\}_{a=1}^{k}\); it is necessary to note that there is a one-to-one correspondence between the elements of \(\overrightarrow{X_{v}}\) and \(\overrightarrow{PA_{v}}\), respectively. Calculate symmetry session keys \(\overrightarrow{SK_{v}}=\{sk_{a}=H(x_{a}S_{v})\}_{a=1}^{k}\) and relevant transmitted auxiliary parameters \(\overrightarrow{R_{v}}=\{R_{a}=n_{a}S_{v}+x_{a}P\}_{a=1}^{k}\) and send \(M_{1}:\{\phi_{1}=H(Auth_{v}||\overrightarrow{R_{v}}||AID_{v}||t_{1}),\overrightarrow {R_{v}},\)\(AID_{v},t_{1}\}\) to CA via an RSU that has previously been mutually authenticated with the vehicle;
2. On receiving \(M_{1}\), CA verifies \(t_{1}\). If it is valid, CA first detects whether \(AID_{v}\) is in the revocation list \(REV\). If it is in the list, it indicates that the vehicle is a malicious vehicle and rejects the request of the vehicle. Then CA utilizes \(AID_{v}\) to retrieve \(R_{Fv}\), which was generated during the vehicle's registration process, and verifies \(\phi_{1}\) by checking whether the equation \(\phi_{1}=H(H(R_{Fv})||\overrightarrow{R_{v}}||AID_{v}||t_{1})\) holds true. If this equation holds, it signifies that the vehicle is legitimate and that \(M_{1}\) has not been tampered with; otherwise, all subsequent operations are abandoned;
3. If the vehicle is legitimate, CA calculates a \(k*n\) symmetrical keys matrix \(SKM_{v}=\{sk_{a}^{i}=H(y_{v}R_{a}-iT_{v})\}_{a\in\{1,2,\cdots k\},i\in\{1,2, \cdots n\}}\). Here, \(k\) denotes the number of RSUs located along the vehicle's path, and \(n\) denotes the total number of all RSUs within a given CA domain. The \(a\)-th row of the matrix \(SKM_{v}\) contains \(n\) elements. It is important to note that the \(n_{a}\)-th element of \(a\)-th row is specifically equal to the session key \(sk_{a}\) of the vehicle side, and the proof process is as follows. \[ \begin{array}{l}SKM_{v}[a,n_{a}]=sk_{a}^{n_{a}}=H(y_{v}R_{a}-iT_{v})=H(y_{v}(n _{a}S_{v}+x_{a}P)-iT_{v})\\ =H(n_{a}T_{v}+x_{a}S_{v}-iT_{v})=H((n_{a}-i)T_{v}+x_{a}S_{v})=H(x_{a}S_{v})=sk_{ a}\end{array} \]  
From the perspective of CA, it is unaware of the value \(n_{a}\) that corresponds to the \(a\)-th row of the \(SKM_{v}\) matrix. Consequently, it does not know which RSU's authentication key is being correctly transmitted. Assuming that \(n=6\), meaning there are 6 RSUs in the entire CA domain, the vehicle needs to traverse 4 RSUs during a specific trip, that is, \(k=4\). The serial numbers of the RSUs that the vehicle will traverse are \((n_{1}=3\), \(n_{2}=2\), \(n_{3}=6\), \(n_{4}=1)\) in CA. Then, the \(SKM_{v}\) matrix can be derived, as illustrated in Equation (1). The four blue elements \((sk_{1}^{3}\), \(sk_{2}^{2}\), \(sk_{3}^{6}\), \(sk_{4}^{1})\) are equal to the four session keys \((sk_{1}\), \(sk_{2}\), \(sk_{3}\), \(sk_{4})\) at the vehicle end, respectively;  
\[