## 4 Security Proofs
### Unlinkability  
In our scheme, a mobile user gets an initial anonymous ticket by running the requesting ticket protocol in Section 3.3 and obtains a renewed one when running the using ticket protocol in Section 3.4. In either Sections 3.3 or 3.4, the mobile user performs the similar operations to get an anonymous ticket. Here, we define a game as follows. Definition 2: Let \(k\) be a security parameter, \(MS_{0}\) and \(MS_{1}\) be two honest mobile users, and \(\mathcal{J}\) be the judge. The game is shown below. Step 1. According to our proposed scheme, \(H\) sets up the system parameters which contain \(H\)'s public key \((e_{H},n_{H})\), secret key \((d_{H},p_{H},q_{H})\), and hash functions \((F_{1},F_{2},F_{3})\). \(\mathcal{J}\) generates its key pair \((pk_{J},sk_{J})\). Step 2. \(H\) generates and outputs two messages \(m_{0}\) and \(m_{1}\). Step 3. Randomly pick a bit \(b\in\{0,1\}\) and place \(m_{b}\) and \(m_{1-b}\) on the private input tapes of \(MS_{0}\) and \(MS_{1}\), respectively. The bit \(b\) will not be revealed to \(H\). Step 4. \(H\) performs the protocol (Sections 3.3 or 3.4) of our scheme with \(MS_{0}\) and \(MS_{1}\), respectively, to issue blinded tickets to them. Step 5. If \(MS_{0}\) and \(MS_{1}\) output two tickets which are \((m_{b},\delta_{b},\sigma_{b},\gamma_{b},s_{b})\) and \((m_{1-b},\delta_{1-b},\sigma_{1-b},\gamma_{1-b},s_{1-b})\) on their private tapes, respectively, give the two 5-tuples in a random order to \(H\); Otherwise, \(\bot\) is given to \(H\). Step 6. \(H\) outputs \(b^{\prime}\in\{0,1\}\) as the guess of \(b\). \(H\) wins the game if \(b=b^{\prime}\). Define the advantage of \(H\) as  
\[Adv_{H}^{Linkability}(k)=|2P[b^{\prime}=b]-1|\]  
where \(P[b^{\prime}=b]\) denotes the probability of \(b^{\prime}=b\). Definition 3 (Unlinkability): In our scheme, the protocols in Sections 3.3 and 3.4 satisfy the unlinkability property if the advantage \(Adv_{H}^{Linkability}(k)\) in the game of Definition 2 is negligible. Theorem 4.1: If \(E_{pk_{J}}\) and \(E_{k}\) are two semantic secure encryption functions, our proposed protocols in Sections 3.3 and 3.4 satisfy the unlinkability property. Proof: In Step 5 of Definition 2, if \(H\) is given \(\bot\), it will determine \(b\) with probability \(\frac{1}{2}\) which is exactly the same as a random guess of \(b\). We assume that \(H\) gets \((m_{b},\delta_{b},\sigma_{b},\gamma_{b},s_{b})\) and \((m_{1-b},\delta_{1-b},\sigma_{1-b},\sigma_{1-b}\gamma_{1-b}s_{1-b})\). Let \((a_{i},\theta_{i},\gamma_{i},\mu_{i},\beta_{i},\rho_{i},\xi_{i},\iota_{i})\) and \((a_{i},\theta_{1_{i}},T_{i},m_{i}^{*},\
u_{i}^{\prime},\beta_{i},\rho_{i},\iota _{i})\) be the view of \(H\) to the protocol of Section 3.3 and the protocol of Section 3.4, respectively, where \(i\in\{0,1\}\) and \(\gamma_{0}=\gamma_{1}\). Consider \((\theta_{i},\gamma_{i},\mu_{i},\rho_{i},\xi_{i})\) in Section 3.3 where \(\theta_{i}=E_{pk_{J}}(k_{i},lD_{MS_{i}})\), \(\mu_{i}=lD_{MS_{i}}\), \(\rho_{i}=E_{k_{i}}(\delta_{i},b_{i},\sigma_{i})\), and \(\xi_{i}=E_{pk_{J}}(r_{z})\), \((\theta_{1_{i}},T_{i}=\{F_{1}(m_{1}^{*}),\delta_{i}^{*},\sigma_{1}^{*},\gamma_{i }^{*}\},m_{i}^{*},\
u_{i}^{\prime},\rho_{i})\) in Section 3.4 where \(\theta_{1_{i}}=E_{pk_{J}}(k_{i})\)\(\rho_{i}=E_{k_{i}}(\delta^{**}_{i},b_{i},\sigma^{**}_{i})\), and \(w^{\prime}_{i}\) is encrypted in \(\sigma_{i}=E_{pk_{i}}((w^{*}_{i}+w^{\prime}+i),r_{i_{i}})\), and \((\delta^{*}_{i},\sigma^{*}_{i})\) in \(T_{i}\) where \(\delta^{*}_{i}=E_{pk_{i}}(ID_{MS_{i}},F_{1}(\vec{r}^{\prime}_{i_{i}}))\) and \(\sigma^{*}_{i}=E_{pk_{i}}((\vec{w}^{*}_{i}+\vec{w}^{\prime}_{i}),\vec{r}^{ \prime}_{i_{i}})\). Since \(E_{pk_{i}}\) and \(E_{k_{i}}\) are semantically secure encryption functions, the information encrypted in the above ciphertexts will not be revealed. In both Sections 3.3 and 3.4, \((\alpha_{i},\beta_{i},t_{i})\) can be considered as follows.