## 4 Concrete Construction of IBMS\({}^{\mathbf{CR}\)-1
### Security Proof  
**IBMSC**-**1** is provably secure under the factorization in the random oracle model. **Theorem 6**: _If the factorization problem is \((t^{\prime},\epsilon^{\prime})\)-hard, \(\textbf{IBMS}^{\textbf{CR}}\textbf{-1}\) is \((t,q_{E},q_{H},q_{S},n,\epsilon)\)-secure against existential forgery attackers under the adaptively chosen message attack and chosen identity attack. We have estimates for \(t^{\prime}\) and \(\epsilon^{\prime}\) as follows:_  
\[\epsilon^{\prime}\geqslant\frac{2\epsilon^{2}}{3(q_{H}+1)}-\left(\frac{2 nq_{ S}q_{H}+n^{2}q_{S}^{2}+q_{H}^{2}}{2^{\ell_{R}}\cdot(q_{H}+1)}+\frac{nq_{S}}{2^{ \ell_{0}-1}}\right)\epsilon-\frac{1}{3\cdot 2^{\ell-1}} \tag{3}\]  
Proof. : We assume \(\mathcal{C}\) is given a factorization instance \(N\) for a product of unknown \(p\) and \(q\), and obtain the result of \(p\) or \(q\) with a non-negligible probability. \(\mathcal{C}\) plays with \(\mathcal{A}\) as follows. Firstly, \(\mathcal{C}\) selects \(a\in\mathbb{Z}_{N}^{*}\), such as a non-cubic residue and a secure parameter \(\ell\geqslant 160\) (the length of \(\ell\) has been discussed and suggested in [22]), and sends \((N,a,\ell)\) to \(\mathcal{A}\) as \(mpk\). \(\mathcal{C}\) manages several lists: one signature list and three hash lists. Then, \(\mathcal{C}\) starts to answer according to \(\mathcal{A}\)'s queries, as follows. * \(h_{1}\)**-Query**\((ID)\): \(\mathcal{C}\) manages a list \((ID,h_{1},s,c_{ID,1},c_{ID,2})\). When \(\mathcal{A}\) requests the identity \(ID\), \(\mathcal{C}\) answers as \(h_{1}\). \((c_{ID,1},c_{ID,2})\in\{0,1\}^{2}\) in two bits and \(s\in\mathbb{Z}_{N}^{*}\) is used as a secret key. When \(\mathcal{A}\) asks on \(ID\), \(\mathcal{C}\) answers \(h_{1}\) if \(ID\) has existed in the \(h_{1}\)-list. Otherwise, \(\mathcal{C}\) randomly selects \(s\in\mathbb{Z}_{N}^{*}\) and \((c_{ID,1},c_{ID,2})\in\{0,1\}^{2}\), calculates \[h_{1}\equiv\frac{s^{3^{\ell}}}{(-1)^{c_{ID,2}}\cdot(a)^{c_{ID,1}}}\pmod{N}\] (4) and returns the answer \(h_{1}\) to \(\mathcal{A}\), adding \((ID,h_{1},s,c_{ID,1},c_{ID,2})\) to the \(h_{1}\)-list. * \(h_{2}\)**-Query**\((R)\): \(\mathcal{C}\) manages a list \((R,h_{2})\). When \(\mathcal{A}\) asks on \(R\), \(\mathcal{C}\) answers \(h_{2}\) if \(R\) has existed in the \(h_{2}\)-list. Otherwise, \(\mathcal{C}\) randomly selects \(h_{2}\in\{0,1\}^{\ell_{0}}\), adds \((R,h_{2})\) into the \(h_{2}\)-list and returns \(h_{2}\). * \(h_{3}\)**-Query**\((R,m,IDSet)\): \(\mathcal{C}\) manages a list \((R,m,IDSet,h_{3})\). When \(\mathcal{A}\) asks on \((R,m,IDSet)\), \(\mathcal{C}\) returns \(h_{3}\) if \((R,m,IDSet)\) has existed in the \(h_{3}\)-list. Otherwise, \(\mathcal{C}\) randomly selects \(h_{3}\in\mathbb{Z}_{N}^{*}\), returns \(h_{3}\), and adds \((R,m,IDSet,h_{3})\) to the \(h_{3}\)-list. * **Extraction query**\((ID)\): \(\mathcal{C}\) executes an additional \(h_{1}\)-query if \(ID\) does not yet exist in the \(h_{1}\)-list and returns \(s\) and \((c_{ID,1},c_{ID,2})\). * **Multi-signature queries**: \(\mathcal{C}\) checks in the \(h_{1}\)-list for whether \(ID_{1}\) exists. If \(ID_{1}\) is already in the \(h_{1}\)-list, \(\mathcal{C}\) has obtained the private key of \(\mathit{signer}_{1}\) and simulates the game as the real algorithm  
**MSign \((sk_{1},IDSet,m)\)** using the secret key \(sk_{1}=s_{1}\). Otherwise, \(\mathcal{C}\) does not have the private key of \(signer_{1}\) and executes the following steps:  
* \(\mathcal{C}\) plays as \(signer_{1}\), and randomly chooses \(t_{1}\leftarrow\{0,1\}^{\ell_{0}}\), broadcasting \(t_{1}\) to other signers. \(\mathcal{C}\) also waits to receive \(t_{2},t_{3},\cdots,t_{n}\) from others; it randomly selects \(w\leftarrow\{0,1\}^{\ell}\) and \(u_{1}\leftarrow\mathbb{Z}_{N}^{*}\), and calculates \[R_{1}=u_{1}^{3^{\ell}}\left((-1)^{\varepsilon_{ID_{1}2}}\cdot a^{\varepsilon_ {ID_{1}1}}\cdot h_{1}(ID_{1})\right)^{-w}\] (5) If \(R_{1}\) already exists in the \(h_{2}\)-list, \(\mathcal{C}\) stops. Otherwise, \(\mathcal{C}\) sets \((R_{1},t_{1})\) in the \(h_{2}\)-list.