## 4 Security Proofs
### Ticket Unforgeability  
In 2003, [PERSON] _et al._ introduced a problem called the RSA Chosen Target Inversion (RSA-CTI) Problem [20]. Then they proved that the Full Domain Hash RSA (FDH-RSA) blind signature is unforgeable as long as the RSA-CTI problem is hard. In this section, we will show that the ticket requesting protocol of Section 3.3 and the ticket using protocol of Section 3.4 satisfy unforgeability as long as the FDH-RSA blind signature is with unforgeability. **Theorem 2**. : _If an attacker \(\mathcal{A}\) can forge an unused ticket in the proposed scheme (Sections 3.3 or 3.4) with probability at least \(\epsilon_{\mathcal{A}}\) in time \(t_{\mathcal{A}}\), there exists a forget \(\mathcal{F}\) that can break the unforgeability of the FDH-RSA blind signature with probability at least \(e^{\prime}\) in time \(t^{\prime}\) such that_  
\[\left\{ \begin{array}{l}e^{\prime}\geq\epsilon_{\mathcal{A}}\\ t^{\prime}\approx t_{\mathcal{A}}+q_{\mathcal{F}}t_{\mathcal{F}}+2q_{ \mathcal{F}}t_{S_{D}}\end{array} \right. \tag{7}\]  
_where \(q_{\mathcal{F}}\) is the number of queries \(\mathcal{A}\) makes to \(\mathcal{F}\), \(t_{\mathcal{F}}\) is the time for \(\mathcal{F}\) to deal with a query, and \(t_{S_{D}}\) is the time for the FDH-RSA blind signing oracle to process a signing query._  
Proof. : The model of this proof is shown as Figure 6. Let \(S_{D}\) be the FDH-RSA blind signing oracle. The public key of \(S_{D}\) is \((e_{H},n_{H})\). First, \(\mathcal{F}\) initializes the environment by generating the public/private key pair \((pk_{j},s_{I})\) of the judge and selecting three hash functions \((F_{1},F_{2},F_{3})\). Then \(\mathcal{F}\) publishes \((pk_{I},e_{H},n_{H},F_{1},F_{2},F_{3})\). \(\mathcal{F}\) utilizes \((e_{H},n_{H})\) as the public key of \(H\) of the system. \(\mathcal{F}\) will simulate the system such that \(\mathcal{A}\) can query \(\mathcal{F}\) to get tickets. If \(\mathcal{A}\) can output \(q_{\mathcal{F}}+1\) tickets after querying \(\mathcal{F}\)\(q_{\mathcal{F}}\) times, we can succeed in one-more forgery to break the unforgeability of the FDH-RSA blind signature scheme. Here, we just show how to simulate the ticket requesting protocol of Section 3.3. The simulation of the ticket using protocol in Section 3.4 is similar to that of the protocol in Section 3.3. Figure 6: The model of the proof for unforgeability. When \(\mathcal{A}\) submits a query \((\alpha_{i},\theta_{i})\) to \(\mathcal{F}\), \(\mathcal{F}\) will return \((t_{i},\rho_{i},\gamma_{i})\) to \(\mathcal{A}\). \(\mathcal{F}\) is depicted in Figure 7. Finally, \(\mathcal{A}\) outputs \(q_{\mathcal{F}}\,+\,1\) tickets \((s_{i},m_{i},\delta_{i},\sigma_{i},\gamma_{i})\) where \(m_{i}\
eq m_{i^{\prime}}\), \(\delta_{i}\
eq\delta_{i^{\prime}}\), \(\sigma_{i}\
eq\sigma_{i^{\prime}}\), and \(1\leq i\
eq i^{\prime}\leq q_{\mathcal{F}}+1\). The outputted tickets can be categorized into two subsets \(S_{T}\) and \(S_{T^{\prime}}\) where \(|S_{T}|=q_{1}\) and \(|S_{T^{\prime}}|=q_{2}\). For each ticket \((s_{j},m_{j},\delta_{j},\sigma_{j},\gamma_{j})\) in \(S_{T}\), \((\delta_{j},\sigma_{j})\) is in \(L\) where \(1\leq j\leq q_{1}\), _i.e._, the tickets in \(S_{T}\) are queried from \(\mathcal{F}\). On the other hand, each ticket in \(S_{T^{\prime}}\) is forged by \(\mathcal{A}\). We say that \(\mathcal{A}\) successfully breaks our scheme if (1) \(q_{1}\,+\,q_{2}\,=q_{\mathcal{F}}\,+\,1\); (2) \(q_{1}\in[0,q_{\mathcal{F}}]\); and (3) \(q_{2}\in[1,q_{\mathcal{F}}+1]\). In the followings, we will show that we can obtain \((q_{\mathcal{F}}+q_{1}+2q_{2})\) signatures by querying \(S_{D}\)\((2q_{\mathcal{F}}\,+\,q_{2})\) times where \((q_{\mathcal{F}}+q_{1}+2q_{2})\,-\,(2q_{\mathcal{F}}\,+\,q_{2})=q_{1}\,+\,q_{2} \,-\,q_{\mathcal{F}}=1\).