## 4 Security Proofs
### Secure Mutual Authentication  
In order to prove the security of mutual authentication in the proposed scheme, we first introduce _Matching Conversations_ and _No Matching\({}^{E}(k)\)_[21; 22] as follows. **Definition 9** (Matching Conversations). : _Fix a number of flows \(R=2\rho-1\) and an \(R\)-flow protocol \(P=(\Pi,\mathcal{G})\) where \(\Pi\) specifies how players behave and \(\mathcal{G}\) generates key pairs for each entity. Run \(P\) in the presence of an adversary \(E\) and consider two oracles \(\Pi^{u}_{MS_{i},V_{j}}\) and \(\Pi^{v}_{V_{j},MS_{i}}\), that engage in conversations \(K\) and \(K^{\prime}\) respectively._  
1. \(K^{\prime}\) is a matching conversation to \(K\) if there exist \(\tau_{0}<\tau_{1}<\cdots<\tau_{R-1}\) such that \(K\) is prefixed by  
Figure 11: The oracle \(\Pi^{u}_{MS_{i},V_{j}}\) in the proof of Ticket Swindling Resistance. \[(\tau_{0},\mathcal{N},\alpha_{1}),(\tau_{2},\beta_{1},\alpha_{2}),\ldots,(\tau_{2 \rho-2},\beta_{\rho-1},\alpha_{\rho})\]  
and \(K^{\prime}\) is prefixed by  
\[(\tau_{1},\alpha_{1},\beta_{1}),(\tau_{3},\alpha_{2},\beta_{2}),\ldots,(\tau_{2 \rho-3},\alpha_{\rho-1},\beta_{\rho-1})\]
2. \(K\) is a _matching conversation_ to \(K^{\prime}\) if there exist \(\tau_{0}<\tau_{1}<\cdots<\tau_{R}\) such that \(K^{\prime}\) is prefixed by \[(\tau_{1},\alpha_{1},\beta_{1}),(\tau_{3},\alpha_{2},\beta_{2}),\ldots,(\tau_{ 2\rho-3},\alpha_{\rho-1},\beta_{\rho-1}),(\tau_{2\rho-1},\alpha_{\rho},*)\] and \(K\) is prefixed by \[(\tau_{0},\mathcal{N},\alpha_{1}),(\tau_{2},\beta_{1},\alpha_{2}),\ldots,( \tau_{2\rho-2},\beta_{\rho-1},\alpha_{\rho})\]  
Finally, \(\Pi^{u}_{MS_{i},V_{j}}\) and \(\[PERSON]^{v}_{V_{j},MS_{i}}\) are said to have had _matching conversations_ if \(K\) is a matching conversation to \(K^{\prime}\) and \(K^{\prime}\) is a matching conversation to \(K\). **Definition 10** (No Matching\({}^{E}(k)\)). : _Let \(k\in\mathbb{N}\) be the security parameter. No Matching\({}^{E}(k)\) is that when protocol \(P\) is run against an adversary \(E\), there exists an oracle \(\Pi^{u}_{MS_{i},V_{j}}\) with \(MS_{i},V_{j}\
otin S_{C}\) (where \(S_{C}\) denotes the set of entities corrupted by \(E\)) which accepted but there is no oracle \(\[PERSON]^{v}_{V_{j},MS_{i}}\) which has had a matching conversation to \(\[PERSON]^{u}_{MS_{i},V_{j}}\), or vice versa._  
**Definition 11**. : _A protocol \(P\) is a secure mutual authentication protocol if for every polynomial-time adversary \(E\): 1. If \(\[PERSON]^{u}_{MS_{i},V_{j}}\) and \(\[PERSON]^{v}_{V_{j},MS_{i}}\) have matching conversations, then both oracles accept; 2. The probability of No Matching\({}^{E}(k)\) is negligible._  
**Theorem 5**. : _The protocol of Section 3.4 is a secure mutual authentication protocol._  
Proof. : Our authentication protocol satisfies the first condition of Definition 11, if the the adversary acts as a wire. Hence, we concentrate on the proof for the second condition. When we carry out the experiment of the communication model against \(E\), \(E\) may succeed in the following two cases. Case 1 is that there exists an oracle \(\[PERSON]^{u}_{MS,V_{j}}\) which accepted, where \(MS_{i},V_{j}\
otin S_{C}\) and \(S_{C}\) is the set of corrupted entities, but there is no oracle \(\[PERSON]^{v}_{V_{j},MS_{i}}\) has a matching conversation to \(\[PERSON]^{u}_{MS_{i},V_{j}}\). Case 2 is that there exists an oracle \(\[PERSON]^{v}_{V_{j},MS_{i}}\) which accepted but there is no oracle \(\[PERSON]^{u}_{MS,V_{j}}\) has a matching conversation to \(\[PERSON]^{v}_{V_{j},MS_{i}}\). Suppose that \(E\) has probability \(\epsilon_{1}\) in Case 1 and \(\epsilon_{2}\) in Case 2. Thus, we conclude that if _No Matching\({}^{E}(k)\)_ is non-negligible, \(\epsilon_{1}\) or \(\epsilon_{2}\) must be non-negligible. In Case 1, \(E\) has to make \(\mathit{Send}(\[PERSON]^{u}_{MS_{i},V_{j}},\mathcal{N})\) query at some time \(\tau_{0}\) and make \(\mathit{Send}(\Pi^{u}_{MS_{i},V_{j}},(r_{1},r_{4}))\) query at some time \(\tau_{2}>\tau_{0}\).