## 3 Proposed Scheme: RSP-Based Message Authentication for VANET
### Constructing Set of Neighbors  
At any time in \(T_{t}\), the time slots in the \(PRG\) and the \(NRG\) in a vehicle may be (\(T_{t-1}\), \(T_{t}\)) or (\(T_{t-2}\), \(T_{t-1}\)). To construct the set of neighbors, every vehicle will say \"hello\" to all neighbors to announce its presence, and will periodically disclose its anonymous identity. Every vehicle must maintain a set of neighbors, which includes information about the neighbors and the expiration time. When \(V_{i}\) receives a hello message from \(V_{j}\), \(V_{i}\) will determine whether \(V_{j}\) is in the set of neighbors; if it is, then \(V_{i}\) presets the expiration time of \(V_{j}\). If \(V_{j}\) is a new vehicle, then \(V_{i}\) will set the \(V_{j}{}^{\prime}s\) information in the neighbor set and preset the expiration time. The expiration time will be counted on continuously. When the expiration time of \(V_{j}\) is reached, the information of \(V_{j}\) will be removed.  
\begin{table}
\begin{tabular}{c c c} \hline \hline
**Anonymous Identity** & **New Registration Set** & **Revoked?** \\ \hline \(\{ID_{\text{TA}},\,T_{0},\,ID_{V_{i}},\,DS_{V_{i}}\}\) & \(\{ID_{Ra},\,T_{t},\,IDS_{V_{i}}\,^{\prime},\,DS_{V_{i}}\,^{\prime},\,PRS_{V_{i} }\,^{\prime}\}\) & No \\ \(\vdots\) & & No \\ \(\{ID_{\text{Rx}},\,T_{t-1},\,ID_{V_{i}},\,DS_{V_{i}}\}\) & \(\{ID_{Ra},\,T_{t},\,IDS_{V_{i}}\,^{\prime},\,DS_{V_{i}}\,^{\prime},\,PRS_{V_{i} }\,^{\prime}\}\) & No \\ \(\vdots\) & & No \\ \hline \hline \end{tabular}
\end{table}
Table 3: Recorded information about the anonymous identity and the new registration set (\(NRG_{V1}\)) in \(\text{RSU}_{\text{A}}\).  
Hello message  
\[V_{i}\rightarrow\text{all: ``Hello'', }(ID_{Ra},T_{t},ID_{Vi},\,DS_{Vi})\text{, where }ID_{Vi}\in_{R}IDS_{Vi}\]  
Construction of Set of Neighbors  
\(V_{i}\) collects hello messages of all neighbors, and then builds the set of neighbors as follows.  
\(V_{i}\) has the information of \(V_{j}\), \((ID_{Rb},\,T_{t},\,ID_{Vj}\), \(DS_{Vi})\), and \(V_{j}\) has the information of \(V_{i}\), \((ID_{Ra},\,T_{t},\,ID_{Vi},\,DS_{Vi})\). \(V_{i}\) generates the pairing value \(P_{Vi,Vj}\) with \(V_{j}\), and \(V_{j}\) generates the pairing value \(P_{Vj,Vi}\) with \(V_{i}\), consistent with Equations (1) and (2).  
\[P_{Vi,Vj}=\hat{\Theta}\;(\frac{H(ID_{Ra}\,\,ID_{Vi}\,\,\|T_{t})}{H(ID_{Ra}\,\, \|ID_{Vi}\,\,\|T_{t})}\;PR_{Vix},\,PK_{Vj})=\hat{\Theta}\;(PK_{Vi}\,,\,PK_{Vj} )^{dvix} \tag{1}\]  
\[P_{Vi,Vi}=\hat{\Theta}\;(\frac{H(ID_{Rb}\,\,\|ID_{Vi}\,\,\|T_{t})}{H(ID_{Rb}\, \,\|ID_{Vi}\,\,\|T_{t})}\;PR_{Viy},\,PK_{Vi})=\hat{\[PERSON]}\;(PK_{Vj}\,,\,PK_{Vi })^{dviy} \tag{2}\]  
If any \(d_{Vix}\) in \(DS_{Vi}\) equals \(d_{Vjy}\) in \(DS_{Vi}\), then \(P_{Vi,Vj}\) will equal \(P_{Vj,Vi}\). \(P_{Vi,Vj}\) is the pairing value of \(V_{i}\) and \(V_{j}\) that is used for mutual authentication. If no \(d_{Vix}=d_{Vjy}\), then \(V_{i}\) checks for another vehicle in the set of neighbors (\(V_{t}\)) whose \(DS_{V_{t}}\) has a common index with \(DS_{Vj}\) and \(DS_{Vi}\), and then puts \"\(ID_{Vi}\)\" in the pairing value field, enabling \(V_{t}\) to help \(V_{i}\) to authenticate with \(V_{j}\). The information of \(V_{k}\) is taken at \(T_{t-1}\), and \(V_{i}\) will use \(PRG_{Vi}\) to make a pairing with \(V_{k}\) in a pairing process that is similar to the process described above. In Table 4, \(V_{i}\) has a common secret with \(V_{j}\) and \(V_{k}\), and \(V_{j}\) can help \(V_{i}\) and \(V_{t}\) to perform authentication.