## 4 Security Analysis
### Anonymity and Message-Vehicle Untracability  
Let \(\mathcal{A}^{t}\) be a PPT tracing adversary, whose goal is to trace the identity \(ID\) related with one or more messages send to one or more RSUs. We allow the adversary to collude with authorities in various scenarios. We denote as \(\mathtt{Corrupted}\) the set of authorities colluding with adversary in each scenario. Let \(\Pi_{3}\) be the communication protocol. We formalize the notion of message-vehicle untraceability by an experiment \(\mathit{Priv}_{\mathcal{A}^{t},\Pi_{3}}(n)\) in which \(\mathcal{A}^{t}\) has access to an Oracle \(\mathcal{O}_{\Pi_{3}}\) that on input a security parameter \(n\) (which defines the billinear group setting along with an AoN-PKET) simulates executions of \(\Pi_{3}\). \(\mathcal{A}^{t}\) has access to all public keys used for encrypting, to a history of simulated executions of \(\Pi_{3}\) that includes the transmitted messages. In addition \(\mathcal{A}^{t}\) has access to all secret keying material of all entities that belong to the set \(\mathtt{Corrupted}\) of all colluding entities. \(\mathcal{A}^{t}\) attempts to relate any of the posted messages \(m\) with the encryption of the identifier \(ID\), \(AEnc(h,r,ID)\). We say that \(\mathcal{A}^{t}\) succeeds if it relates any message with the corresponding encrypted identifier \(AEnc(h,r,ID)\). If \(\mathcal{A}^{t}\) succeeds then \(\mathit{Priv}_{\mathcal{A}^{t},\Pi_{3}}(n)\) outputs \(1\) and zero otherwise. Suppose there is some statistical noise and \(k\) messages are sent for signatures every second. The signature of these messages remain valid for a time frame say \(t_{f}\). Then \(P_{b}(m,ID)\) is the probability to successfully bind message \(m\) submitted on a specific time \(t\) with the correct encrypted identifier \(AEnc(h,r,ID)\). The message \(m\) remains valid until \(t+t_{f}\). Assuming that all messages signed by the SA are forwarded from the vehicles to RSUs at a random time within the valid time frame, then \(P_{b}(m,ID)\leq\frac{1}{k}\). In the worst case scenario only the \(k\) messages submitted on \(t\) are published within the time frame. **Definition 1**. : \(\Pi_{3}\) _provides message-vehicle untraceability if for all PPT adversary \(\mathcal{A}^{t}\) there exists a negligible function negl such that:_  
\[Adv(\mathcal{A}^{t})=|Pr[Prv_{\mathcal{A}-Corrupted,\Pi_{3}}(n)=1]-\tfrac{1}{k}| =negl(n).\]  
**Claim 1**. : \(\Pi_{3}\) provides vehicle anonymity and message-vehicle untraceability, provided that at least one of system entities (\(CA,SA\) or RSU) does not belong to the Corrupted set. Proof. : Recall that the proposed protocol consist of the following exchanges:  
1. The vehicle requests from the CA an anonymous ID. 2. The CA sends to the vehicle the anonymous ID and the relevant proofs to the SA. 3. The vehicle requests a signature from the SA. 4. The SA responds to the vehicle. 5. The vehicle sends the blindly signed message to an RSU. 6. The RSU posts the transmitted message. To win the game, the adversary should be able to relate the identity of the vehicle (\(a\leftrightarrow b\)) with the signature request send by the vehicle to the SA (\(c\leftrightarrow d\)) and finally with the blindly signed message send to an RSU (\(e\leftrightarrow f\)). We will show that the adversary will always fail, provided that at least one of the entities is not corrupted. **Case 1**. : \((a\leftrightarrow b)\) The real identity ID assigned to a vehicle can not be revealed if the \(CA\
otin\) Corrupted and the encryption scheme used in \(\Pi_{1}\) is secure. Proof. : Clearly if the CA is not corrupted the entities belonging to the Corrupted set cannot learn the real identity of the vehicle, since the communication is encrypted using the public key of the CA. **Case 2**. : \((c\leftrightarrow d)\) Messages produced by a vehicle and are authenticated by the SA are untraceable by \(\mathcal{A}^{t}\), provided that the \(SA\
ot\in\)Corrupted. Proof. : Let \(\texttt{Corrupted}=\{CA,RSU\}\).