## 4 Security Analysis
### Unforgeability  
Let \(\Pi_{1},\Pi_{2}\) and \(\Pi_{3}\) be the set up, the registration and the secure communication protocol respectively, as described in Section 3.3. Let \(\mathcal{A}^{f}\) be a PPT forging adversary, i.e., an external adversary who monitors the communications between all honest entities and whose goal is to forge the secure communication protocol \(\Pi_{3}\). In other words, the goal of the adversary is to send a valid looking message to an RSU, without having first issued valid credentials by running \(\Pi_{2}\), with the authorities that have already run \(\Pi_{1}\). We assume that \(\mathcal{A}^{f}\) is having oracle access to \(\Pi_{1},\Pi_{2}\) and \(\Pi_{3}\) but has no access to the randomness used to encrypt or the credentials \(ID\)s of the users. We will construct an algorithm \(\mathcal{B}\) that attacks the DLOG problem by using an adversary \(\mathcal{A}^{f}\) that produces valid \(\mathcal{R}\).  
We will prove that if \(\mathcal{A}^{f}\) can successfully forge \(\Pi_{3}\) with non-negligible probability, then \(\mathcal{B}\) can use \(\mathcal{A}^{f}\) as a subroutine to successfully attack the DLOG problem with non-negligible probability. We assume that \(C_{DLOG}\) is a challenger for the discrete logarithm problem. We denote as \(\mathcal{O}_{\Pi}\) the oracle access of the adversary on a protocol \(\Pi\).  
* **Setup.**\(C_{DLOG}\) provides a challenge \(g,g^{\rho}\) to \(\mathcal{B}\), which forwards the challenge to \(\mathcal{A}^{f}\). Then \(\mathcal{A}^{f}\) uses its oracle access to \(\Pi_{1}\) with input the challenge \(g,g^{\rho}\), to receive the corresponding output of the set up protocol, i.e., \(\mathcal{O}_{\Pi_{1}}:g,g^{\rho}\rightarrow\xi\), \((g,h=g^{\xi})\). Thus, an AON-PKEET is set up with \(\xi\) and \((g,h=g^{\xi})\) the private and public keys respectively.
* \(\mathcal{A}^{f}\) uses its oracle access to \(\Pi_{2}\), to receive the encryptions of valid credentials \(ID_{1},\ldots,ID_{N}\). For the encryption of \(ID_{i}\), \(\mathcal{O}_{\Pi_{2}}\) outputs \((g^{\rho})^{\xi}=(g^{\xi})^{\rho}=l\rho^{\rho}\) end sets \(AEnc(h,r_{i},1)\cdot(g^{\rho},h^{\rho}ID_{i})=(g^{\rho+r_{i}},h^{\rho+r_{i}}ID _{i})=AEnc(h,\rho+r_{i},ID_{i})\) re randomizing encryptions. Thus, \(BB_{SA}\) is formed.
* **Attack.**\(\mathcal{A}^{f}\) requests oracle access to \(\mathcal{O}_{\Pi_{3}}\) for polynomially many executions of \(\Pi_{3}\). Then, the challenge \(AEnc(h,r,ID_{i})=(K_{1},K_{2})\) is given to \(\mathcal{A}^{f}\) for forgery. The adversary chooses a message \(m\) and computes \(\mathcal{C}=H(K_{1},K_{2},m,t_{cur}|rand)\). It outputs a valid NIZKP \(\mathcal{R}\) such that \(g^{\mathcal{R}}K_{1}^{\mathcal{C}}=g^{\rho+r_{i}}\).
* **Guess.**\(\mathcal{B}\) receives from \(\mathcal{A}^{f}\) the values \(\mathcal{R},r,\mathcal{C},r_{i}\) and outputs its guess \(\rho\prime=\mathcal{R}+r\mathcal{C}-r_{i}\). If \(\rho\prime=\rho\) then \(\mathcal{B}\) wins.  
Since, \(\mathcal{R}\in\mathbb{Z}_{p}\) the probability to randomly select a valid \(\mathcal{R}\) equals to \(\frac{1}{p}\). We define the advantage of \(\mathcal{A}^{f}\) to break \(\Pi_{3}\) as: \(ADV_{\mathcal{A}^{f}}=|Prob[\mathcal{R}=valid]-\frac{1}{p}|\). We also define the advantage of \(\mathcal{B}\) to break DLOG as: \(ADV_{\mathcal{B}}=|Prob[\rho t=valid]-\frac{1}{p}|\). Then it holds that:  
\[Prob[\mathcal{R}=valid]=Prob[\mathcal{R}\,|\,g^{\mathcal{R}}K_{1 }^{\mathcal{C}}=g^{\rho+r_{i}}]=\] \[=Prob[\mathcal{R}\,|\,g^{\mathcal{R}}g^{\mathcal{C}}=g^{\rho+r_{ i}}]=\] \[=Prob[\mathcal{R}\,|\,g^{\mathcal{R}+r\mathcal{C}}=g^{\rho+r_{i}}]=\] \[=Prob[\mathcal{R}\,|\,g^{\mathcal{R}+r\mathcal{C}-r_{i}}=g^{\rho}]=\] \[=Prob[\mathcal{R}\,|\,\rho t=\mathcal{R}+r\mathcal{C}-r_{i}=\rho]=\] \[=Prob[\rho t=valid] \tag{1}\]  
Since all values \(r,r_{i},\mathcal{C}\) are known to \(\mathcal{B}\), it holds that if an adversary \(\mathcal{A}^{f}\) can produce valid \(\mathcal{R}\) with non-negligible advantage, then it can be used by \(\mathcal{B}\) as a subroutine to break the DLOG problem also with non-negligible advantage.