# An Enhanced Privacy-Preserving Authentication Scheme for Vehicle Sensor Networks
## 6 Analysis
### Security Analysis
#### 6.2.1 The Formal Security Analysis  
**Theorem 1**. : _Let \(GAP\) denote the general authentication procedure presented in Figure 4. Let \(|Hash|\) and \(|D|\) denote the range space of the hash function and the size of the password dictionary \(D\), respectively. Finally, let \(A\) represent an adversary within a polynomial time \(t\) against the semantic security of \(GAP\) by issuing \(q_{send}\) Send queries, \(q_{exc}\) Execute queries and \(q_{h}\) hash queries. Then, we have_  
\[Adv_{GAP,D}(A)\leq\frac{q_{h}^{2}}{|Hash|}+\frac{2q_{send}}{|D|}.\]  
**Proof of Theorem 1. ** To complete the proof, four experiments are constructed, where the first one simulates a real attack. For every experiment \(Exp_{n}\), we use an event \(Succ_{n}\) to denote the event in which the adversary successfully guesses the bit \(b\) from the _Test_ query. **Experiment \(Exp_{0}\)**. This experiment simulates an actual attack. According to definition, we have  
\[Adv_{GAP,D}(A)=2 Pr[Succ_{0}]-1. \tag{1}\]  
**Experiment \(Exp_{1}\)**. In this experiment, the oracles _Execute_, _Send_, _Corrupt_, _Reveal_, _Test_ as in an actual attack are simulated. It can be seen that one cannot distinguish this experiment from the actual experiment. Thus,  
\[Pr[Succ_{1}]=Pr[Succ_{0}]. \tag{2}\]  
**Experiment \(Exp_{2}\)**. All oracles considered in experiment \(\text{Exp}_{1}\) are also simulated in this experiment; however, all executions are halted where a collision occurs when simulating the _Send_ and the \(h\) oracle. \(A\) issues _Send_ to try to deceive the other participants into accepting a modified message. Simultaneously, it can query the \(h\) oracle to verify whether a hash collision exists. Since the messages transmitted in the network are all associated with a participant's identity, a temporary secret random number and a long-lived key, and the authentication procedure only uses an XOR operation and a hash function, there is no other collision except hash collision. The probability of collision in the \(h\) oracle is at most \(q_{h}^{2}/2|Hash|\) by the birthday paradox. Hence,  
\[|Pr[\text{Succ}_{1}]-Pr[\text{Succ}_{2}]|\leq\frac{q_{h}^{2}}{2|Hash|}. \tag{3}\]  
**Experiment \(Exp_{3}\)**. All oracles considered in experiment \(\text{Exp}_{2}\) are simulated in this experiment, in addition to stopping the stimulation of a \(Corrupt\) query to an OBU. Note that the information \(B_{i}\), \(C_{i}\),\(D_{i}\), \(y_{i}\), \(Z_{i}\) and \(P_{pub_{i}}\) stored in the OBU can be extracted by \(A\) when the \(Corrupt(U_{i})\) query is issued. However, this information is useless to \(A\) for calculating the session key since it would also need the secret \(A_{i}\), and it is difficult to derive \(A_{i}\) from \(B_{i}\) without also obtaining the user's correct password \(PW_{i}\) via the password attack. Hence, we obtain  
\[|Pr[\text{Succ}_{2}]-Pr[\text{Succ}_{3}]|\leq\frac{q_{send}}{|D|}. \tag{4}\]  
In addition, we know that the adversary \(A\) can only win the game by guessing the bit \(b\) when querying the _Test_ oracle because the adversary has no advantage. Therefore,  
\[Pr[\text{Succ}_{3}]=\frac{1}{2}. \tag{5}\]  
From Equations (2) to (5), we have  
\[|Pr[\text{Succ}_{0}]-\frac{1}{2}| =|Pr[\text{Succ}_{0}]-Pr[\text{Succ}_{3}]|\] \[\leq|Pr[\text{Succ}_{0}]-Pr[\text{Succ}_{1}]|+|Pr[\text{Succ}_{1 }]-Pr[\text{Succ}_{2}]|\] \[+|Pr[\text{Succ}_{2}]-Pr[\text{Succ}_{3}]|\] \[Adv_{GAP,D}(A)\leq\frac{q_{h}^{2}}{|Hash|}+\frac{2q_{send}}{|D|}.\]0  
Therefore, from Equation (1), we get  
\[Adv_{GAP,D}(A)\leq\frac{q_{h}^{2}}{|Hash|}+\frac{2q_{send}}{|D|}.\]1  
**Theorem 2**. : _Let \(G\) represent a group with a prime order \(p\), and \(SCP\) denote the secure communication procedure presented in \[Adv_{GAP,D}(A)\leq\frac{q_{h}^{2}}{|Hash|}+\frac{2q_{send}}{|D|}.\]2 Let \(\ell\) be the size of the identity space, \(|Hash|\) and \(|D|\) represent the range space of the hash function and the size of the password dictionary \(D\).