# Privacy-Preserving Authentication Based on PUF for VANETs
## 6 Performance Evaluation
### Computational Overhead Comparison  
To facilitate the comparison of computational overhead, this experiment was conducted on a laptop equipped with an Intel i5-8300H processor (2.3 GHz) and 16 GB of memory. By repeatedly executing operations with different input values and taking the average, we obtained the execution times of common cryptographic operations. Specifically, we represented the time for hash function operations as \(T_{h}\), the execution time for scalar multiplication on elliptic curve cryptography (ECC) as \(T_{m}\), and the execution times for encryption and decryption algorithms of AES uniformly as \(T_{a}\) (although typically the decryption function of AES takes longer than the encryption function, the difference in execution time between the encryption and decryption algorithms is negligible for small data volumes). Furthermore, the PUF deployed on vehicles and RSUs adopted the ring oscillator algorithm. The time required to apply a 128-bit challenge to the PUF and generate the corresponding 128-bit response was recorded as 9 microseconds (\(\mu\)s) [23], we represented the execution times for PUF as \(T_{p}\), the execution times for the function \(Rep(W^{\prime},P_{F})\) of FE as \(T_{gen}\), and the execution times for the function \(Gen(W)\) of FE as \(T_{rep}\). The times required for these operations are detailed in Table 2, which serves as the basis for subsequent computational overhead. Notably, the execution times for concatenation operations \((||)\) and XOR operations \((\oplus)\) are negligible compared to the times listed in Table 2, so we do not consider the computational time for these two operations.  
Moreover, in the authentication phase of the proposed scheme, there are 6 hash operations, an AES encryption operation, 2 AES decryption operations, 2 function \(Rep(W^{\prime},P_{F})\) operations of the fuzzy extractor, and 2 generating a 128-bit response of PUF operations that need to be performed. Furthermore, we compare the verification time of the proposed scheme with schemes in [19; 20; 21; 22]. The results in Table 3 and Figure 6 show that our proposed scheme computation overhead is better than others.  
\begin{table}
\begin{tabular}{c l c} \hline \hline
**Notation** & **Operation** & **Time (ms)** \\ \hline \(T_{h}\) & Hash function & 0.001 \\ \(T_{m}\) & Scale multiplication of ECC & 0.383 \\ \(T_{a}\) & AES encryption and decryption & 0.011 \\ \(T_{p}\) & The 128-bit PUF operation & 0.009 \\ \(T_{gen}\) & Function \(Gen(W)\) of the fuzzy extractor with a 128-bit input & 0.023 \\ \(T_{rep}\) & Function \(Rep(W^{\prime},P_{F})\) of the fuzzy extractor with a 128-bit input & 0.010 \\ \hline \hline \end{tabular}
\end{table}
Table 2: The execution time of the basic operations.  
\begin{table}
\begin{tabular}{c l l} \hline \hline
**Scheme** & **Communicate with a RSU** & **Communicate with n RSUs** \\ \hline
[19] & \(4T_{m}+T_{p}+10T_{h}\) & \(n(4T_{m}+T_{p}+10T_{h})\) \\
[20] & \(8T_{a}+2T_{p}+14T_{h}\) & \(n(4T_{a}+2T_{p}+10T_{h})+4(T_{a}+T_{h})\) \\
[21] & \(3T_{m}+2T_{h}\) & \(n(T_{m}+2T_{h})+2T_{m}\) \\
[22] & \(5T_{m}+2T_{h}\) & \(n(5T_{m}+2T_{h})\) \\ Ours & \(3T_{a}+2T_{p}+2T_{rep}+6T_{h}\) & \(n(3T_{a}+2T_{p}+2T_{rep}+6T_{h})\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: The computation overhead in the authentication phase.