## 5 Security Proof and Analysis
### Security Analysis  
We set several security goals in Section 2. Next, we delve into a detailed analysis of the security properties associated with the proposed scheme.  
1. Anonymity: OLDs in our system will not communicate with other entities with pseudo identities \(PID_{i}\), where \(PID_{i}=\{PID_{i,1},PID_{i,2}\},PID_{i,1}=ID_{i}\oplus H0(sk_{i}\cdot L_{i} \|T_{t}),PID_{i,2}=(sk_{i}\cdot L_{i})\oplus H1(T_{t})\). Malicious users are not able to obtain the sender's privacy only via public parameters and messages sent. This way, vehicles are allowed to send messages without exposing their real identities.
2. Authentication and Privacy: All messages sent by communicating parties should sign these messages before sending. They compute \(\sigma=sk_{i}+w_{i}\cdot r_{i}\ mod\ q\), where \(w_{i}=H2(M_{i}\|PID_{i}\|T_{t}\|R_{i}\|PK_{i})\). Then encapsulated messages \(msg=\{M_{i},T_{t},PK_{i},R_{i},PID_{i}\}\) are broadcasted. Thus, all interactive parties in our system can authenticate each other to ensure reliability and legitimacy. In addition, an encapsulated message \(msg\) includes no LC \(NLC_{i}\) explicitly, which will keep the basic location privacy of OLDs. But when needed, the GC can derive the rough location of \(v_{i}\) by computing \((PID_{i,2}\oplus H1(T_{t}))\cdot(PK_{i}\cdot\alpha)^{-1}\) from the \(msg\).
3. Traceability: When malicious messages are detected, the GC will extract vehicles' real identities by computing \(ID_{i}=H0(PK_{i}\cdot\alpha\cdot NLC_{i}\|T_{t})\oplus PID_{i,1}\), since \(sk_{i}\cdot L_{i}=sk_{i}\cdot\alpha\cdot NLC_{i}\cdot P=PK_{i}\cdot\alpha\cdot NLC _{i}\) and \(NLC_{i}=(PID_{i,2}\oplus H1(T_{t}))\cdot(PK_{i}\cdot\alpha)^{-1}\) can be easily derived via messages.
4. Unlinkability: Every time, to generate a message \(msg:\{M_{i},T_{t},PK_{i},R_{i},PID_{i}\}\), a random number \(r_{i}\in Z_{q}\) will be reselected and a new \(w_{i}=H2(M_{i}\|PID_{i}\|T_{t}\|R_{i}\|PK_{i})\) will be recomputed. Due to the randomness of \(r_{i}\) and the variability of \(w_{i}\), a malicious party is unable to link messages sent by one OLD to itself. Therefore, the proposed scheme offers unlinkability in interactive communications.
5. Resistance to common attacks: Our scheme is capable of countering common attacks present in traditional networks, such as the following: * _Replay Attack_: By encapsulating the timestamp \(T_{t}\) within the message, it prevents the message from being forwarded again in the future. Upon receiving the message, receivers first check the timestamp to verify its freshness. If it is still fresh, the receiver will start to verify the validation of these messages. Otherwise, messages will be abandoned.
* _Impersonation Attack_: An adversary needs to generate a signature for the message msg that satisfies \(\sigma\cdot P=PK_{i}+w_{i}\cdot R_{i}\) in order to impersonate a legitimate vehicle. However, based on Theorem 1, no adversary can forge such a signature in polynomial time, which proves that our scheme is capable of resisting impersonation attacks.
* _Modification Attack_: A signature \(\sigma=sk_{i}+w_{i}\cdot r_{i}\ mod\ q\) is a digital signature related to \(M_{i}\) since \(w_{i}=H2(M_{i}\|PID_{i}\|T_{i}\|R_{i}\|PK_{i})\). If \(M_{i}\) is modified by a malicious party, then \(w_{i}\) will change consequently, which makes \(\sigma\) change as well. Hence, the modification can be easily detected if the message itself is modified. This way, our scheme is able to resist modification attacks.
* _Sybil Attack_: To start a sybil attack, the adversary must generate multiple identities to play multiple roles. However, the pseudo identities are computed by a tamper-proof device. An adversary must violate the device first to generate those identities, which is infeasible via current technologies. Hence, our scheme successfully defends against sybil attacks.