## 3 The Proposed Solution
### Detailed Protocol Description
#### 3.3.3 V2I Communication  
Registered vehicles will first authenticate their (partially blinded) messages via the SA and then anonymously send the authenticated messages to RSUs as follows (see Figure 3). Again we assume that all communications are encrypted and integrity protected using the public keys of the SA and/or RSU respectively. Initially \(V\) prepares a fresh encryption of its identifier using a new random value \(r_{i}\) as follows. It chooses \(r_{i}\in_{R}\mathbb{Z}_{p}\) and AoN-Encrypts the credential \(ID\) with \(r_{i}\): \(AEnc(h,r_{i},ID)\rightarrow(K_{1},K_{2})=(g^{r_{i}},IDh^{r_{i}})\). Then \(V\) uses the partially blinded signature scheme [57] to blind the message \(\mathcal{M}=\{m,m^{\prime}\}\), where \(m\) is the actual message to be send blinded. The non-blinded part is predefined as \(m^{\prime}=t_{cur}||rand\), where \(t_{cur}\) is the current time to ensure message freshness and \(rand\) is a randomness that ensures message uniqueness. Then \(V\) blinds \(m\) using randomness \(b\) as: \(\overline{m}=H(m||b)\). In addition, \(V\) computes a Non Interactive Zero Knowledge Proof of knowledge for its identifier \(ID\). This will essentially be a proof that \(V\) knows the randomness \(r_{0}\) used to AoN-Encrypt \(ID\) at the registration phase, by using the randomness \(r_{i}\) chosen for the new AoN-Encryption of \(ID\)[59]. \(V\) computes a challenge for the NIZKP using the fresh AoN Encryption, the blinded message \(\overline{m}\), and the non-blinded message \(m^{\prime}=t_{cur}||rand\), i.e. : \(\mathcal{C}=H(K_{1},K_{2},\overline{m},m^{\prime})\).The response is computed as: \(\mathcal{R}=r_{0}-r_{i}\cdot\mathcal{C}\). Finally, \(V\) forwards \((K_{1},K_{2})\), \((\overline{m},m^{\prime})\) and \(\mathcal{R}\) to the SA. Figure 2: The Registration protocol. The SA will first check the freshness and uniqueness of the non-blinded message \(m^{\prime}=t_{cur}|rand\). Then, it uses the trapdoor \(tk=(\hat{\rho},\hat{\phi}=\hat{\rho}^{\xi})\) to compute \(e(K_{2},\hat{\rho})\cdot e(K_{1},\hat{\phi})^{-1}\rightarrow(X_{1},X_{2})\) and to check if there is a match in the \(BB_{SA}\), i.e., some entry \(D_{j}\in BB_{SA}\) is identical to \((X_{1},X_{2})\). Search is performed in \(\log N\) time where \(N\) is the number of registered vehicles. This assures the SA that \((K_{1},K_{2})\) is a re-encryption of a valid credential. If the AoN-PKEET test fails, abort. Else let \(D_{j}=(C_{1},C_{2})=(g^{\tau_{0}},IDh^{\tau_{0}})\) be the initial encryption of \(ID\) found in \(BB_{SA}\). Now the SA will verify the NIZKP as follows: it computes the challenge \(\mathcal{C}=H(K_{1},K_{2},\overline{m},m^{\prime})\) (in the same way as \(V\) presumably did) and then the checks whether \(g^{\mathcal{R}}{K_{1}}^{C}=C_{1}\), (i.e., \(g^{\tau_{0}-\tau_{i}\cdot\mathcal{C}}\cdot g^{\tau_{i}\mathcal{C}}=g^{\tau_{0}}\)). If the verification fails, it aborts. If the NIZKP verification succeeds then the SA is assured in zero knowledge that \(V\) knows the exponent used in \(C_{1}\) (and therefore a valid \(ID\)). In addition, notice that \(\mathcal{C}\) also binds the fresh AoN-Encrypption of the credential with the blinded message \(\overline{m}\) to be signed. If the verification succeeds, then the SA updates \(\mathcal{B}B_{SA}\) by adding the time of request. The non-blinded part \(m^{\prime}=t_{cur}|rand\) is appended in the appropriate line \(D_{j}=e(C_{2},\hat{\rho})\cdot e(C_{1},\hat{\phi})^{-1}\) containing \((C_{1},C_{2})\). This part of the table is kept private. Multiple requests from the same user can be detected on request. \(\mathcal{B}B_{SA}=\left[ \begin{array}{ccccc}D_{1}&\vdots&\vdots&\vdots& \cdots\\ D_{j}&\vdots&\vdots&\vdots&\cdots\\ D_{j}&\vdots&\vdots&\vdots&\cdots\\ D_{\text{${\mathbb{R}}$}}&\end{array} \right]\) Finally, the SA will sign the blinded message \(\overline{m}\), by selecting \(k\in_{\mathbb{R}}\mathbb{Z}_{p}\) and computing \(l=g^{k}\), \(e=H(l||m^{\prime}||\overline{m})\) and \(s=k-xe\mod q\). The signature \((l,s)\) is send to \(V\).