## 4 Scheme Construction
It can be inferred that the GS-MR scheme satisfies the anonymity requirement. **Theorem 3** (full traceability). : _The GS-MR scheme meets full traceability under ROM if the \(RSIS_{n,m,\beta,\beta}\) problem is hard._

Proof of Theorem 3.: When proving the traceability of the GS-MR scheme, there are two key components: (1) The algorithm \(Sign\) generates legal signatures that can be traced back to the identities of their signers. (2) No adversary can forge a legal and untraceable group signature. First, as shown in Theorem 1, the GS-MR scheme is proven to correctly open any valid signature and query the identity details of the signer. Therefore, the following proof focuses on the second point, namely, that it is impossible for any PPT adversary to successfully construct a legally and untraceable signature. \(\square\)

Let \(\mathcal{A}\) be any PPT algorithm defined in Definition 6 that can forge a signature with a non-negligible advantage after numerous inquiries. Then, a challenger \(\mathcal{S}\) can be built to solve the \(RSIS_{n,m,\beta,\beta}\) problem with a non-negligible advantage. Let the challenger \(\mathcal{S}\) maintain three lists \(l_{1},l_{2},C,\Gamma\), and initialize them as empty. Then, \(\mathcal{S}\) honestly runs the algorithm \(KeyGen(\mathcal{1}^{\lambda},1^{N})\) of the scheme, with input security parameter \(\lambda\) and maximum member group \(\{\mathbf{ID}_{i}\}_{i=1}^{N}\), randomly selects \(j\in\{1,2,\ldots,N\}\), generates \(gpk\), \(gsk_{j}\), \(gtk\), and then sends \(gpk\) and \(gtk\) to \(\mathcal{A}\). In response to \(\mathcal{A}\)'s inquiry, \(\mathcal{S}\) replied as follows (\(\mathcal{A}\) had conducted relevant \(H_{1}\) queries and \(H_{2}\) queries prior to performing signing and corrupt queries):

1. \(H_{1}\) query. \(\mathcal{A}\) selects N polynomial vectors \(\mathbf{y}_{j}\gets D_{\sigma_{1}}^{m}\) to \(\mathcal{S}\). \(\mathcal{S}\) first checks list \(L_{1}\). If \(\mathcal{A}\) has previously submitted the same query, \(\mathcal{S}\) directly returns the same query result. Otherwise, \(\mathcal{S}\) selects a random vector \(\alpha\in\{-1,0,1\}^{l_{1}+l_{2}}\) and returns it to \(\mathcal{A}\). For this query, \(\mathcal{S}\) records \((\{\mathbf{y}_{i}\}_{i=1}^{N},\alpha)\) in the list \(L_{1}\). 2. \(H_{2}\) query. \(\mathcal{A}\) selects a message \(M\), and \(c_{1},\ c_{2}\), and submits them to \(\mathcal{S}\). \(\mathcal{S}\) first checks list \(L_{2}\). If \(\mathcal{A}\) has previously submitted the same query, \(\mathcal{S}\) directly returns the same query result. Otherwise, \(\mathcal{S}\) selects a random vector \(\mathbf{v}\in\{-1,0,1\}^{m}\) and returns it to \(\mathcal{A}\). For this query, \(\mathcal{S}\) records \((M,\mathbf{v},c_{1},c_{2})\) in the list \(L_{2}\). 3. Corrupt query. \(\mathcal{A}\) inputs \(k\in[N]\), if \(k=j\), \(\mathcal{S}\) terminates the game; if \(k\
eq j\), \(\mathcal{S}\) sends the signing key \(gsk_{k}\) to \(\mathcal{A}\). For this query, \(\mathcal{S}\) records \((k,\mathbf{e}_{k})\) in the list \(C\). 4. Signing query. \(\mathcal{A}\) inputs \(k\in[N]\) and message \(M\), if \(k=j\), \(\mathcal{S}\) will modify \(z_{i}\) in the algorithm \(Sign\) to \(\mathbf{z}_{i}=\mathbf{y}_{i}\), and return the signature \(SIG\) to \(\mathcal{A}\); if \(k\
eq j\), \(\mathcal{S}\) honestly runs the algorithm \(Sign\) and returns the signature \(SIG\) to \(\mathcal{A}\). For this query, \(\mathcal{S}\) records \((k,M)\) in the list \(\Gamma\). After a series of queries, \(\mathcal{A}\) outputs a forged group signature \(SIG^{*}=(\Gamma^{*},(c_{1}^{*},c_{2}^{*}),r^{*})\). If the signature \(SIG^{*}\) satisfies Definition 6, it implies that \(\mathcal{A}\) wins GAME II. We analyzed the following two aspects:

1. Assuming that \(SIG^{*}\) is a valid signature and satisfies \(Open(gpk,SIG^{*},gtk)=j\).