## 4 Scheme Construction  
In the proposed GS-MR scheme, each group member has a fixed length of identity information \(\textbf{ID}=(d_{1},d_{2},...,d_{l})\in\{0,1\}^{l}\). The parameters of GS-MR are as follows: Let \(\lambda\) be the security parameter, and \(N\) be the maximum group members. Specifically, let Gaussian parameters \(\sigma_{1}=poly(n)\) and \(\sigma_{2}=nm\omega(\log^{2}m)\log q\) and modulus \(q\geq\beta\omega(n\log n)\) be prime, where \(\beta=poly(n)\) and \(m>\log q/\log(2\sigma_{1}\sqrt{2n})\). The noise boundary of \(RLWE_{n,m,d,\chi}\) is set to an integer \(b\) and satisfies \(b=\widetilde{O}(n^{5/4})\) and \(q/b=\widetilde{\ell}\widetilde{O}(n)\). Choose four hash functions: \(H_{1}:\mathbb{Z}_{q}^{n}\rightarrow\{0,1\}^{l_{1}+_{2}},H_{2}:\{0,1\}^{*} \rightarrow\{v\in\{-1,0,1\}^{m},||v||\leq t\}\), \(F_{1}:\{0,1\}^{l_{2}}\rightarrow\{0,1\}^{l_{1}}\) and \(F_{2}:\{0,1\}^{l_{1}}\rightarrow\{0,1\}^{l_{2}}\) to be modeled as random oracles. The GS-MR scheme we proposed is as follows:  
\(KeyGen(1^{\lambda},1^{N}):\) given \(\lambda\) and \(N\), the group manager performs Algorithm 1. ```
1:\((\textbf{a},\textbf{T}_{\textbf{a}})\gets TrapGen_{\mathcal{R}_{q}}(n,m,q)\)
2:Randomly choose \(\textbf{a}_{0},\textbf{a}_{1}\ldots\textbf{a}_{l}\leftarrow\mathcal{R}_{q}^{m \times m}\)
3:forall\(1\leq i\leq N\)do
4:\(\textbf{D}_{i}=\textbf{a}\cdot\left(\sum_{j=1}^{l}d_{j}\textbf{a}_{j}\right)^ {-1}\)
5:\(\textbf{T}_{\textbf{D}_{i}}\leftarrow\mathit{BasisDel}(Rot(\textbf{a}),\sum_{j =1}^{l}Rot(\textbf{a}_{j})d_{j},\textbf{T}_{\textbf{a}},\sigma_{2})\)
6:\(\textbf{e}_{i}\leftarrow\mathit{SamplePre}_{\mathcal{R}_{q}}(\textbf{D}_{i}, \textbf{T}_{\textbf{D}_{i}},u,\sigma_{2})\), such that \(\textbf{D}_{i}\textbf{e}_{i}=u\mathrm{mod}q\)
7:\(\mathrm{gsk}_{i}=\textbf{e}_{i}\)
8:endfor
9:Randomly choose \(u\leftarrow\mathcal{R}\), \(f\leftarrow\mathcal{R}_{q}\), \(s\leftarrow\chi\), \(e\leftarrow\chi\)
10:Calculate \(g=(f\otimes s+e)\mathrm{mod}q\)
11:Output : \(\mathit{gpk}=[\textbf{a},\textbf{a}_{0},\textbf{a}_{1}...\textbf{a}_{l},u,f,g]\), \(\mathit{gtk}=s,\mathit{gsk}=\{\textbf{e}_{i}\}_{i=1}^{N}\)
```  
**Algorithm 1**\(KeyGen(1^{\lambda},1^{N})\)  
\(Sign(\mathit{gpk},M,\mathit{gsk}_{\pi},\{\textbf{ID}_{i}\}_{i=1}^{N}):\) given \(\mathit{gpk}\), message \(M\in\{0,1\}^{l_{2}}\), signing key \(\mathit{gsk}_{i}=\textbf{e}_{i}\) and a group member's identity set \(\{\textbf{ID}_{i}\}_{i=1}^{N}\), the signer runs Algorithm 2. Figure 2: The definitions for the anonymity game and traceability game. ```
1:for all\(1\leq i\leq N\)do
2:\(y_{i}\gets D_{\sigma_{1}}^{m}\)
3: Calculate \(\mathbf{D}_{i}=\mathbf{a}\cdot\left(\sum_{j=1}^{l}d_{j}\mathbf{a}_{j}\right)^{-1}\)
4:endfor
5: Calculate \(\alpha=H(\sum_{j=1}^{N}\mathbf{D}_{j}y_{j})\)
6: Calculate \(M^{\prime}=F_{1}(M)||(F_{2}(F_{1}(M))\oplus M)\)
7: Calculate \(r=M^{\prime}\oplus\alpha\)
8: Expand \(\mathbf{ID}_{\pi}\) to \(\mathbf{\bar{D}}_{\pi}=(0^{n-l}||\mathbf{ID})\in\{0,1\}^{n}\)
9:\(ID_{\pi}^{\prime}=\tau^{-1}(\mathbf{\bar{D}}_{\pi})\in\mathcal{R}\)
10: Randomly choose \(w+\chi_{\varepsilon}v_{1},e_{2}\leftarrow\chi\)
11: Calculate \((c_{1}=f\otimes w+e_{1},c_{2}=g\otimes w+e_{2}+[q/2]ID_{i}^{\prime})\in\mathcal{ R}_{q}^{2}\)
12:\(\triangleright\)\(=H_{2}(r,c_{1},c_{2})\)
13:for all\(1\leq i\leq N\)do
14:if\(i\
eq\pi\), then \(\mathbf{z}_{i}=\mathbf{y}_{i}\)
15:else calculate \(\mathbf{z}_{i}=\mathbf{e}\mathbf{v}+\mathbf{y}_{i}\), and outputs \((\mathbf{z}_{i},r)\) with probability \(\min(1,D_{\sigma_{1}}^{m}(\mathbf{z}_{i})/\,MD_{\sigma_{1}\sigma_{1}}^{m}(\mathbf{z}_ {i}))\).