## 4 Scheme Construction
Opening query: \(\mathcal{A}\) makes an opening query on a signature \(SIG\), \(\mathcal{S}\) calls the algorithm \(Open(gpk,SIG,gtk)\) to output a member identity \(ID_{i}\), and returns the member's identity \(ID_{i}\) to \(\mathcal{A}\); otherwise, it returns to \(\bot\). \(\mathcal{A}\) selects two indexes \(i_{0},i_{1}\in[N]\) with \(i_{0}\
eq i_{1}\) and a message \(M\), and sends them to \(\mathcal{S}\). Then, \(\mathcal{S}\) calls the signature algorithm \(Sign(PK,M,gsk_{i_{0}},\{ID_{i}\}_{i=1}^{N})\) and sends the signature \(SIG=(\Pi,(c_{1},c_{2}),r)\) to \(\mathcal{A}\). \(G_{0}^{\prime}:\)\(G_{0}^{\prime}\) was modified from \(G_{0}\) When calling the algorithm \(Sign(gpk,M,gsk_{i_{0}},\{ID_{i}\}_{i=1}^{N})\) to generate a signature, calculate \(\mathbf{z}_{i_{0}}=\mathbf{e}_{i_{0}}\mathbf{v}+\mathbf{y}_{i_{0}}\) and \(\mathbf{z}_{i_{1}}=\mathbf{e}_{i_{1}}\mathbf{v}+\mathbf{y}_{i_{1}}\) in addition to the remaining steps in the signature generation process (calculate the values of \(j\
otin\{i_{0},i_{1}\}\) and \(\mathbf{z}_{i}\) according to the scheme described above). \(G_{1}:\)\(G_{1}\) is identical to \(G_{0}\) with the exception that \(\mathcal{S}\) chooses \(b=1\) rather than \(b=0\). \(G_{1}^{\prime}:\)\(G_{1}^{\prime}\) is identical to \(G_{0}^{\prime}\). \(\square\)

**Lemma 6**. : \(G_{0}\) _and \(G_{0}^{\prime}\) are computationally indistinguishable._

**Proof of Lemma 6. ** In the \(G_{0}\) and \(G_{0}^{\prime}\) games, the difference in signatures lies in the calculation of \(\mathbf{z}_{i_{1}}\). According to Lemma 2, the value \(\mathbf{z}_{i_{1}}\) produced via rejection sampling in \(G_{0}^{\prime}\) is statistically equivalent to the value produced by the Gaussian distribution \(D_{\sigma_{1}}^{m}\) (statistical distance less than \(2^{-\omega(\log m)}/M\)). In \(G_{0}\), the value of \(\mathbf{z}_{i_{1}}\) is taken from the Gaussian distribution \(D_{\sigma_{1}}^{m}\) and so the games \(G_{0}\) and \(G_{0}^{\prime}\) are computationally indistinguishable. \(\square\)

**Lemma 7**. : \(G_{1}\) _and \(G_{1}^{\prime}\) are computationally indistinguishable._

**Proof of Lemma 7. ** The indistinguishability of computation between \(G_{1}\) and \(G_{1}^{\prime}\) (where \(b=1\) in the context of the GAME I model) is proved in the same way as described above. \(\square\)

**Lemma 8**. : _If the \(RLWE_{n,m,q,\beta}\) problem is hard, \(G_{0}^{\prime}\) and \(G_{1}^{\prime}\) are computationally indistinguishable._

**Proof of Lemma 8. ** Games \(G_{1}^{\prime}\) and \(G_{0}^{\prime}\) are similar, except for the computation of the part containing member information \(c_{2}\) in the signature (which includes the identity of the member \(i_{1}\)). Therefore, it is only necessary to prove that the signature \(SIG^{\prime}=(\Pi^{\prime},(c_{1}^{\prime},c_{2}^{\prime}),r^{\prime})\) generated in \(G_{0}^{\prime}\) and the signature \(SIG*=(\Pi*,(c_{1}^{*},c_{2}^{*}),r*)\) in \(G_{1}^{\prime}\) are indistinguishable in computation. The \(c_{2}^{\prime}\) and \(c_{2}^{*}\) can be seen as the LPR encryption of different member identities (\(i_{0}\) and \(i_{1}\)) according to the LPR encryption scheme [26], which is indistinguishable (satisfies IND-CCA security) under the \(RLWE_{n,m,q,\beta}\) assumption. Therefore, for an adversary \(\mathcal{A}\), \(c_{2}^{\prime}\) and \(c_{2}^{*}\) are indistinguishable in computation. Combined with the above proof, \(SIG^{\prime}=(\Pi^{\prime},(c_{1}^{\prime},c_{2}^{\prime}),r^{\prime})\) and \(SIG*=(\Pi*,(c_{1}^{*},c_{2}^{*}),r*)\) are statistically indistinguishable. Therefore, \(G_{0}^{\prime}\) and \(G_{1}^{\prime}\) are indistinguishable in computation. \(\square\)

In conclusion, \(G_{0},\ G_{0}^{\prime},\ G_{1},\ G_{1}^{\prime}\) are statistically indistinguishable. Therefore, for any adversary \(\mathcal{A}\), when facing GAME I defined at the beginning of this paper, the advantage of winning the game is \(Adv=|\Pr[b^{\prime}=b]-1/2|+negl(n)\), indicating that \(\mathcal{A}\) has no advantage in winning the anonymity game.