ML-GS: Module Lattice-Based Group Signature Scheme

Group signatures (GS) are a special class of digital signatures designed to provide privacy protection for groups. As a prominent research topic in public-key cryptography, GS has attracted increasing attention in recent years and has been applied in various multi-user scenarios. Any group member can generate a signature on behalf of the entire group. The validity of the signature can be publicly verified, but the identity of the actual signer remains hidden (anonymity). A group manager, equipped with a tracing key, can reveal the identity of the signer when necessary (traceability). Due to these two core properties, group signatures are well-suited for a range of network applications, such as electronic voting, vehicular networks, and anonymous cryptocurrencies [1–3]. Figure 1 illustrates the application of GS in electronic contract signing.

Figure 1.

Group Signature in Electronic Contract Signing

Most existing GS schemes are constructed based on traditional number-theoretic hardness assumptions, such as integer factorization and discrete logarithms. These problems are believed to be intractable for classical computers in polynomial time. However, the introduction of Shor algorithm [4] demonstrated that quantum computers can efficiently solve these problems, posing a significant threat to the cryptographic foundations of the current Internet infrastructure in the post-quantum era. Although the timeline for practical quantum computers remains uncertain, ongoing advances in quantum algorithms [5] suggest that their realization may not be far off. Considering this, the development of quantum-resistant cryptographic schemes has become an urgent and critical area of research.

In response to the disruptive threat that quantum computing poses to traditional cryptographic schemes, the National Institute of Standards and Technology (NIST) has launched a standardization process for post-quantum cryptography. Among the various candidates, lattice-based cryptography has emerged as one of the most promising approaches due to its strong security guarantees and practical efficiency. Since Ajtai's pioneering work in 1996 [6], which first introduced lattice problems into cryptography, subsequent research has shown that current quantum algorithms cannot efficiently solve the underlying hard problems on lattices [7]. In addition to quantum resistance, lattice-based schemes offer several desirable features, including worst-case to average-case reductions, parallelizability, and high computational efficiency. These advantages have made lattice-based group signature schemes a highly active area of research. Although existing lattice-based GS schemes have been proven secure under well-established lattice hardness assumptions, they still suffer from substantial storage overhead and relatively low signing efficiency, which remain key challenges for practical deployment.

In August 2024, NIST officially released the first set of post-quantum cryptographic standards, FIPS 203-205 [8–10], marking a critical milestone in the transition from classical to quantum-resistant cryptographic systems. Among them, FIPS 204 standardizes a lattice-based digital signature scheme known as Dilithium [11]. Dilithium is designed within the “Fiat-Shamir with Aborts” framework, which avoids the complexities of Gaussian sampling and enables a simple, efficient signing process. This construction has provided valuable insights for the design of GS scheme. In particular, by adopting Dilithium’s signature structure for the group member signing phase, it is possible to significantly improve signing speed and reduce signature size.

Based on the above, the motivation for proposing our new group signature scheme is as follows:

• To address the urgent need for quantum-resistant group signatures: The advancement of quantum computing threatens the security of traditional group signature schemes, making the development of post-quantum alternatives a critical research imperative.

• To overcome practical limitations in existing lattice-based group signatures: While lattice-based cryptography offers a promising path to quantum resistance, many current lattice-based group signature schemes are hindered by significant storage overhead and suboptimal signing efficiency, limiting their practical applicability.

• To leverage recent advancements in post-quantum cryptography standards: The Dilithium signature scheme, standardized by NIST in FIPS 204, provides robust and efficient building blocks. We aim to adapt its core principles to the group signature setting to enhance performance and security.

In this paper, we propose a module lattice-based group signature scheme (ML-GS). Our specific contributions are as follows:

To ensure the dynamic joining of group members, we adopt a Gaussian preimage sampling technique over module lattices. The module nature of our construction enables flexible parameter selection to accommodate varying security levels. We also utilize a public matrix to generate identity vectors for each group member. This approach reduces the number of public matrices required for identity verification to just two, thereby significantly minimizing both public and private key sizes. Furthermore, the ML-GS scheme follows a sign-hybrid-encrypt paradigm, with its design centered around the FIPS 204 signature scheme, Dilithium [9]. We employ a dual-Dilithium signature mechanism to enhance efficiency and reduce the overall signature size. This construction guarantees that, when a valid signature is opened, the algorithm cannot reveal the identity of any signer other than the actual one. To ensure correct identity opening, the identity vectors of group members are encrypted using the K-PKE encryption scheme from FIPS 203 [8]. The resulting ciphertext is partially reused to derive randomness in the local signature generation process, while certain components of the local signature are embedded as plaintext in the sign -hybrid-encrypt mechanism.

Additionally, the ML-GS scheme achieves both anonymity and traceability in the Random Oracle Model (ROM), with its security grounded on the Module Learning With Errors (MLWE) and Module Short Integer Solution (MSIS) assumptions. Finally, we compare ML-GS scheme with a GS scheme [12] proposed at Eurocrypt 2022. The results show that our scheme achieves a 6% reduction in public key size and an 80% reduction in signature size, at the cost of a 16% increase in each member’s signing key size.

In 2010, Gordon et al. [13] were the first to introduce a lattice-based GS scheme, constructed using non-interactive zero-knowledge (NIZK) proofs. While theoretically significant, their scheme suffered from impractically large signature sizes. In 2013, Laguillaumie et al. [14] proposed an improved scheme that reduced the signature size to a logarithmic scale relative to the number of group members. In 2015, Ling et al. [15] presented a GS scheme based on ideal lattices, which significantly reduced key and signature sizes by transitioning to a ring-based setting. In 2018, Ling et al. [16] introduced a constant-size GS scheme using the “constrained guessing” technique [17] to address the issue of linearly growing signature sizes. However, this scheme required overly large parameters and suffered from completeness issues in its NIZK component. NIZK remains a foundational technique in many lattice-based GS schemes [18–21]. In 2019, Katsumata et al. [22] proposed a GS scheme in the standard model, eliminating the need for NIZK proofs of group membership during signature verification. In 2024, Tang et al. [23] proposed an event-oriented linkable GS scheme that uses a linking algorithm to detect multiple signatures from the same signer, thereby preventing malicious abuse. In 2025, Zhang et al. [24] creatively combined the Chinese Remainder Theorem and the trapdoor sampling inverse transformation algorithm based on the GKV scheme [13] to design a new lattice-based group signature scheme, which ensures privacy protection for medical data in the medical field. In recent years, a growing number of GS schemes have been proposed and applied across a wide range of scenarios [25–29].

From the development trajectory of lattice-based group signatures outlined above, we can summarize that group signature schemes are typically constructed from multiple cryptographic components: a signature scheme is used to issue private keys to group members, zero-knowledge proofs ensure the anonymity of identities, and a lattice-based encryption scheme guarantees the traceability of signatures. In recent years, the continuous proposal of lattice-based signature schemes [30, 31] has also led to the ongoing optimization of key issuance in group signatures. In ML-GS, we use the [32] scheme to issue private keys to users. Instead of using zero-knowledge proofs to ensure member anonymity, we employ a dual Dilithium signature architecture. Simultaneously, the continuous advancements in lattice-based encryption schemes [33] also ensure the traceability of the ML-GS scheme.

The remainder of this paper is organized as follows: In Section 2, we present the basic notation and relevant algorithms. In Section 3, we introduce the definition and security model of group signatures. In Section 4, we describe the construction of the ML-GS scheme. In Section 5, we provide a security analysis of the ML-GS scheme. In Section 6, we analyze the efficiency of ML-GS and present comparative experiments. Finally, Section 7 concludes the paper.

The notations used in this paper are described in Table 1.

Table 1.

Notations	Description
ZqnZ_q^n	n-dimensional vector over modulo q
Zqn×mZ_q^{n \times m}	n × m matrix over modulo q
R	polynomial Z[[x] / (xd + 1)
Rq	quotient ring Z[q[x] / (xd + 1)
x ← D	x is sampled from the distribution D
∥a∥	∑ ai2\sqrt {\sum {a_i^2} }
∥a∥∞	maxj| aj |\mathop {\max }\limits_j \left| {{a_j}} \right|
∥w∥	∑ ‖ wi ‖2\sqrt {\sum {{{\left\| {{w_i}} \right\|}^2}} } , where w = (w0, …., w)∈ Rk
∥w∥∞	maxj‖ wj ‖∞\mathop {\max }\limits_j {\left\| {{w_j}} \right\|_\infty }, where w = (w0, …., wk) ∈ Rk
⊥	the algorithm outputs fail
negl(λ)	a non-negligible function about λ
B	the set of integers representable by a single byte, i.e., {0,1,…,255}

To issue signing keys to group members, a trapdoor sampling algorithm is used to sample short vectors. In 2021, Bert et al. [32] proposed an efficient preimage sampling technique on module lattices, which exhibits high modularity. Depending on the modularity and specific requirements of different schemes, the operations on R_q can be easily adjusted. Based on this, we introduce two algorithms.

Given a tool vector gT=[ 1bb2…bk−1 ]{g^T} = \left[ {\matrix{ 1 \hfill & b \hfill & {{b^2}} \hfill & \ldots \hfill & {{b^{k - 1}}} \hfill \cr } } \right], where k = log_bq. In the modular setting, we can construct a matrix G=Id⊗gT=[ gTgT⋱gT ]∈Rd×dk,{\bf{G}} = {{\bf{I}}_d} \otimes {{\bf{g}}^T} = \left[ {\matrix{ {{{\bf{g}}^T}} \hfill & {} \hfill & {} \hfill & {} \hfill \cr {} \hfill & {{{\bf{g}}^T}} \hfill & {} \hfill & {} \hfill \cr {} \hfill & {} \hfill & \ddots \hfill & {} \hfill \cr {} \hfill & {} \hfill & {} \hfill & {{{\bf{g}}^T}} \hfill \cr } } \right] \in {{\rm{R}}^{d \times d{k^,}}} and G-lattice Λq⊥(gT)∈Rqdk\Lambda _q^ \bot \left( {{{\bf{g}}^T}} \right) \in {\rm{R}}_q^{dk}. After introducing the G-lattice, we have the following lemma.

The FIPS 203 standard's key encapsulation protocol [8] is centered around an encryption scheme based on the MLWE problem. This standard provides a public-key encryption scheme, K-PKE, that is secure under CPA (Chosen Plaintext Attack). In our design of ML-GS, we will use K-PKE to encrypt group members' identity information, and the encrypted result will serve as a commitment value as part of the signature generation process.

K-PKE consists of three components: K-PKE.KeyGen, K-PKE.Encrypt and K-PKE.Decrypt. Below, we briefly describe these three algorithms according to the requirements of our scheme.

K – PKE.KeyGen(): The algorithm samples two vectors s and e from a binomial distribution and generates a matrix a from a uniform distribution. It computes the public key key ek_PKE = (a,b), where b=NTT−1(a∘s^)^+e{\bf{b}} = {{\mathop{\rm NTT}\nolimits} ^{ - 1}}\widehat {({\bf{a}}\; \circ \;\widehat {\bf{s}})} + {\bf{e}}, the private key dk_PKE = s, and outputs (ek_PKE, dk_PKE).

K – PKE.Encrypt(ek_PKE,m,r): The algorithm takes a public key ek_PKE, a message m, and a random bit seed r, and randomly selects a vector r, e₁, e₂ from a binomial distribution. It then computes, u=NTT−1(a∘r^)^+e1v=NTT−1(b^∘r^)+e2+mu = {{\mathop{\rm NTT}\nolimits} ^{ - 1}}\widehat {({\bf{a}} \circ \widehat {\bf{r}})} + {{\bf{e}}_1}\quad v = {{\mathop{\rm NTT}\nolimits} ^{ - 1}}(\widehat {\bf{b}} \circ \widehat {\bf{r}}) + {{\bf{e}}_2} + m, and outputs the ciphertext ct = (u, v).

K-PKE.Decrypt(dk_PKE, ct): The algorithm takes a private key dk_PKE, a ciphertext ct, computes m=(v−NTT−1(s^∘u^))m = \left( {v - {{{\mathop{\rm NTT}\nolimits} }^{ - 1}}(\hat s \circ \hat u)} \right) and outputs the plaintext m.

In this section, the proposed ML-GS scheme follows the fundamental definition of group signatures introduced by Bellare et al. [37].

Verification correctness: Pr[ 0←ML−GS.Verify(gpk,M,σ)|gpk,gmk,gtk←ML−GS.Setup(1λ)ski←ML−GS.KeyGen(gpk,gmk,i)σ←ML−GS.Sign(gpk,ski,M) ]≤negl(n).\Pr {\mkern 1mu} \left[ {0 \leftarrow {\rm{ML}} - {\rm{GS}}.{\mathop{\rm Verify}\nolimits} (gpk,M,\sigma )\left| {\matrix{ {gpk,gmk,gtk \leftarrow {\rm{ML}} - {\rm{GS}}.{\mathop{\rm Setup}\nolimits} \left( {{1^\lambda }} \right)} \cr {s{k_i} \leftarrow {\rm{ML}} - {\rm{GS}}.{\mathop{\rm Key}\nolimits} {\mathop{\rm Gen}\nolimits} (gpk,gmk,i)} \cr {\sigma \leftarrow {\rm{ML}} - {\rm{GS}}.{\mathop{\rm Sign}\nolimits} \left( {gpk,s{k_i},M} \right)} \cr } } \right.} \right] \le negl(n).

Opening correctness: Pr[ ⊥← ML-GS.Open (gpk,gtk,M,σ,reg)|gpk,gmk,gtk,reg← ML-GS.Setup (1λ)ski← ML-GS.KeyGen (gpk,gmk,i,reg)σ← ML-GS.Sign (gpk,ski,M)1← ML-GS.Verify (gpk,M,σ) ]≤negl(n).\Pr \left[ { \bot \leftarrow {\rm{ ML - GS}}{\rm{.Open }}(gpk,gtk,M,\sigma ,reg)\left| {\matrix{ {gpk,gmk,gtk,reg \leftarrow {\rm{ ML - GS}}{\rm{.Setup }}\left( {{1^\lambda }} \right)} \cr {s{k_i} \leftarrow {\rm{ ML - GS}}{\rm{.KeyGen }}(gpk,gmk,i,reg)} \cr {\sigma \leftarrow {\rm{ ML - GS}}{\rm{.Sign }}\left( {gpk,s{k_i},M} \right)} \cr {1 \leftarrow {\rm{ ML - GS}}{\rm{.Verify }}(gpk,M,\sigma )} \cr } } \right.} \right] \le negl(n).

The group signature scheme should guarantee the message reliability. The ML-GS scheme satisfies the message authentication requirements by ensuring that only legitimate group members can generate valid signatures through the modular lattice assumptions and the FIPS 204 standard signature structure, and that any attempts to forge signatures are equivalent to solving the MLWE/MSIS problem. The validity of a signature can be publicly verified, but only the signer can generate a legitimate signature for the corresponding message (integrity and authenticity are guaranteed).

The security requirements of GS scheme vary depending on different application scenarios. According to the summary by Bellare et al. [37], the two most fundamental security properties of group signatures are anonymity and traceability. Anonymity ensures that the identity of the actual signer is indistinguishable to external observers. ML-GS guarantees that the verification of a valid signature does not reveal the signer’s identity. In our scheme, the identity vector of the group member is concealed during the signing process using K-PKE encryption standardized in FIPS 203. Combined with a dual-Dilithium mechanism and random masking, we construct a "sign-hybrid-encrypt" structure. Traceability allows the group manager to reveal the identity of the signer when necessary, ensuring that the signer cannot deny their signing behavior. Our design guarantees traceability: any attack aiming to break traceability is shown to be as hard as solving the underlying MSIS problem. In our security proof, we demonstrate that, assuming the hardness of MSIS, no adversary can forge a valid signature and falsely attribute it to another group member.

We first introduce three random oracles.

• O_corrupt(i) Given a member's identity i, returns a signing key sk_i.

• _sign(i,M): Given a member's identity i and a message M, returns a signature σ ← ML – GS. Sign(gpk, sk_i, M).

• OP(M, σ): Given a message M and a signature σ, if the signature is the correct signature of the member for the message M, returns the identity i; otherwise, it returns ⊥.

Figure 3.

The Definitions for Anonymity Game

Figure 4.

The Definitions for Traceability Game

The setup algorithm ML-GS.Setup takes the security parameter λ as input. First, it invokes the trapdoor generation algorithm TrapGen to generate a matrix A and its corresponding trapdoor T_A, preparing for the issuance of signing keys to the group members.

The algorithm K-PKE.KeyGen generate an encrypted public-private key pair (ek_PKE, dk_PKE)‥ This step ensures that during the signature generation phase, the signer's identity is correctly encrypted, and during the opening phase, the signer's identity is correctly decrypted using the private key.

A random seed ζ is selected and expanded using an XOF function (such as SHAKE-256, denoted as H in this paper) to generate additional random values. Specifically:

• 1)

  A 64-byte public key random seed ρ. It can be used to randomly sample a polynomial vector u and a polynomial matrix B from ExpandPK algorithm.

• 2)

  A 32-byte private key random seed ρ′‥ It can be used to sample and generate the signing key for the member during the key generation phase.

Finally, the registration list reg is initialized as empty. The setup algorithm is shown in Algorithm 1.

The key generation algorithm ML-GS.KeyGen takes gpk, gmk, the identity i of the member and the registration list reg as inputs. First, the private key random seed ρ'. is expanded into a polynomial vector xi∈Sηk{x_i} \in S_\eta ^k through the ExpandS algorithm, which is taken as part of the member's signing key. Then, calculate the public identity vector g_i = Bx_i, and another part of the signing key, s_i, ‘is output through the trapdoor sampling algorithm Sample(A, T_A, u – g_i, η). Finally, the identity vector g_i is added to the registration list and output member i's signing key gsk_i = (x_i, s_i) The key generation algorithm is shown in Algorithm 2.

The signing algorithm ML-GS.Sign takes gpk, sk_i and M as input. First, the public key random seed ρ is used to expand the public parameters u, B through the ExpandPK algorithm, and then the identity vector g_i is computed. Before signing the message, it is concatenated with seed ρ to produce a 64-byte message representation μ.

Signing algorithm consists of rejection sampling loop and an encryption. The specific steps are as follows:

To obtain the signature, the signing algorithm first encrypts the member's identity vector g_i using the encryption algorithm of K-PKE. It then selects two vectors y₁, y₂ from a Gaussian distribution Dγ1kD_{{\gamma _1}}^k computes the commitment (w₁, w₂), and uses the message representation μ and the ciphertext of g_i to generate challenge values c˜1,c˜2{{\tilde c}_1},{{\tilde c}_2}. Finally, the signature algorithm generates the final challenge value c˜{\tilde c} by combining the ciphertext value of c˜1{{\tilde c}_1}, and c˜2{{\tilde c}_2} using the hash function H, and produces the final signature value through the rejection sampling algorithm. The final signature σ contains the challenge value c˜2{{\tilde c}_2}, all ciphertext information, and the response value z₁, z₂. The signing algorithm is shown in Algorithm 3.

The verification algorithm ML-GS.Verify takes the group public key gpk, a message M, and a signature σ as input. First, the public key random seed ρ is used to expand the public parameters u, B through the ExpandPK algorithm, and then the hash ρ and message M into a 64-byte message representation μ. Next, the challenge value c˜2{{\tilde c}_2} from the signature part and the ciphertext ct₂ are used to obtain the challenge value c˜2{{\tilde c}_2}. Finally, the verification algorithm checks the validity of z₁, z₂ and verifies whether the reconstructed value w2′{\bf{w}}_2^\prime matches the signer's commitment hash c˜2{{\tilde c}_2}. The verification algorithm is shown in Algorithm 4.

The opening algorithm ML-GS.Open takes gpk, the tracing key gtk, a message M, a signature σ, and the registration list reg as input. First, as in the verification algorithm, it reconstructs u, B, μ, c˜{\tilde c}. Then, using the decryption algorithm of the K-PKE scheme and the tracing key s, it recovers the identity vector g_i and c˜1{{\tilde c}_1}. If g_i ∈ reg and c˜1=H(μ‖ Bz1−gic ‖ct1){{\tilde c}_1} = H\left( {\mu \left\| {{\bf{B}}{z_1} - {{\bf{g}}_i}c} \right\|c{t_1}} \right), the algorithm returns the identity i; otherwise, it returns ⊥. The open algorithm is shown in Algorithm 5.

In this section, we prove the correctness of the ML - GS scheme, mainly including the verification correctness and the opening correctness. Suppose the signature σ=(c˜2,z1,z2,ct1,ct2)\sigma = \left( {{{\tilde c}_2},{{\bf{z}}_1},{{\bf{z}}_2},c{t_1},c{t_2}} \right) is a valid signature generated by a group member for the message M under the group public key gpk = (ρ, A, a, b).

1)Verification correctness

The verifier first recovers the public key (u, B), the hash value μ of the message M, and the challenge c˜{\tilde c}, and calculates the commitment w2′{\bf{w}}_2^\prime . If all coefficients of \z₁, z₂ are less than γ₁ – β, and the commitment w2′{\bf{w}}_2^\prime , and the ciphertext ct₁ is equal to c˜{\tilde c}, then the signature is accepted. Next, we will provide the proofs for these two parts of verification passing.

a) ‖ z1 ‖∞≤γ1−β∧‖ z2 ‖∞≤γ1−β{\left\| {{{\bf{z}}_1}} \right\|_\infty } \le {\gamma _1} - \beta \wedge {\left\| {{{\bf{z}}_2}} \right\|_\infty } \le {\gamma _1} - \beta

During the signature stage, according to step 16 of the signature algorithm procedure, if any coefficient of z₁, z₂ are greater than γ₁ – β, it will lead to the failure of the rejection sampling output, and recalculation will be done with the new masking vector y_i. Therefore, the correct signatures output by the signature algorithm procedure will all satisfy ‖z‖∞≤γ1−β{\bf{z}}{_\infty } \le {\gamma _1} - \beta .

b) c˜2=H(μ‖ w2′ ‖ct1){{\tilde c}_2} = H\left( {\mu \left\| {{\bf{w}}_2^\prime } \right\|c{t_1}} \right)

First, according to step 5 of the verification algorithm, we have w2′=Bz1+Az2−uc{\bf{w}}_2^\prime = {\bf{B}}{{\bf{z}}_1} + {\bf{A}}{{\bf{z}}_2} - {\bf{uc}}. Since z₁ = y₁ + cx_i, z₂ = y₂ + cs_i,1, we can obtain: 1w2′=Bz1+Az2−uc=B(y1+cxi)+A(y2+csi)−uc=By1+Ay2+Bcxi+Acsi−uc\matrix{ {{\bf{w}}_2^\prime = {\bf{B}}{{\bf{z}}_1} + {\bf{A}}{{\bf{z}}_2} - {\bf{uc}}} \hfill \cr { = {\bf{B}}\left( {{{\bf{y}}_1} + c{{\bf{x}}_i}} \right) + {\bf{A}}\left( {{{\bf{y}}_2} + c{{\bf{s}}_i}} \right) - {\bf{u}}c} \hfill \cr { = {\bf{B}}{{\bf{y}}_1} + {\bf{A}}{{\bf{y}}_2} + {\bf{B}}c{{\bf{x}}_i} + {\bf{A}}c{{\bf{s}}_i} - {\bf{u}}c} \hfill \cr }

Then, according to steps 3 and 7 of the key generation algorithm, we know that: g_i = Bx_i, As_i = u – g_i. Combining with formula (1), we can get: 2w2′=By1+Ay2+Bcxi+Acsi−uc=By1+Ay2+gic+Asic−(Asi+gi)c=By1+Ay2+gic−gic\matrix{ {{\bf{w}}_2^\prime = {\bf{B}}{{\bf{y}}_1} + {\bf{A}}{{\bf{y}}_2} + {\bf{B}}c{{\bf{x}}_i} + {\bf{A}}c{{\bf{s}}_i} - {\bf{u}}c} \hfill \cr { = {\bf{B}}{{\bf{y}}_1} + {\bf{A}}{{\bf{y}}_2} + {{\bf{g}}_i}c + {\bf{A}}{{\bf{s}}_i}c - \left( {{\bf{A}}{{\bf{s}}_i} + {{\bf{g}}_i}} \right)c} \hfill \cr { = {\bf{B}}{{\bf{y}}_1} + {\bf{A}}{{\bf{y}}_2} + {{\bf{g}}_i}c - {{\bf{g}}_i}c} \hfill \cr } we can get: w2′=By1+Ay2=w2{\bf{w}}_2^\prime = {\bf{B}}{{\bf{y}}_1} + {\bf{A}}{{\bf{y}}_2} = {{\bf{w}}_2}.

2) Therefore, we can obtain c˜2=H(μ‖ w2 ‖ct1)=H(μ‖ w2′ ‖ct1){{\tilde c}_2} = H\left( {\mu \left\| {{{\bf{w}}_2}} \right\|c{t_1}} \right) = H\left( {\mu \left\| {{\bf{w}}_2^\prime } \right\|c{t_1}} \right).

Opening correctness

Based on the security guarantees of the Kyber encryption algorithm specified in FIPS 203 [8], the K-PKE.Decrypt algorithm can recover the identity matrix g_i and the challenge value c˜1{{\tilde c}_1} with overwhelming probability. If the signature was generated by a legitimate group member and is valid, then the identity vector satisfies g_i ∈ reg according to the registration table. Moreover, from Step 10 of the signing algorithm, we obtain w₁ = By₁ = Bz₁ – g_ic and c˜1=H(μ‖ Bz1−gic ‖ct1){{\tilde c}_1} = H\left( {\mu \left\| {{\bf{B}}{{\bf{z}}_1} - {{\bf{g}}_i}c} \right\|c{t_1}} \right). Therefore, the opening correctness of the ML-GS scheme is ensured.

Our proposed ML-GS scheme is constructed based on hard problems over lattices. We evaluate its security using two sets of parameters and corresponding estimations, as shown in Table 2. First, under the parameter set PARM I, and based on the estimation by enumeration [38], the ML-GS scheme achieves 96 bits post-quantum security level, which meets the Category I standard defined by the NIST. Similarly, PARM II enables our scheme to achieve 154 bit post-quantum security.

Table 2.

Parameter	Recommended Parameters
	PARM I	PARM II
q	1073738753	1073738753
Q	3329	3329
n	256	256
(k, l)	(4,4)	(6,5)
η	83832	83290
η1	3	3
τ	39	49
γ1≥11τknη{\gamma _1} \ge 11\tau \sqrt {kn} \eta	≈ 231	≈ 231
BKZ blocksize b to break SIS	364	583
Classical security	106	170
Quantum security	96	154

The main time-consuming operations in the ML-GS scheme stem from trapdoor generation and sampling algorithms over module lattices. In evaluating the computational efficiency of the ML-GS scheme, we primarily focus on operations that consume significant time, while omitting those with relatively low overhead, such as polynomial addition and hash operations. We employed the Sage Math library and conducted performance tests under a Windows 11 operating system with an AMD Ryzen 5 5600G 3.9 GHz processor. The average runtime of these time-consuming operations was measured over 1000 executions. The computation times for trapdoor generation and sampling algorithms are presented in Table 3.

We tested the setup, key generation, signing, and verification algorithms of the ML-GS scheme under two sets of security parameters, and the results are shown in Table 4.

Next, we compare our scheme with two lattice-based GS schemes: Lyubashevsky et al. introduced their scheme in 2022 [12], and Tang et al. proposed theirs in 2024 [23]. The comparison results regarding time computation overhead are shown in Table 5. Here, d denotes the number of polynomial matrix multiplications, T_M represents the total time cost of these multiplications, and T_S and T_V refer to the time required for non-interactive zero-knowledge proof generation and verification, respectively.

To make the comparison results more intuitive, we conducted simulated implementations of the main time-consuming operations for both schemes and the ML-GS scheme. Figure 5 presents the specific comparison of time overhead.

Figure 5.

Time Cost Comparison of GS Schemes (ms).

As shown in Figure 5, the ML-GS scheme significantly outperforms existing solutions in all core operations. Key generation is over 75% faster, signing time is reduced by up to 69%, and verification is about 30% faster. These improvements highlight the efficiency and practicality of our scheme for real-time applications.

The sizes of the keys and signatures are calculated as follows:

Group public key. The group public key consists of a public random seed ρ, a public matrix A, and a K-PKE key pair (a, b). Therefore, its size is 32 + 32kl⌈log₂ q⌉ + 32k(k + 1)⌈log₂ Q⌉ bits.

Group trapdoor key. The group trapdoor key consists of a secret random seed ρ and a trapdoor matrix T_A. Thus, its size is 32 + 32l²⌈log₂ q⌉ bits.

Group tracing key. The group tracing key includes only the K-PKE decryption key s. Hence, its size is 32k⌈log₂ η₁⌉ bits.

Signing key. The group member's signing secret key consists of a random short vector x and a sampled short vector s. To compute the size of s, we refer to Lemma 5. Accordingly, the total size is 32k⌈ log2η ⌉+32l⌈ log2(2ηd(log2q+2)n) ⌉32k\left\lceil {{{\log }_2}\eta } \right\rceil + 32l\left\lceil {{{\log }_2}\left( {2\eta \sqrt {d\left( {{{\log }_2}q + 2} \right)n} } \right)} \right\rceil bits.

Signature. A signature σ consists of (c˜2,z1,z2,ct1,ct2)\left( {{{\tilde c}_2},{{\bf{z}}_1},{{\bf{z}}_2},c{t_1},c{t_2}} \right). The total size of the signature is 32 + 32 + 32(k + l)log₂(12γ₁) + 1024k bits.

Based on the above calculations of the storage overhead for each key and signature, Figure 6 presents the communication cost of the ML-GS scheme under two parameter sets. As shown in Figure 6, the group public key incurs the largest overhead in the ML-GS scheme, reaching 22.5 KB under PARM I, followed by the group trapdoor key, which costs 15 KB. This substantial cost mainly results from the trapdoor setup and preimage sampling over lattices, which require relatively large parameter settings.

Figure 6.

The Store Cost of ML-GS Scheme.

Regarding the signature size, thanks to the signature architecture adopted from FIPS 204, our scheme exhibits a unique advantage among lattice-based group signature schemes. Under the PARM I parameter set that achieves a 96-bit post-quantum security level, the signature size is only 12.75 KB.

To demonstrate the efficiency of the ML-GS scheme in terms of storage cost, we compare our scheme with scheme [12] and [23], and the comparison results are shown in Table 6. For a fair comparison, we evaluate ML-GS under PARM II, which provides the same post-quantum security level as scheme [12] and [23].

From Table 6, it can be seen that the public key size of our scheme is reduced by approximately 6.46% compared to scheme [12]’s 48KB, and by about 83.32% compared to scheme [23]’s 268.5KB, effectively lowering storage overhead. The secret key size is 7KB, which is slightly increased by 16.67% compared to [12], but reduced by 89.75% compared to [23]’s 68.7KB, maintaining a relatively low key burden. More notably, the signature size is only 18.0KB, representing a reduction of approximately 80.43% and 95.34% compared to the 92KB of [12] and 386.1KB of [23], respectively.

However, compared with some existing group signature schemes based on zero - knowledge proofs, our ML - GS scheme also has some drawbacks when it comes to tracing the identity of group members. That is, the ML - GS.Open algorithm in the opening phase requires a registration list reg as an input parameter. The registration list contains the identity vectors of all registered group members. Therefore, as the number of group members increases, the overhead cost of the opening algorithm for the group administrator will increase.