## 4 Security Analysis
### Message Unlinkability  
As defined in Section 3, message unlinkability requires that an RSU, (or any other authority) should not be able to link together different messages that come from a single sender (vehicle), even if the identity of the sender is not known.  
Let \(\mathcal{A}^{u}\) denote an PPT adversary aiming to break the unlinkability property, who captures the capabilities of honest-but-curious authorities (CA and SA) and RSUs. \(\mathcal{A}^{u}\) monitors all the communications of the SA. Let \(\Pi_{3}\) be the communication protocol. We formalize the notion of unlinkability by an experiment \(\mathit{Priv}_{\mathcal{A}^{u},\Pi_{3}}(n)\) in which \(\mathcal{A}^{u}\) has Oracle access to \(\Pi_{3}\). On input a security parameter \(n\) (which defines the billinear group setting along with an AoN-PKEET) simulates executions of \(\Pi_{3}\). \(\mathcal{A}^{u}\) has access to the public key used for encrypting and to the history of simulated executions of \(\Pi_{3}\) that includes the transmitted messages. \(\mathcal{A}^{u}\) is also allowed to have access to the list of the valid identifiers of all vehicles \(ID_{1},ID_{2},\ldots,ID_{N}\) (although in real life adversary has no knowledge of the list of the identifiers!). \(\mathcal{A}^{u}\) attempts to relate any of the messages sent with a valid identified \(ID_{i}\). We say that \(\mathcal{A}^{u}\) succeeds if it successfully relates a message with the correct identifier. If \(\mathcal{A}^{u}\) succeeds then \(\mathit{Priv}_{\mathcal{A}^{u},\Pi_{3}}(n)\) outputs \(1\) and zero otherwise.  
**Definition 2**.: \(\Pi_{3}\) _provides message unlinkability if for all PPT adversary \(\mathcal{A}^{u}\) there exists a negligible function negl such that:_  
\[Adv(\mathcal{A}^{u})=|\mathit{Pr}[\mathit{Priv}_{\mathcal{A}^{u},\Pi_{3}}](n )=1]-1/N|=\mathit{negl}(n)\]  
_Where \(N\) is the number of different credentials. That is \(\mathcal{A}^{u}\) is no better than picking at random. We say that \(\Pi_{3}\) provides unlinkability._  
**Claim 2**.: \(\Pi_{3}\) provides message unlinkability.  
Proof.: We assume all communication is encrypted using the public key of SA. The ElGamal scheme, on which the AoN-PKEET is based, provides IND-CPA security under the DDH assumption. After polynomially many executions of \(\mathcal{O}_{\Pi_{3}}\) the adversary will pick an identifier \(ID\) from the list of identifiers. By simulating the IND-CPA game it will attempt to guess if the next message sent to SA is the encryption of \(ID\) or not. Since ElGamal offers IND-CPA security this is possible only with negligible probability. Thus, there exists a negligible function \(\mathit{negl}\) such that:  
\[Adv(\mathcal{A}^{\mathcal{U}})=|\mathit{Pr}[\mathit{Priv}_{\mathcal{A}^{U},\Pi _{3}}(n)=1]-1/N|=\mathit{negl}(n).\qed\]  
**Traceability:** Only CA can extract the real identity of the vehicle if necessary.  
It is obvious that if all three entities collude, traceability is possible. A message is forwarded to RSU, then the encrypted credential can be related to the message sent. The timestamp can be forwarded from the RSU to the SA. This however is a desired protocol function that allows us to address the issue of misbehaving drivers, but only if all the entities collide (e.g., after a legal claim has been issued).