## 4 Scheme Construction
\begin{array}{ll}\sum\limits_{i=1}^{N}\mathbf{D}_{i}\mathbf{z}_{i}-uH_{2}(r,c_{1},c_{ 2})&=\sum\limits_{i\in[N]\setminus\{\pi\}}\mathbf{D}_{i}\mathbf{y}_{i}+\mathbf{D}_{\pi}\mathbf{ z}_{\pi}-uH_{2}(r,c_{1},c_{2}),\\ &=\sum\limits_{i\in[N]\setminus\{\pi\}}\mathbf{D}_{i}\mathbf{y}_{i}+\mathbf{D}_{\pi}(\mathbf{ e}_{\pi}\mathbf{v}+\mathbf{y}_{\pi})-uH_{2}(r,c_{1},c_{2}),\\ &=\sum\limits_{i=1}^{N}\mathbf{D}_{i}\mathbf{y}_{i}+\mathbf{w}-uH_{2}(r,c_{1},c_{2}),\\ &=\sum\limits_{i=1}^{N}\mathbf{D}_{i}\mathbf{y}_{i}.\end{array}  \tag{4}\]

Then, we have

\[M^{\prime}=H_{1}(\sum\
olimits_{i=1}^{N}\mathbf{D}_{i}\mathbf{y}_{i})\oplus r=H_{1}( \sum\
olimits_{i=1}^{N}\mathbf{D}_{i}\mathbf{z}_{i}-uH_{2}(r,c_{1},c_{2}))\oplus r, \tag{5}\]

and since

\[M^{\prime}=F_{1}(M)||(F_{2}(F_{1}(M))\oplus M), \tag{6}\]

we can recover the message

\[M=\left[M^{\prime}\right]_{I_{2}}\oplus F_{2}([M^{\prime}]^{I_{1}}) \tag{7}\]

From it, and the message \(M\) must satisfy \(F_{1}(M)=[M^{\prime}]^{I_{1}}\). On the other hand, when \(i\
eq\pi\) and \(\mathbf{z}_{i}=\mathbf{y}_{i}\), where \(\mathbf{y}_{i}\gets D_{\sigma_{1}}^{m}\), according to Lemma 1, \(||\mathbf{z}_{i}||\in[N]_{/\{\pi\}}\) satisfies \(||\mathbf{z}_{i}||\leq 2\sigma\sqrt{m}\) with overwhelming probability; when \(i=\mathbf{\pi}\), we have \(\mathbf{z}_{i}=\mathbf{e}_{i}\mathbf{v}+\mathbf{y}_{i}\), and where \(\mathbf{y}_{i}\gets D_{\sigma_{1}}^{m}\), according to Lemma 2, \(\mathbf{z}_{i}\) is statistically indistinguishable from Gaussian distribution \(D_{\sigma_{1}}^{m}\). Therefore, for all \(\mathbf{z}_{i}\), \(||\mathbf{z}_{i}||\leq 2\sigma\sqrt{m}\) is established with overwhelming probability. (2) Opening correctness

The correctness of opening depends on the accuracy of the underlying LPR encryption, and the parameter settings described in Section 4. of this paper meet the correctness requirements of the encryption scheme, assuming that \(SIG=(\Pi,(c_{1},c_{2}),r)\) is a signature generated by an honest member \(i\) through the algorithm \(Sign(gpk,M,gsk_{i},\{\mathbf{ID}_{i}\}_{i=1}^{N})\). Regarding the validity of the open algorithm, we show that

\[ \begin{array}{ll}c_{2}-c_{1}s&=g\otimes w+e_{2}+\lfloor q/2\rfloor ID_{i}^{ \prime}-(f\otimes w+e_{1})\otimes s\\ &=(f\otimes s+e)\otimes w+e_{2}+\lfloor q/2\rfloor ID_{i}^{\prime}-(f\otimes w +e_{1})\otimes s\\ &=ew+e_{2}-e_{1}s+\lfloor q/2\rfloor ID_{i}^{\prime},\end{array}  \tag{8}\]

where \(||w||_{\infty},||\mathbf{e}_{1}||_{\infty},||\mathbf{e}_{2}||_{\infty}\leq b\). Note that \(b=\overset{\sim}{O}(n^{5/4})\) and \(q/b=\overset{\sim}{\ell}\overset{\sim}{O}(n)\), it can therefore be concluded that \(||\mathbf{e}w+e_{2}-e_{1}s||_{\infty}\leq 2n\cdot b^{2}+b=\overset{\sim}{O}(n^{3 5})\ll[q/10]\). Next, we determine the value of the \(\mathbf{ID}\) based on the value of each component of \(c_{2}-c_{1}\). The algorithm \(Open(gpk,SIG,gtk)\) then recovereds the \(\mathbf{ID}\) with a probability of 1. \(\Box\)

Theorem 2 (full anonymity): _The GS-MR scheme meets full anonymity under ROM if the \(RLWE_{n,m,d,X}\) problem is hard._

**Proof of Theorem 2. ** Let \(\mathcal{A}\) be any PPT adversary in Definition 1; the following proves that the GS-MR scheme satisfies the anonymity requirement by showing that the four games \(G_{0},\ G_{0}^{\prime},\ G_{1},\ G_{1}^{\prime}\) are indistinguishable. \(G_{0}:\)\(G_{0}\) is denoted as the experiment with \(b=0\) in GAME I. First, the system is set up, and the challenger \(\mathcal{S}\) calls the algorithm \(KeyGen(1^{n},1^{N})\) to generate \(gpk\), \(gtk\), and \(gsk=\{\mathbf{e}_{i}\}_{i=1}^{N}\). Then, \(\mathcal{S}\) sends \(gpk\) and \(gsk=\{\mathbf{e}_{i}\}_{i=1}^{N}\) to \(\mathcal{A}\). \(\mathcal{A}\) is permitted to make the following adaptive queries:

1. Signing query: \(\mathcal{A}\) makes a signing query on an index \(i\) and a message \(M\), and then \(\mathcal{S}\) returns the signature \(SIG=(\Pi,(c_{1},c_{2}),r)\) to \(\mathcal{A}\). 2.