## 5 Concrete Construction of IBMS\({}^{\bf CR}\)-2
### Security Proof  
**IBMSCR-2** is secure under the factorization in the random oracle model.  
**Theorem 7**.: _If integer factorization is \((t^{\prime},\epsilon^{\prime})\)-hard, our IBMS\({}^{CR}\)\(-\)2 scheme is \((t,q_{H},q_{E},q_{S},n,\epsilon)\)-secure against existential forgery in the random oracle model._  
Because most of the simulation game between \(\mathcal{A}\) and \(\mathcal{C}\) is the same, we give the security proof simply.  
Proof.: When it is given an integer factorization instance \(N\), \(\mathcal{C}\) returns \(p\) or \(q\) if \(\mathcal{A}\) succeeds in forging a multi-signature.  
\(\mathcal{C}\) sends \(mpk=\{N,h_{1},h_{2},h_{3},a,\eta,\lambda\}\) to \(\mathcal{A}\). \(\mathcal{C}\) maintains several lists (\(list_{h_{1}}\), \(list_{h_{2}}\), \(list_{h_{3}}\), \(list_{S}\)).  
* \(h_{1}\)**-Query**. \(\mathcal{C}\) manages a list \((ID,c,h_{1},s)\). \(\mathcal{C}\) sends \(h_{1}\) to \(\mathcal{A}\) if \(ID\) exists when \(\mathcal{A}\) queries the hash value of \(ID\). Otherwise, \(\mathcal{C}\) randomly selects \(s\in\mathbb{Z}_{N}^{*}\) and \(c\in\{0,1,2\}\), sets \(h_{1}\equiv s^{3}/a^{c}\pmod{N}\), returns \(h_{1}\), and adds \((ID,c,h_{1},s)\) to \(list_{h_{1}}\).
* The \(h_{2}\)**-query**, \(h_{3}\)**-query** and **extraction query** are similar to **IBMS\({}^{CR}\)\(-\)1**.
* The **multi-signature query** is similar to **IBMS\({}^{CR}\)\(-\)1**, except that Equation (5) changes to \[R_{1}=u_{1}^{3}\prod_{i=1}^{n}\left(a^{c_{ID_{i}}}\cdot h_{1}(ID_{1})\right)^{ -w^{*}}\] (14) At the end of the game, \(\mathcal{A}\) forges \(m\sigma^{*}=(w^{*},u^{*})\) with \(IDSet^{*}\) on \(m^{*}\). \(\mathcal{C}\) calculates \[R^{*}\leftarrow(u^{*})^{3}\prod_{i=1}^{n}\left(a^{c_{ID_{i}^{*}}}\cdot h_{1}( ID_{i}^{*})\right)^{-w^{*}}\] (15) and queries \(h_{3}(R^{*}\|IDSet^{*}\|m^{*})\) to the hash oracle. If the forgery is valid, we obtain that \[u^{*3}\equiv R^{*}\prod_{i=1}^{n}\left(a^{c_{ID_{i}^{*}}}\cdot h_{1}(ID_{i}^{ *})\right)^{w^{*}}\equiv R^{*}\prod_{i=1}^{n}\left(s_{i}^{*3}\right)^{w^{*}} \equiv R^{*}s^{*w^{*}}\pmod{N}\] (16) because \(s^{*}\leftarrow\prod_{i=1}^{n}(s_{i}^{*})^{3}\pmod{N}\). \(\mathcal{C}\) returns \((s^{*},w^{*},u^{*})\).  
We also apply the rewinding technique to factor \(N\). At last, \(\mathcal{C}\) obtains \((s,w,u)\) and \((s^{\prime},w^{\prime},u^{\prime})\) such that  
\[u^{3}\equiv Rs^{w}\;\;\text{and}\;\;u^{\prime 3}\equiv R^{\prime}s^{\prime w^{ \prime}} \tag{17}\]  
Because \(R=R^{\prime}\), \(m=m^{\prime}\), and \(s=s^{\prime}\), we have  
\[\left(\frac{u}{u^{\prime}}\right)^{3}\equiv s^{(w-w^{\prime})}\pmod{N} \tag{18}\]  
Because \(w\
eq w^{\prime}\), two cases emerge:  
* If \(w-w^{\prime}\equiv 1\pmod{3}\), we denote \(w-w^{\prime}=3k+1\) for an integer \(k\). Therefore, \(s\equiv\left(\frac{u}{u^{\prime},s^{k}}\right)^{3}\), that is, \(\tilde{s}=\frac{u}{u^{\prime},s^{k}}\) satisfies \(\tilde{s}^{3}\equiv s\pmod{N}\).
* If \(w-w^{\prime}\equiv-1\pmod{3}\), we denote \(w-w^{\prime}=3k-1\) for an integer \(k\). Therefore, \(s\equiv(\frac{u,s^{k}}{u^{\prime}})^{3}\), that is, \(\tilde{s}=\frac{u,s^{k}}{u^{\prime}}\) satisfies \(\tilde{s}^{3}\equiv s\pmod{N}\).  
From the discussion above, \(\mathcal{C}\) calculates a cubic root \(\tilde{s}\) where \(\tilde{s}^{3}=s\). Meanwhile \(\mathcal{C}\) searches the entries in the \(h_{1}\)-list where \(ID_{i}\in IDSet\) and calculates \(\tilde{s}=\prod_{i\in IDSet}\tilde{s}_{i}^{3}\). Therefore, we have \(\tilde{s}^{3}\equiv\tilde{s}^{3}\equiv s\pmod{N}\). If \(\tilde{s}\
eq\tilde{s}\pmod{N}\), we can factor \(N\) by Theorem 1 with a probability that \(\tilde{s}\
eq\tilde{s}\pmod{N}\) of \(2/3\).  
Thus, we have finished the proof.