## 4 Concrete Construction of IBMS\({}^{\mathbf{CR}\)-1  
### Construction  
Inspired by the previous work [6; 22; 23], we propose a concrete identity-based multi-signature scheme (\(\mathbf{IBMSC}\)**-1**) with three-round interactive communications among the marine sensors and the generation of a single multi-signature as an authenticated tag.  
* \(\mathtt{Setup}\)\((k,\ell)\): The key generator center inputs security parameters \(k\) and \(\ell\), and then:
* 1. Chooses two random primes \(p\) and \(q\), such that \(p\equiv q\equiv 1\pmod{3}\) and \((p-1)(q-1)/9\equiv-1\pmod{3}\). Without loss of generality, we assume that \((p-1)/3\equiv-1\pmod{3}\),
* 2. Chooses two random primes \(\pi_{1}\) and \(\pi_{2}\) from the Eisenstein ring \(\mathbb{Z}[\omega]\), \(s.t.\) the norms satisfy \(N(\pi_{1})=p\) and \(N(\pi_{2})=q\).
* 3. Computes \(N=p*q\). We let \(A+B\omega=\pi_{1}\pi_{2}\), \(A,B\in\mathbb{Z}\), and then compute \(C=-AB^{-1}\pmod{N}\). Note that \(\left(\frac{C}{p}\right)_{3}=\omega^{2}\), and \(\left(\frac{C}{q}\right)_{3}=\omega\).
* 4. Chooses a random number \(a\in\mathbb{Z}_{N}^{*}\) such that \(\left(\frac{a}{N}\right)_{3}=\omega\).
* 5. Computes \(d=\frac{1}{3}[\frac{1}{9}(p-1)(q-1)+1]\).  
6.  Selects three hash functions \(h_{1}(\cdot)\), \(h_{2}(\cdot)\), and \(h_{3}(\cdot)\) such that \(h_{1}(\cdot):\{0,1\}^{*}\rightarrow\mathbb{Z}_{N}^{*}\), \(h_{2}\) and \(h_{3}(\cdot):\{0,1\}^{*}\rightarrow\{0,1\}^{\ell}\). As a result of the step **Setup**, the master secret key is \(msk=(p,q,d)\), which is securely stored, and the public parameter is \(mpk=(N,h_{1},h_{2},h_{3},a,C,\ell)\).
7. \(\bullet\) Extra \((mpk,msk,ID)\): **KGC** inputs the identity \(ID\), computes the hash value of \(ID\) as \(h_{1}(ID)\) and obtains a first symbol \(c_{ID,1}\) such that \[c_{ID,1}=\left\{\begin{array}{ll}0,&\text{ if }\left(\frac{h_{1}(ID)}{N} \right)_{3}=1\\ 1,&\text{ if }\left(\frac{h_{1}(ID)}{N}\right)_{3}=\omega^{2}\\ 2,&\text{ if }\left(\frac{h_{1}(ID)}{N}\right)_{3}=\omega\end{array}\right.\] We let \(h=a^{c_{ID,1}}\cdot h_{1}(ID)\) and we have \(\left(\frac{h}{N}\right)_{3}=1\). Following this, **KGC** computes a second symbol \(c_{ID,2}\) such that \[c_{ID,2}=\left\{\begin{array}{ll}0,&\text{ if }\left(\frac{h}{p}\right)_{3}= \left(\frac{h}{q}\right)_{3}=1\\ 1,&\text{ if }\left(\frac{h}{p}\right)_{3}=\omega,\left(\frac{h}{q}\right)_{3}= \omega^{2}\\ 2,&\text{ if }\left(\frac{h}{p}\right)_{3}=\omega^{2},\left(\frac{h}{q}\right)_{3}= \omega\end{array}\right.\] We let \(I_{ID}=C^{c_{ID,2}}\cdot a^{c_{ID,1}}\cdot h_{1}(ID)\). It is easy to find that \(I_{ID}\in\mathbb{C}\mathbb{R}_{N}\), as \(\left(\frac{I_{ID}}{p}\right)_{3}=\left(\frac{I_{ID}}{q}\right)_{3}=1\). Finally, **KGC** extracts the private key \(sk_{ID}\) as a \(3^{\ell}\)-th root of \(I_{ID}\): \[sk_{ID}\equiv I_{ID}^{d^{\ell}}\left(\text{mod }N\right)\] (1)  
**KGC** sends \(sk_{ID}\) as well as \((c_{ID,1},c_{ID,2})\) to signer \({}_{ID}\) secretly. Note that \(I_{ID}\equiv sk_{ID}^{3^{\ell}}\pmod{N}\). Following this, we denote \(\widetilde{ID}=\{ID,c_{ID,1},c_{ID,2}\}\).
7. \(\bullet\) Sign and verify: These two algorithms can be derived from [23].
8. \(\bullet\) MSign \((mpk,sk_{1},m,IDSet)\): For simplicity, **IBMSCR-1** is described from the \(MS_{1}\)'s point of view. Given the \(MS_{1}\)'s private key \(sk_{1}\), the message \(m\) and the identity set \(IDSet=\{\widetilde{ID_{1}},\widetilde{ID_{2}},...,\widetilde{ID_{n}}\}\), \(MS_{1}\) executes the following algorithm from Algorithm 1. **MSign** generates \(m\sigma=(w,u)\) as the multi-signature.
9. \(\bullet\) MVerify \((mpk,IDSet,m,m\sigma)\). The algorithm verifies by the following three steps. 1. For \(i=1,2,...,n\), it computes \(I_{i}\equiv C^{c_{ID,2}}\cdot a^{c_{ID,1}}\cdot h_{1}(ID_{i})\pmod{N}\). 2. It computes \(\hat{R}\equiv u^{3^{\ell}}\left(\prod_{i=1}^{n}I_{i}\right)^{-w}\pmod{N}\). 3. It checks whether \[w=h_{3}(\hat{R}\|IDSSet\|m)\] (2) is satisfied. If Equation (2) is satisfied, **MVerify** returns 1. This means \(m\sigma\) is valid. Otherwise **MVerify** returns 0.