## 4 Concrete Construction of IBMS\({}^{\mathbf{CR}\)-1
### Security Proof
\(\mathcal{C}\) looks up \(R_{i}\) such that \((R_{i},t_{i})\) where \(2\leqslant i\leqslant n\). If for some \(i\) the record is found, \(\mathcal{C}\) also stops. Otherwise, \(\mathcal{C}\) calculates \(R=\prod_{i=1}^{n}R_{i}\pmod{N}\) and sets \(h_{3}(R\|S\|m)=w\), or stops if the entry has already existed. * \(\mathcal{C}\) sends \(R_{1}\) to other signers. After receiving \(R_{2}^{\prime},\cdots,R_{n}^{\prime}\) from the signers, \(\mathcal{C}\) verifies that \(h_{2}(R_{i}^{\prime})\stackrel{{?}}{{=}}t_{i}\). \(\mathcal{C}\) ends up with the protocol if one of these does not satisfy this, which means \(\mathcal{A}\) has to guess the results of the hash value. If \(R_{i}\
eq R_{i}^{\prime}\) for some \(i\), \(\mathcal{C}\) stops. \(\mathcal{C}\) sends \(u_{i}\) to the signers, receives \(u_{2},u_{3},\cdots,u_{n}\), and calculates \(u=\prod_{i=1}^{n}u_{i}\pmod{N}\). Finally, \(\mathcal{C}\) sends \(m\sigma=(w,u)\) to \(\mathcal{A}\). At the end of the game, \(\mathcal{A}\) generates a multi-signature \(m\sigma^{*}=(w^{*},u^{*})\) on message \(m^{*}\). \(\mathcal{C}\) calculates  
\[R^{*}\leftarrow(u^{*})^{3^{\ell}}\prod_{i=1}^{n}\left((-1)^{\varepsilon_{ID_{ i}2}}a^{\varepsilon_{ID_{i}1}}h_{1}(ID_{i}^{*})\right)^{-w^{*}} \tag{6}\]  
and makes an additional query \(h_{3}(R^{*}\|IDSet^{*}\|m^{*})\). We let \(U\subseteq IDSet^{*}=\{ID_{1}^{*},ID_{2}^{*},...,ID_{n}^{*}\}\) denote the honest IDSet, that is, \(\mathcal{A}\) never compromised. If \(\mathcal{A}\) succeeded in forgery, that is,  
* **MVerify \((mpk,IDSet^{*},m^{*},\sigma^{*})=1\)**
* \(U\
eq\emptyset\)
* \(\mathcal{A}\) has never queried \((IDSet^{*},m^{*})\) to the signature oracle then \(\mathcal{C}\) checks the \(h_{1}\)-list. If the multi-signature is valid, we can obtain \[u^{*^{3^{\ell}}} \equiv R^{*}\prod_{i=1}^{n}\left((-1)^{\varepsilon_{ID_{i}2}}a^{ \varepsilon_{ID_{i}1}}h_{1}(ID_{i}^{*})\right)^{w^{*}}\] (7) \[\equiv R^{*}\prod_{i=1}^{n}s_{i}^{*^{3^{\ell}}w^{*}}\pmod{N}\]  
We let \(s^{*}\leftarrow\prod_{i=1}^{n}(s_{i}^{*})^{3^{\ell}}\pmod{N}\) and produce \((s^{*},\sigma^{*})\). To factor \(N\) by applying the rewinding technique, \(\mathcal{C}\) plays with \(\mathcal{A}\) once again using the random tapes, which are the same as for the first time. Because \(\mathcal{C}\) previously recorded the transcripts, \(\mathcal{C}\) obtains the same results for \(\mathcal{A}\)'s queries. When \(\mathcal{A}\) queries for \(h_{3}\), \(\mathcal{C}\) randomly selects an alternative answer \(w^{\prime}\) instead of \(w\), as, in the second run, the \(h_{1}\)- and \(h_{2}\)-query are equal to those of the first round. \(\mathcal{C}\) generates \((s,m\sigma)\) and \((s^{\prime},m\sigma^{\prime})\) such that  
\[u^{3^{\ell}}\equiv Rs^{w}\;\;and\;\;u^{*^{3^{\ell}}}\equiv R^{\prime}s^{\prime w ^{\prime}}\]  
By \(R=R^{\prime}\), \(m=m^{\prime}\) and \(s=s^{\prime}\), we have  
\[\left(\frac{u}{u^{\prime}}\right)^{3^{\ell}}\equiv s^{(w-w^{\prime})}\pmod{N} \tag{8}\]Because \(w\
eq w^{\prime}\in\{0,1\}^{\ell_{0}}\) and \(\ell_{0}<\ell\), we can obtain \(|w-w^{\prime}|<3^{\ell}\). According to Theorem 2, \(\mathcal{C}\) can calculate a cubic root \(\tilde{s}\) where \(\tilde{s}^{3}=s\). Meanwhile, \(\mathcal{C}\) checks the \(h_{1}\)-list to search for an entry in which \(ID_{i}\in IDSet\) and calculates \(\tilde{s}=\prod_{i\in IDSet}s_{i}^{3^{\ell-1}}\). Therefore, \(\tilde{s}^{3}\equiv\tilde{s}^{3}\equiv s\pmod{N}\). If \(\tilde{s}\
eq\tilde{s}\pmod{N}\), \(N\) can be factored by Theorem 1. Otherwise, \(\mathcal{C}\) cannot factor \(N\). The probability that \(\tilde{s}\
eq\tilde{s}\pmod{N}\) is \(2/3\). Finally, we calculate the probability that \(\mathcal{C}\) returns a _valid_ result. Because most of the simulation game is similar to in [6], we set \(\epsilon^{\prime}\), \(\epsilon\) and \(\epsilon^{*}\) as the probability to factor \(N\) by \(\mathcal{C}\), the probability to forge a multi-signature in practice by \(\mathcal{A}\) and the probability to succeed in the first run before the rewinding technique by \(\mathcal{A}\), respectively.