# Privacy-Preserving Authentication Based on PUF for VANETs
## 3 Preliminaries
### Route Planning
\begin{array}{l}SKM_{v}=\begin{pmatrix}sk_{1}^{1}&sk_{1}^{2}&sk_{1}^{3}&sk_{ 1}^{4}&sk_{1}^{5}&sk_{1}^{6}\\ sk_{2}^{1}&sk_{2}^{2}&sk_{2}^{3}&sk_{2}^{4}&sk_{2}^{5}&sk_{2}^{6}\\ sk_{3}^{1}&sk_{3}^{2}&sk_{3}^{3}&sk_{3}^{3}&sk_{3}^{3}&sk_{3}^{5}&sk_{3}^{5}\\ sk_{4}^{1}&sk_{4}^{2}&sk_{4}^{3}&sk_{4}^{4}&sk_{4}^{5}&sk_{4}^{6}\\ \end{pmatrix}\end{array}  \tag{1}\]  
* CA uses the elements of the matrix \(SKM_{v}\) to encrypt the authentication keys of all \(n\) RSUs by calculating \(EMM_{v}=\{c_{a}^{i}=\text{Eyn}(sk_{a}^{i},\,K_{u}^{i})\}_{a\in\{1,2,\ldots,k\},i\in\{1,2,\ldots,n\}}\). The results for each element in \(EMM_{v}\) are shown in Equation (2); \[ \begin{array}{l}EMM_{v}=\begin{pmatrix}Eyn(sk_{1}^{1},K_{u}^{1})&Eyn(sk_{2}^ {2},K_{v}^{2})&Eyn(sk_{3}^{3},K_{u}^{3})&Eyn(sk_{4}^{4},K_{u}^{4})&Eyn(sk_{4}^{5 },K_{u}^{5})&Eyn(sk_{1}^{6},K_{u}^{6})\\ Eyn(sk_{2}^{2},K_{u}^{1})&Eyn(sk_{2}^{2},K_{u}^{2})&Eyn(sk_{2}^{3},K_{u}^{3})&Eyn (sk_{2}^{2},K_{u}^{4})&Eyn(sk_{2}^{2},K_{u}^{4})\\ Eyn(sk_{3}^{3},K_{u}^{1})&Eyn(sk_{3}^{3},K_{u}^{2})&Eyn(sk_{3}^{3},K_{u}^{3})&Eyn (sk_{3}^{2},K_{u}^{4})&Eyn(sk_{3}^{2},K_{u}^{4})&Eyn(sk_{3}^{2},K_{u}^{4})\\ Eyn(sk_{4}^{4},K_{u}^{1})&Eyn(sk_{4}^{4},K_{u}^{2})&Eyn(sk_{4}^{4},K_{u}^{4})&Eyn (sk_{4}^{4},K_{u}^{4})&Eyn(sk_{4}^{4},K_{u}^{4})&Eyn(sk_{4}^{4},K_{u}^{4})\\ \end{array} \end{array}\] (2)
* CA generates a timestamp \(t_{2}\) and a temporary session key \(K_{v}\) with the vehicle, where \(K_{v}=H(R_{Fv}||t_{2})\), \(\phi_{2}=H(E_{K_{v}}(EMM_{v})||H(R_{Fv})||t_{2}||AID_{v})\). Next, CA sends \(M_{2}:\{E_{K_{v}}(EMM_{v}),t_{2},AID_{v},\phi_{2}\}\) to the vehicle;
* On receiving \(M_{2}\), the vehicle verifies \(t_{2}\). If it is correct, the vehicle then verifies \(\phi_{2}\) by checking whether the equation \(\phi_{2}=H(E_{K_{v}}(EMM_{v})||H(Rep(PUF(C_{v}),P_{Fv}))||t_{2}||AID_{v})\) holds. If the checking process passes, the vehicle accepts \(M_{2}\). In the end, the vehicle gets \(E_{K_{v}}(EMM_{v})\);
* The vehicle calculates \(K_{v}=H(Rep(PUF(C_{v}),P_{Fv})||t_{2})\) and uses \(K_{v}\) to decrypt \(E_{K_{v}}(EMM_{v})\) in order to retrieve \(EMM_{v}\), and then retrieve the needed authentication keys by calculating \(\{Dec(sk_{a},Eyn(sk_{a}^{n_{a}},K_{u}^{n_{a}}))\}_{a=1}^{k}\). In the above example, in order to obtain \(k\) desired RSUs, only 4 decryption operations need to be performed, i.e., \(K_{u}^{3}=Dec(sk_{1},Eyn(sk_{1}^{3},K_{u}^{3}))\), \(K_{u}^{2}=Dec(sk_{2},Eyn(sk_{2}^{2},K_{u}^{2}))\), \(K_{u}^{6}=Dec(sk_{3},Eyn(sk_{3}^{6},K_{u}^{6}))\), \(K_{u}^{1}=Dec(sk_{4},Eyn(sk_{4}^{1},K_{u}^{1}))\);
* In the event of physical attacks, such as side-channel attacks, the long-stored authentication keys \(\{K_{u}^{i}\}_{a=1}^{k}\) may be compromised. To prevent this, we employ a \(K_{v}\) to individually encrypt each authentication key, namely, \(\{E_{K_{v}}(K_{u}^{i})\}_{a=1}^{k}\). In the aforementioned process of this section, the vehicle simultaneously requests authentication keys from all the RSUs it encounters. To avoid path leakage, it employs OT. As a result, the entire process becomes relatively complicated. Now, we will analyze the time complexity. In the above process, the primary time consumption stems from the computation of \(SKM_{v}\)and \(EMM_{v}\). Assuming there are \(n\) RSUs under the CA domain and the vehicle requires obtaining \(k\) RSUs prior to a specific trip, then \(SKM_{v}\) comprises \(n*k\) elements. When calculating each element in \(SKM_{v}\), Only two scalar multiplication operations on ECC, one addition operation on ECC and one hash operation are necessary. Consequently, the time complexity of computing \(SKM_{v}\) is approximately \(\mathcal{O}(n*k)\), and the same time complexity applies to calculating \(EMM_{v}\), which is also about \(\mathcal{O}(n*k)\). All other operations within this section exhibit either constant or linear time complexity with respect to \(k\). Therefore, the total time complexity of this section is dominated by the \(\mathcal{O}(n*k)\).