## 3 Proposed Scheme: RSP-Based Message Authentication for VANET  
In the proposed scheme, one day is split into n time slots (\(T_{1}\)\(\sim\)\(T_{n}\)), and the \(TA\) maintains a large secret pool that will be pre-distributed randomly to all RSUs and vehicles as information about the original registration set (ORG) at \(T_{0}\). With a pseudo random generator and the same seed value that is provided by the \(TA\) in \(T_{1}\)\(\sim\)\(T_{n}\), all RSUs have the same secret pool from which to issue the random secret in response to registration requests from vehicles. Every day, in \(T_{1}\) or the first time slot (\(T_{t}\)), a vehicle enters the coverage of an RSU, and requests the new registration set (NRG) using the information in its ORG. In another time slot, the vehicle can request the new registration set using the information in its NRG; set this NRG as its previous registration set (PRG), and set the new registration as its new NRG. Accordingly, the ORG, PRG and NRG that are maintained by a vehicle are requested at \(T_{0}\), \(T_{t-1}\)_and_\(T_{t}\), respectively. The information of the registration set includes issuer, time slot, set of identities, set of secret indices and set of private keys. The public key can be derived from the identity and the time slot, and in the public keys are embedded the indexed secret value to form the private keys. At any time, a vehicle can choose randomly one of its identities in ORG, PRG or NRG as its identity and announce this anonymous identity to all neighbors. An anonymous identity has the form (issuer, time slot, identity, set of secret indexes). Based on the information in a vehicle's anonymous identity, neighboring vehicles can find the common secret, calculate the pairing value, or find a neighbor that can help with message authentication or confidential communication. This section will describe this process in detail. Table 1 presents the associated notation and definitions. \begin{table}
\begin{tabular}{c l} \hline \(Z_{a}\) & \(Z_{a}\) is a finite field that is formed by mod \(q\), where \(q\) is a large prime number. \\ \hline \(G\),\(P\), \(P^{x}\) & \(G\) is an \(EC\) addition group with mod q; \\  & \(P\) is the generator of \(G\). \(P^{x}\) is the value on the \(x\) axis. \\ \hline \(M\) & \(M\) is a character stream or bit stream. \\ \hline \(H(M)\) & \(H(M)\) is a hash function that maps \(M\) to \(Z_{a}\). \\ \hline \(HMAC(M)_{k}\) & \(HMAC(M)_{k}\) is a hash function that maps \(M\) to \(Z_{q}\) with key \(K\). \\ \hline  & \(\hat{\mathfrak{e}}\) (\(Q\),\(R\)) is a bilinear pairing function that pairs \(Q\) and \(R\) in \(G\) with a value in \(Z_{q}\). \\ \(\hat{\mathfrak{e}}\) (\(Q\),\(R\)) & \(\hat{\mathfrak{e}}\) (\(Q\),\(R\)) satisfies the functions of pairing. \\  & \(\hat{\mathfrak{e}}\) (\(Q\),\(R\)) = \(\hat{\mathfrak{e}}\) (\(R\),\(Q\)), \\  & \(\hat{\mathfrak{e}}\) (\(Q\),\(R\)) = \(\hat{\mathfrak{e}}\) (\(Q\),\(R\)) = \(\hat{\mathfrak{e}}\) (\(Q\),\(R\))\({}^{ab}\) \\ \hline \(ID_{TA}\), \(ID_{Ra}\) & \(ID_{TA}\) and \(ID_{Ra}\) are the IDs of the TA and RSUa. \\ \hline  & \(SP_{TA}\) is the secret pool of the TA that is generated by a pseudo random generator with seed \(S_{do}\), \(SP_{TA}\) has \\ \(SP_{TA}\) & \(RT_{TA}\) secrets. \\ \(SP_{TA}\) & \(\{SP_{TA}=\{SP_{TA}\) (\(d_{i}\)) \(\}SP_{TA}\) (\(d_{i}\)) \(\in PRNG(S_{do})\), \(\mathrm{d_{i}=1\
eg}R_{TA}\}\) \\  & \(SP_{TA}\) (\(\mathrm{d_{i}\)) is the \(d_{\mathrm{th}}\) secret in \(SP_{TA}\) \\ \hline  & \(SP_{Rt}\) is the secret pool of RSUs, which is generated by \(PRNG(S_{dt})\), where \(S_{dt}\) is sent by TA at \(T_{t}\). All \\  & RSUs have the same \(SP_{Rt}\) at \(T_{t}\); \\  & \(R_{R}\) is the size of \(SP_{Rt}\) \\  & and \(SP_{Rt}\) = \(\{SP_{Rt}\) (\(d_{i}\)) \(\}SP_{Rt}\) (\(d_{i}\)) \(\in PRNG(S_{dt})\), \(d_{i}=1\
eg R_{R}\}\) \\ \hline  & \(DS_{Ra}\) and \(DS_{V_{t}}\) are the set of secret indexes of Ra and \(V_{t}\).