## 5 Concrete Construction of IBMS\({}^{\bf CR}\)-2
### Construction  
* **Setup**\((k,\ell)\): Given the security parameters, **Setup** can be executed as follows. 1. **KGC** chooses random primes \(p\) and \(q\) where \(p\equiv 2\pmod{3}\) and \(q\equiv 4\) or \(7\pmod{9}\), and calculates the product \(N=p\cdot q\). 2. A non-cubic residue \(a\) is selected such that \(\left(\frac{a}{q}\right)=-1\). 3. Several computational parameters are computed: \[\begin{array}{rcl}\eta&=&[q-1\pmod{9}]/3\\ \lambda&=&\eta\pmod{2}+1\\ \beta&=&(q-1)/3\\ \xi&=&a^{\eta\beta}\pmod{q}\end{array}\] (4) Three hash functions \(h_{1},h_{2}\) and \(h_{3}\) are picked up, where \(h_{1}\):\(\{0,1\}^{*}\to Z_{N}^{*}\), \(h_{2},h_{3}\):\(\{0,1\}^{*}\to\{0,1\}^{\ell}\). Finally, the algorithm **Setup** outputs \(\mathit{msk}=(p,q,\beta)\) and \(\mathit{mpk}=(N,h_{1},h_{2},h_{3},a,\eta,\lambda)\). **KGC** keeps _msk_ secretly.
* **Extra**\((\mathit{mpk},\mathit{msk},\mathit{1D})\): **KGC** computes \(\mathit{sk}\) as follows:1. **KGC** computes \(\omega=h_{1}(ID)^{\lambda\beta}\pmod{q}\) and set sa symbol \(c_{ID}\) according to \(\omega\) and \(\xi\): \[c_{ID}=\left\{\begin{array}{ll}0,&\text{if }\omega=1\\ 1,&\text{if }\omega=\xi\\ 2,&\text{if }\omega=\xi^{2}\end{array}\right.\] **KGC** denotes \(I=a^{c_{ID}}\cdot h_{1}(ID)\pmod{N}\). 2. **KGC** calculates \[sk=I^{\frac{2^{\beta}(p-1)(q-1)-3}{q}}\pmod{N}\] (12) and securely distributes \(sk\) to the signer. We have \(sk_{i}^{3}\cdot I_{i}\equiv 1\pmod{N}\). Following this, we denote the identity by \(\widetilde{ID_{i}}=\{ID_{i},c_{ID_{i}}\}\).
* **Sign** and **verify**: These two algorithms can be derived from [29].
* **MSign**\((mpk,sk_{1},m,IDSet)\): Given the \(M\mathsf{S}_{1}\)'s private key \(sk_{1}\), the message \(m\) and the identity set \(IDSet=\{\widetilde{ID_{1}},\widetilde{ID_{2}},...,\widetilde{ID_{n}}\}\), \(M\mathsf{S}_{1}\) executes the following algorithm in Algorithm 2. **MSign** generates the multi-signature \(m\sigma=(w,u)\).
* **MVerify**\((mpk,IDSet,m,m\sigma)\). The algorithm verifies by the following three steps: 1. For \(i=1,2,...,n\), it computes \(I_{i}=a^{c_{ID_{i}}}\cdot h_{1}(ID_{i})\). 2. It computes \(\hat{R}=u^{3}\cdot\left(\prod_{i=1}^{n}I_{i}\right)^{up}\pmod{N}\). 3. It checks whether \[w=h_{3}(\hat{R}\|IDSet\|m)\] (13) is satisfied. If Equation (13) is satisfied, **MVerify** returns 1. This means \(m\sigma\) is valid. Otherwise **MVerify** returns 0. **Algorithm 2**: The MSign algorithm in **IBMSCR-2**. **Input**: the master public key \(mpk\), the private key \(sk\), the identity set \(IDSet\), the message to be signed \(m\); **Output**: a multi-signature \(m\sigma\). 1. Each \(MS_{i}\) randomly selects \(r_{i}\in\mathbb{Z}_{N}^{*}\) and calculates \(R_{i}=r_{i}^{3}\pmod{N}\) and \(t_{i}=h_{2}(R_{i})\). 2. Each \(MS_{i}\) broadcasts \(t_{i}\) to co-signers \(MS_{j}\) (\(j\
eq i\)). 3. After obtaining \(t_{i}\) from \(MS_{i}\), \(MS_{1}\) broadcasts \(R_{1}\) to other \(MS_{i}\). 4. After receiving \(R_{i}\) from other signers, \(MS_{1}\) checks whether \(t_{i}=h_{2}(R_{i})\) for \(2\leqslant i\leqslant n\) is satisfied. 5. If one of these fails, the algorithm stops, which means the attackers have mixed invalid partial signatures. Otherwise, \(MS_{1}\) sets \(R=\prod_{i=1}^{n}R_{i}\pmod{N}\), \(w=h_{3}(R\|IDSet\|m)\), and \(u_{1}=r_{1}\cdot sk_{1}^{up}\pmod{N}\). 6. \(S_{1}\) broadcasts \(u_{1}\) to other \(MS_{i}\). 7. After receiving \(u_{i}\) from \(MS_{i}\), \(MS_{1}\) aggregates these by \(u=\prod_{i=1}^{n}u_{i}\pmod{N}\). 8. Each \(MS_{i}\) locally generates a multi-signature \(m\sigma=(w,u)\). **Return**\(m\sigma\);