## 4 Scheme Construction
Since the signature is valid, it follows that \(\mathbf{v}^{*}=H_{2}(\sum_{i=1}^{N}\mathbf{D}_{i}\mathbf{z}_{i}-uv^{*},c_{1},c_{2})\); Furthermore, since the signature \(SIG\) forged by \(\mathcal{A}\) can satisfy the verification correctness, we have \(\mathbf{v}^{*}=H_{2}(\sum_{i=1}^{N}\mathbf{D}_{i}\mathbf{z}_{i},c_{1}^{*},c_{2}^{*})\). As the collision probability of the hash-oracle is negligible, we can see that \(c_{1}=c_{1}^{*}\) and \(c_{2}=c_{2}^{*}\), and therefore we can conclude that \[\sum_{i=1}^{N}\mathbf{D}_{i}(\mathbf{z}_{i}-\mathbf{z}_{i}^{*})=\mathbf{0}\text{mod}q,\] (9) since \(\sum_{i=1}^{N}||\mathbf{z}_{i}-\mathbf{z}_{i}^{*}||\leq b\), it follows that \(\sum_{i=1}^{N}\left(\mathbf{z}_{i}-\mathbf{z}_{i}^{*}\right)\) is a solution to the \(RSIS_{n,m,\alpha,\beta}\) problem. 2. Assuming \(Open(gpk,SIG^{*},gtk)=\bot\), the forged signature \(SIG^{*}=(\Gamma^{*},(c_{1}^{*},c_{2}^{*}),r^{*})\) produced by the adversary \(\mathcal{A}\) satisfies the following condition \[\mathbf{ID}_{k}^{*}\
otin\{\mathbf{ID}_{i}\}_{i=1}^{N}\text{ i.e., }\mathbf{D}_{k}=\mathbf{a}\cdot\left(\sum_{i=1}^{l}d_{i(k)}\mathbf{a}_{i}\right)^{-1} \
eq\mathbf{a}\cdot\left(\sum_{i=1}^{l}d_{i(k)}^{*}\mathbf{a}_{i}\right)^{-1}=\mathbf{D}_{ k}^{*}.\] (10)Since the above condition can be verified by the algorithm \(Verify(gpk,SIG,\{ID_{i}\}_{i=1}^{N})\), we have

\[\sum_{i=1}^{N}\mathbf{D}_{i}\mathbf{z}_{i}^{*}-u\mathbf{v}^{*}=\sum_{i=1}^{N}\mathbf{D}_{i}\mathbf{y }_{i}^{*}\ i.e.\ \mathbf{D}_{k}^{*}\mathbf{z}_{k}^{*}-u\mathbf{v}^{*}=\mathbf{D}_{k}^{*}\mathbf{y}_{k}^{*}. \tag{11}\]

Let

\[\mathbf{D}_{k}^{*}\mathbf{z}_{k}-u\mathbf{v}^{*}=\mathbf{D}_{k}^{*}(\mathbf{e}_{k}\mathbf{v}^{*}+\mathbf{y} _{k}^{*})-u\mathbf{v}^{*}=\mathbf{D}_{k}^{*}\mathbf{y}_{k}^{*}. \tag{12}\]

From Equations (11) and (12), we can obtain

\[\mathbf{D}_{k}^{*}((\mathbf{e}_{i}^{*}-\mathbf{e}_{i})\mathbf{v}^{*})=\mathbf{0}\text{mod}q. \tag{13}\]

Since \(||(\mathbf{e}_{i}^{*}-\mathbf{e}_{i})\mathbf{v}^{*}||_{\infty}\leq 4\sigma_{1}t\sqrt{m}\), \((\mathbf{e}_{i}^{*}-\mathbf{e}_{i})\mathbf{v}^{*}\) is a solution to the \(RSI_{n,m,q,\beta}\) problem. Based on the proof of the two above cases, if the adversary \(\mathcal{A}\) wins GAME II, then the challenger \(\mathcal{S}\) will obtain a solution to the \(RSI_{n,m,q,\beta}\) problem. However, the \(RSI_{n,m,q,\beta}\) problem is to solvedifficult under the parameters provided in this paper, and so \(\mathcal{A}\) cannot satisfy the two conditions mentioned above. Therefore, the GS-MR scheme has full traceability. ## 6 Implementation and Efficiency Analysis

As proof of concept, in order to understand the practicality of group signatures with recoverable messages, we simply performed some implementations of the GS-MR scheme. We have shown implementations of the GS-MR, which were experimented with using an AMD Ryzen 5 5600G @ 3.90 GHz CPU with 16 GB of RAM. The programs were compiled using SageMath and Python 3.8. A selection of some program parameters were first shown. Then, based on these parameters, some corresponding outputs in the GS-MR scheme were experimentally derived. In Table 1, we summarize the theoretical estimates of the key size and signature size of GS-MR, where \"\(n\cdot S\) denotes \(n\) elements in a set \(S\)\". We followed the parameter settings of [PERSON] et al. [37] and also considered the security of the parameter settings in this paper. * To keep \((\mathbf{a},\mathbf{T}_{\mathbf{a}})\gets TrapGen_{\mathcal{R}_{q}}(n,m,q)\) working safely, set \(q\geq 2\), \(m\geq 1\), and \(\overline{m}\geq\)log \(q/\log(2\sigma_{1}\sqrt{2n})\). * For the Gaussian parameter in \(BasisDel(\mathbf{A},\mathbf{R},\mathbf{T}_{\mathbf{A}},\sigma)\), we chose \(\sigma_{R}=\sqrt{n\log q}\omega\) (\(\sqrt{\log m}\)), and according to [PERSON] [38], let \(\sigma_{2}\geq||\mathbf{T}_{\mathbf{A}}||\cdot(\sigma_{\text{R}}\sqrt{m}\cdot\omega( \log^{3/2}m))\). * For Gaussian parameters in rejection sampling, we chose \(\sigma_{1}=\omega(t\sqrt{\log m})\approx 12\cdot t\cdot\sqrt{nm}\).