## 4 Security Proofs
### Ticket Swinding Resistance
There is also an oracle \(\mathcal{O}_{T}\) which plays the role of \(H\) in the protocol of Section 3.3 (or Section 3.4) to issue tickets. \(\mathcal{O}_{T}\) will return \((t,\rho,\gamma)\) when it is queried with \((\alpha,\theta)\). Assume that an attacker \(\mathcal{A}_{TS}\) performs at most \(q_{1}\) times of \(Execute(\Pi_{MS_{i},V_{j}}^{u}\), \(\Pi_{V_{j},MS_{i}}^{v})\) queries, \(q_{2}\) times of \(Send(\Pi_{MS_{i},V_{j}}^{u},\mathcal{N})\) queries, and \(q_{3}\) times of \(Send(\Pi_{V_{j},MS_{i}}^{v},\mathcal{M})\) queries. \(\mathcal{A}_{TS}\) can also submit a \(Reveal(T)\) query to get the secret \(m\) of \(T\) where \(T\) must have been consumed for authentication. \(\mathcal{S}_{TS}\) initializes four global parameters which are \(i_{guess}=0\), \(s_{guess}=0\), \(T_{guess}=\mathcal{N}\), and \(r_{guess}=\mathcal{N}\). Then \(\mathcal{S}_{TS}\) guesses that the attacker \(\mathcal{A}_{TS}\) will swindle \(T\) which is returned from the \(\lambda\)th \(Send(\Pi_{MS_{i},V_{j}}^{u},\mathcal{N})\) query. When \(Execute(\Pi_{MS_{i},V_{j}}^{u},\Pi_{V_{j},MS_{i}}^{v})\) is queried, the oracle \(\Pi_{MS_{i},V_{j}}^{u}\) will run the protocol of Section 3.3 (or Section 3.4) with \(\mathcal{O}_{T}\) to get a ticket \((m,\delta,\sigma,\gamma,s)\) and prepares \(T=(F_{1}(m),\delta,\sigma,\gamma,s)\). Then it takes \(T\) to perform the protocol of Section 3.4 with \(\Pi_{V_{j},MS_{i}}^{v}\) under the presence of \(\mathcal{A}_{TS}\). When \(Send(\Pi_{MS_{i},V_{j}}^{u},\mathcal{M})\) and \(Send(\Pi_{V_{j},MS_{i}}^{v},\mathcal{M})\) are queried, \(\Pi_{MS_{i},V_{j}}^{u}\) and \(\Pi_{V_{j},MS_{i}}^{v}\) will act according to Figure 11. There are five lists in Figure 11 where \(L_{T_{MS}}\) and \(L_{T_{V}}\) are used to record the transcript of \(\[PERSON]_{MS_{i},V_{j}}^{u}\) and \(\[PERSON]_{V_{j},MS_{i}}^{v}\), \(L_{K_{MS}}\) and \(L_{K_{V}}\) store the session keys of \(\[PERSON]_{MS_{i},V_{j}}^{u}\) and \(\[PERSON]_{V_{j},MS_{i}}^{v}\), and \(L_{usedT}\) records all used \(T\)'s. Figure 10: The model of the proof of Ticket Swindling Resistance. In Figure 11, \(s_{guess}\) denotes the session \(u\) of \(\[PERSON]^{u}_{MS_{i},V_{j}}\). \(\Pi^{u}_{MS_{i},V_{j}}\) checks if the current session \(u\) is corresponding to the \(\lambda\)th \(\mathit{Send}(\Pi^{u}_{MS_{i},V_{j}},\mathcal{N})\) query (line 27 to line 30). If true, it randomly selects \(r_{5}\in\{0,1\}^{lr}\). Here, \(\Pi^{u}_{MS_{i},V_{j}}\) does not know \(x\) and sets \(F_{3}(r_{2}||r_{4})=\bot\). The simulation will fail if \(\mathcal{A}_{TS}\) sends a query \((r_{2}||r_{4})\) to \(\mathcal{O}_{F_{3}}\). However, we will show that the probability of the above failure is negligible in Appendix. In Figure 11, \(\Pi^{v}_{V_{j},MS_{i}}\) checks if \(r_{f_{3}}\) is equal to \(\bot\). If true, this means that the current session \(v\) matches the \(\lambda\)th \(\mathit{Send}(\Pi^{u}_{MS_{i},V_{j}},\mathcal{N})\) query. After finishing the simulation, \(\mathcal{S}_{TS}\) can retrieve \((m,T)\) from \(L_{\mathit{usedT}}\) via \(T_{guess}\). If \(m\
eq\bot\), \(\mathcal{S}_{TS}\) has that \(T_{guess}=T=(m^{\prime}=y,\delta,\sigma,\gamma,s)\) where \(y=F_{1}(m)=m^{\epsilon}\) mod \(N\). Thus, \(\mathcal{S}_{TS}\) solves the RSA-STI problem. Therefore, \(\mathcal{A}_{TS}\), with non-negligible probability at least \(\epsilon_{TS}\), can consume an eavesdropped \(T\) to successfully perform the anonymous authentication protocol of Section 3.4 with \(\Pi^{v}_{V_{j},MS_{i}}\), \(\mathcal{S}_{TS}\) can solve the RSA-STI problem with non-negligible advantage at least \(\frac{\epsilon_{TS}}{q_{2}}\).