Abstract
Currently, existing group signature schemes with user-controlled and sequential linkability (GS-UCSL) suffer from critical limitations: they lack post-quantum security, cannot efficiently revoke malicious signers, grant excessive tracing power to group managers (GM), and rely on heavy revocation lists or secure channels that incur high computation or communication overhead. To address these issues, we propose an efficient lattice-based conditional privacy-preserving GS-UCSL (LCGS-UCSL). Our scheme is built on lattice cryptography to achieve post-quantum security, and unifies implicit linkability, explicit linkability, and sequential linkability under user autonomous control. We design a polynomial-based revocation mechanism that eliminates revocation list verification and secure-channel token updates, enabling lightweight and privacy-preserving member revocation. To curb GM’s overreach, we introduce key-oblivious encryption to split users into traceable and non-traceable types without their awareness, and use cuckoo hashing to realize \(O(1)\) registry operations. We further integrate signature aggregation and non-interactive zero-knowledge proofs of knowledge to optimize batch verification and reduce communication overhead. We formally prove the scheme’s anonymity, traceability, Existential Unforgeability under Chosen-Message Attack, and non-frameability in the random oracle model, and validate its practicality via performance analysis. The results show that LCGS-UCSL achieves comprehensive functionality with competitive efficiency, filling the gap toward post-quantum secure GS-UCSL with efficient revocation and balanced privacy.
Introduction
Group signatures (Bellare et al. 2005; Chaum and Heyst 1991) enhance the conventional signature mechanism by concealing the identity of the signer. They operate within an anonymity set established by a collective of signers, whose membership requests have been reviewed and approved by the group manager (GM). In this system, any holder of the group’s public key can authenticate a signature. To prevent the abuse of anonymity, the opener typically has the authority to reveal the actual signer of any signature.
Linkable group signatures (Garms and Lehmann 2019) are an emerging group signature scheme, but most linkable group signature schemes rely on a GM to perform the linking action, making the scheme impractical. Satisfactorily, a scheme with user-controlled linkability (Krenn et al. 2019) has emerged, granting signers the autonomy to control which signatures can be linked, and eliminating the dependency on GM. This is also more conducive from a privacy perspective as it retains the signer’s complete control. They facilitate user-controlled linkability through the calculated pseudonyms associated with each signature, which are determined by the scope and the signer’s secret key. This directly results in the automatic linking of all signatures of the same scope.
Besides, in scenarios where group signatures are applied to data that possesses inherent sequential characteristics, such as time series data, merely confirming the connection between signatures is insufficient. It may be necessary to provide proof that the sequence of linked messages adheres to the same order in which they were originally generated, without any omissions of potentially pertinent information. For example, in intelligent transportation systems, smart vehicles are often required to transmit sensor data to a centralized data repository, or “data lake”. The chronological sequence of events within this data can be crucial for anomaly detection. A vehicle that reports fuel levels of 35, 45, 30, and then 40 L within a brief period might signal an anomaly, whereas a sequence of 45, 40, 35, and 30 L would likely be considered normal. Similarly, in contact tracing systems, where pseudonyms are utilized for a specific duration before being replaced with new ones, individuals may be requested to disclose pseudonymous data that spans across multiple pseudonyms. The intentional omission or misordering of certain data segments could hinder the effectiveness of the contact tracing process. In these applications, the number of anonymous signatures that need to be sequentially linked could reasonably range from tens to potentially hundreds of signatures within a relatively short timeframe.
Furthermore, the preservation of order can also be significant in situations with lower demands on data throughput. For instance, the implications of a person failing to pay a series of mortgage fees consecutively could be quite different from those of scattered defaults occurring over a more extended period. Ensuring the integrity and sequential order of anonymous signatures is, therefore, essential for the accurate interpretation and utilization of the data in these contexts.
In traditional group signature schemes (Bao et al. 2023a), traceability is achieved by requiring each signer to encrypt his/her identity information and then prove that the resulting ciphertext is well-formed. This inevitably grants the GM the omnipotent ability to uncover the real identity behind every valid signature. To mitigate such an excessive concentration of power, we need a mechanism that separates traceable signers from non-traceable ones without the signers themselves noticing the partition. A natural idea is to let traceable signers encrypt their identities under a public key whose corresponding secret key is known exclusively to the GM, whereas non-traceable signers employ a public key whose secret key is unknown to anyone. Yet rational signers have no incentive to volunteer for traceability. Consequently, the assignment must be performed in an oblivious fashion. We achieve this by randomizing the public key. During registration, the GM first rerandomizes the original public key into a fresh key \(rpk\) and issues \(rpk\) to the signer. Thanks to the rerandomization algorithm’s key-oblivious property, no party lacking the original secret key and the employed randomness can determine whether \(rpk\) is traceable. Thus, the GM silently tags certain randomized keys as traceable while the signers remain unaware. When producing a signature, each signer simply encrypts their identity under their own \(rpk\). To formalize this technique, Kohlweiss et al. (2015) introduced key-oblivious encryption (KOE) (a public-key primitive that allows public keys to be rerandomized without revealing the linkage), and instantiated it under the ElGamal framework. Ling et al. (2019) later proposed a lattice-based accountable tracing signature that relies on a lattice variant of KOE. We will adopt this lattice-based construction in our scheme.
Currently, the majority of group signature schemes are developed based on large integer factorization, discrete logarithms, and bilinear pairings (Bellare et al. 2005; Chaum and Heyst 1991; Garms and Lehmann 2019; Bao et al. 2023a; Kohlweiss 2015; Yue et al. 2021; London et al. 2025; Krenn et al. 2019; Diaz and Lehmann 2021). However, they stand vulnerable to certain quantum algorithms (Nielsen and Chuang 2001; Shor 1999; Grover 1996). Group signature schemes constructed on the lattice structure are deemed significant owing to their resilience against quantum computing attacks, the correlation of average to worst-case scenarios, in addition to their fundamental nature and capability for efficiency. Hence, a plethora of lattice-based group signature schemes have recently been put forward (Ling et al. 2019; Gordon et al. 2010; Pino et al. 2018; Lyubashevsky et al. 2021; Tang et al. 2023, 2024; Gao et al. 2024; Chen et al. 2025).
Motivation
Group signatures with user-controlled and sequential linkability (GS-UCSL), pioneered by Diaz et al. in PKC’21 (Diaz and Lehmann 2021), enable signers to autonomously control linkability and preserve the chronological order of signatures, making them highly suitable for privacy-critical sequential scenarios such as intelligent transportation, contact tracing, and time-series data authentication. However, the state-of-the-art GS-UCSL scheme suffers from three fatal limitations that hinder its real-world deployment, especially in post-quantum and dynamic environments:
-
(1)
It is not post-quantum secure, as it relies on classic number-theoretic assumptions vulnerable to quantum attacks;
-
(2)
It provides no revocation mechanism, so malicious signers cannot be removed from the group;
-
(3)
It omits traceability entirely, leaving no way to identify abusive signers when necessary.
Meanwhile, existing lattice-based post-quantum group signature schemes either lack user-controlled linkability, suffer from inefficient revocation based on revocation lists or secure channels, or grant excessive, unrestricted tracing power to group managers. None of them can simultaneously achieve post-quantum security, user-controlled sequential linkability, efficient revocation, and balanced traceability.
Contribution
To fill this gap and resolve the above limitations, we propose an efficient lattice-based conditional privacy-preserving GS-UCSL (LCGS-UCSL). Our scheme inherits full user-controlled sequential linkability from the original GS-UCSL, and introduces conditional opening and lightweight polynomial-based revocation to enable practical accountability. In this way, we preserve complete group signature functionality while supporting batch verification of sequentially linked signatures. Our core contributions are summarized as follows:
-
(1)
Post-quantum secure GS-UCSL with full linkability modes.
We construct the first lattice-based group signature supporting user-controlled and sequential linkability (including implicit, explicit, and sequential linkability), which resists quantum attacks and preserves complete user-controlled privacy for sequential data scenarios (e.g., Internet of Vehicles time-series, contact tracing).
-
(2)
Lightweight polynomial revocation without privacy leakage.
We propose a novel revocation polynomial (RP) mechanism that avoids revocation list verification and frequent secure-channel token distribution. The GM only updates the public revocation polynomial instead of reissuing member keys, achieving constant-time revocation verification and protecting the privacy of revoked users.
-
(3)
Balanced traceability with oblivious user classification.
We use lattice-based key-oblivious encryption (Ling et al. 2019) to randomly classify users into traceable/non-traceable types without being detected, restricting GM’s arbitrary tracing power while retaining conditional opening capability. Cuckoo hashing is adopted for \(O(1)\) registry operations, optimizing system scalability.
-
(4)
Efficient batch verification and anti-key-escrow design.
Signature aggregation and non-interactive zero-knowledge proofs of knowledge (NIZKPoK) are integrated to reduce batch verification time and communication overhead by over 80%.
It is worth noting that although the proposed LCGS-UCSL scheme integrates multiple advanced mechanisms including polynomial-based revocation, key-oblivious encryption, user-controlled sequential linkability, and signature aggregation, these components are designed to cooperate in a lightweight and modular way. The polynomial revocation mechanism avoids revocation lists and frequent secure-channel updates; key-oblivious encryption enables oblivious user tracing classification without extra computation; sequential linkability is achieved via lightweight hash-based state chains; and signature aggregation optimizes batch verification efficiency. The entire system follows a clear modular workflow, which ensures comprehensive functionality while maintaining practical feasibility. Comprehensive performance analysis under large-scale deployments and dynamic revocation scenarios is provided in Sect. “Performance evaluation” to validate efficiency and stability.
The paper is organized as follows. Section “Related work” provides an overview of related works. Section “Preliminaries” introduces notation and the basics of lattice-based cryptography. Section “Framework of our LCGS-UCSL” defines our LCGS-UCSL and provides a high-level framework for the scheme, together with security and threat models. Section “Our scheme” contains the full mathematical details of LCGS-UCSL. Sect. “Correctness analysis and security proof” provides correctness analysis and security proofs. Section “Performance evaluation” provides performance evaluation and benchmarking. Sect. “Conclusion and future work” gives a summary of our work and some concluding remarks.
Related work
This section introduces some related works about Revocable group signature, Lattice-based group signatures, and Group signature (ring signature) for user-controlled linkability.
Revocable group signature schemes
For revocable group signature, current recognisable structures are categorisable into two broad types. The first entails the design wherein revoked signers are unable to generate a signature to pass verification checks, as in Yue et al. (2021). The alternate type is where a revoked signer can produce a signature that initially passes a verification check, but subsequently fails the revocation check, as demonstrated in Refs. London et al. (2025), Tang et al. (2023), Gao et al. (2024). In the first category, the central concept involves periodically publishing broadcast encryptions decipherable only by non-revoked members. These schemes necessitate signers to calculate both the group membership certificate and decryption proof for the ciphertext, resulting in reasonably high computational costs. Nevertheless, the verification costs are relatively low and constant. In contrast, the latter category relies on the verifier local revocation (VLR) mechanism, which utilizes a revocation list (RL) containing information about revoked signers to verify if the signer’s signature has been revoked. This scheme facilitates a more efficient signature as it requires the signer to compute only the proof of group membership. However, the verification process correlates with the number of revoked members, rendering VLR suitable only for short RLs, and the process of revoking verification results in a loss of privacy for the signer.
Lattice-based group signature schemes
Currently, the focus on the development of lattice-based group signature schemes is intensifying, and the first such scheme was pioneered by Gordon et al. (2010) in 2010. In the years that followed, an array of lattice-based group signature schemes emphasizing heightened efficiency has been proposed, as seen in Ref. Pino et al. (2018, Lyubashevsky et al. (2021). In 2019, Ling et al. (2019) proposed a lattice-based privacy-preserving group signature scheme for controlling the GM’s revocation rights, which solves the problem of excessive GM rights. In 2023, Tang et al. (2023) introduced a method centered on lattice-based group signatures with time-bound keys using redactable signatures. This scheme employs a combination of natural revocation and RL, thereby achieving a minimized revocation cost. In 2024, Gao et al. (2024) proposed a post-quantum secure group signature with VLR and backward unlinkability. In 2025, Tang et al. (2024) proposed an event-oriented linkable group signature from the lattice, which is post-quantum secure and linkable. However, the linkability of this scheme is not user-controlled and is not flexible, so it is not very practical. Tran et al. (2025) proposed a lattice-based group signature scheme secure in the standard model. Constructed from random lattices, this scheme features a smaller signature size and public key size, as well as security against chosen-ciphertext attacks, compared with other group signature schemes based on random lattices.
Signature schemes for user-controlled linkability
In 2019, Krenn et al. (2019) proposed the concept of group signature scheme with user-controlled linkability and analyzed the security of the scheme. In 2021, Diaz and Lehmann (2021) introduced the groundbreaking GS-UCSL scheme, marking the first instance of a group signature merging user-controlled linkability with sequential linkability. The following year, Fiore et al. (2022) presented an innovative ring signature with user-controlled linkability (RS-UCL). Unlike group signatures with user-controlled linkability, RS-UCL does not necessitate a GM and can be deployed entirely in a decentralized fashion. In 2023, Bao et al. (2023a, 2023b) proposed user-control linkability schemes and applied these schemes to specific scenarios (such as the Internet of Vehicles system and the medical service system). Nevertheless, none of the above schemes are post-quantum secure. In 2025, Chen et al. (2025) proposed a lattice-based group signature with user-controlled linkability and verifier conditional revocation, yet this scheme does not possess sequential linkability. To date, no post-quantum secure GS-UCSL scheme has been proposed.
Preliminaries
This section introduces the notations and a basic overview of lattice-based cryptography.
Notations
Table 1 describes some system parameters (the selection of \(d\), \(q\), \(Q\), \(\sigma\), \({\sigma}_{r}\), \({\sigma}_{B}\), \({\sigma}_{{s}_{\text{1,2}}}\), \({\sigma}_{{s}_{3}}\) and \({\sigma}_{k}\) values refer to Refs. Pino et al. (2018), Lyubashevsky (2012), Micciancio and Peikert (2012)).
Basic properties and hardness assumptions of lattices
Lattices
Some basic knowledge of the lattices is shown in Ajtai (1999). \({{\varvec{b}}}_{1}\), \({{\varvec{b}}}_{2}\), \(\cdots\), \({{\varvec{b}}}_{m}\) are \(m\) linearly independent vectors in \({\mathcal{R}}^{n}\). Let \({\varvec{B}}=[{{\varvec{b}}}_{1}|\) \({{\varvec{b}}}_{2}|\) \(\cdots |\) \({{\varvec{b}}}_{m}]\), \(\Lambda \left({\varvec{B}}\right)=\{{\varvec{B}}{\varvec{c}}=\sum_{i=1}^{m}{{\varvec{b}}}_{i}{c}_{i}\)|\({\varvec{c}}\in {\mathbb{Z}}^{m}\}\) represent the \(m\)-dimensional lattice \(\Lambda\) generated by the basis \({\varvec{B}}\), where \({\varvec{B}}\) is a basis of the lattice \(\Lambda \left({\varvec{B}}\right)\).
Typically, for a matrix \({\varvec{A}}\in {\mathbb{Z}}_{q}^{n\times m}\), two special integer lattices modulo \(q\) are described as follows:
Discrete Gaussian distribution
Let \(n>0\), \({\varvec{c}}\in {\mathbb{R}}^{n}\) and \(\boldsymbol{\Sigma }\in {\mathbb{R}}^{n\times n}\) be a positive-definite symmetric matrix. The Gaussian function with covariance parameter \(\boldsymbol{\Sigma }\) and center parameter \({\varvec{c}}\) is defined as
The Gaussian distribution over the lattice \(\Lambda \subseteq \text{s}\text{p}\text{a}\text{n}(\boldsymbol{\Sigma })\) with covariance parameter \(\boldsymbol{\Sigma }\) and center parameter \({\varvec{c}}\) is the distribution with support \(\Lambda\) and probability mass function
If \(\boldsymbol{\Sigma }={\sigma }^{2}{{\varvec{I}}}_{n}\), we write \({\rho}_{\sigma ,{\varvec{c}}}\) and \({\mathcal{D}}_{\Lambda ,\sigma ,\mathbf{c}}\). We omit \({\varvec{c}}\) when it is 0. We also define \({\mathcal{D}}_{\Lambda +{\varvec{c}},\Sigma }={\mathcal{D}}_{\Lambda ,\boldsymbol{\Sigma },-{\varvec{c}}}+{\varvec{c}}\). For convenience, we let \({\rho}_{\boldsymbol{\Sigma },{\varvec{c}}}(S)\) denote the quantity \(\sum_{{\varvec{y}}\in S}{\rho}_{\boldsymbol{\Sigma },{\varvec{c}}}({\varvec{y}})\) for any countable set \(S\) (Lyubashevsky 2012).
Gaussian sampling
Lemma 1
(Micciancio and Regev 2007). For the discrete Gaussian distribution \({\mathcal{D}}_{{\mathbb{Z}}^{m},\sigma }\), we have.
According to (Lyubashevsky 2012) and Lemma 1, when \({\varvec{c}}\in {\mathbb{Z}}^{m}\), and \(\alpha\) is a positive number, the following conclusions can be drawn:
Hard problems on lattices
The security of our LCGS-UCSL relies on the difficult assumptions of the Module SIS (MSIS) problem (Pino et al. 2018) and the Module Learning With Errors (MLWE) problem (Pino et al. 2018).
Definition 1
(M(odule) \({SIS}_{q,h,v,\gamma }\) problem (Pino et al. 2018)). Given a random matrix \({\varvec{A}}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{h\times v}\), the advantage of solving the (Hermite Normal Form) \({MSIS}_{q,h,v,\gamma }\) problem for an algorithm \(\mathcal{A}\) is.
Definition 2
(the Decision version of M(odule) \({SIS}_{q,h,v,\gamma }\) problem (Lyubashevsky 2012)). Given a pair (\({\varvec{A}}\), \({\varvec{t}}\)) decide, with non-negligible advantage, whether it came from the \({MSIS}_{q,h,v,\gamma }\) distribution or whether it was generated uniformly at random from \({\mathbb{R}}_{q}^{h\times v}\times {\mathbb{R}}_{q}^{h}\).
Definition 3
(M(odule) \({LWE}_{q,h,v,\chi }\) problem (Pino et al. 2018)). Given a random matrix \({\varvec{A}}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{h\times v}\), and a probability distribution \(\chi\) over \({\mathbb{R}}_{q}\), the advantage of solving the Decision \({MLWE}_{q,h,v,\chi }\) problem for an algorithm \(\mathcal{A}\) is.
where \({\varvec{A}}\stackrel{\mathbf{\$}}{\leftarrow }\in {\mathbb{R}}_{q}^{h\times v}\), \({\varvec{s}}\stackrel{\mathbf{\$}}{\leftarrow }{\chi }^{v}\), \({\varvec{e}}\stackrel{\mathbf{\$}}{\leftarrow }{\chi }^{h}\), and \({\varvec{v}}\stackrel{\mathbf{\$}}{\leftarrow }{\mathbb{R}}_{q}^{h}\). Namely, distinguish distributions (\({\varvec{A}}\), \({\varvec{A}}{\varvec{s}}+{\varvec{e}}\)) and (\({\varvec{A}}\), \({\varvec{v}}\)).
MP12 trapdoor functions for lattices
Ref. Micciancio and Peikert (2012) gives two polynomial algorithms (GenTrap, SampleD). The details are as follows:
GenTrap(\(n\), \(m\), \(\overline{m }\), \(q\)): Given \(n\), \(q\), \(k=\lceil\text{log}q\rceil\), \(\overline{m }=w=n\lceil\text{log}q\rceil\), and \(m=\overline{m }+w\), this algorithm samples a matrix \(\overline{{\varvec{A}} }\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{Z}}_{q}^{n\times \overline{m} }\), computes \({{\varvec{g}}}^{T}=(1,\) \(2,\) \(4,\) \(\cdots\),\({2}^{k-1})\in {\mathbb{Z}}^{k}\) and \({\varvec{G}}={{\varvec{I}}}_{n}\otimes{{\varvec{g}}}^{T}\), and outputs a trapdoor \({\varvec{R}}\in {\mathbb{Z}}_{q}^{\overline{m}\times w }\) (\(\Vert \widetilde{{\varvec{R}}}\Vert \le O(\sqrt{n\text{log}\,q})\)), and \({\varvec{A}}=[\overline{{\varvec{A}} }| {\varvec{G}}-\overline{{\varvec{A}}}{\varvec{R} }]\in {\mathbb{Z}}_{q}^{n\times m}\).
SampleD(\({\varvec{A}}\), \({\varvec{R}}\), \({\varvec{u}}\), \(\sigma\)): Given the matrix \({\varvec{A}}\in {\mathbb{Z}}_{q}^{n\times m}\), the vector \({\varvec{u}}\in {\mathbb{Z}}_{q}^{n}\), the trapdoor \({\varvec{R}}\in {\mathbb{Z}}_{q}^{\overline{m}\times w }\), and the Gaussian parameter \(\sigma \ge \Vert \widetilde{{\varvec{R}}}\Vert \times \omega (\sqrt{\text{log}\,n})\), this algorithm outputs \({\varvec{x}}\in {\mathbb{Z}}_{q}^{m}\) which satisfied \({\varvec{A}}{\varvec{x}}={\varvec{u}} \text{mod}\;q\) and \(\Vert \widetilde{{\varvec{x}}}\Vert \le \sigma \sqrt{m}\).
Both of the above algorithms can be easily extended to ring versions.
Rejection sampling
Given a positive integer \(m\), \(\sigma =\omega (\| {\varvec{c}}\| \sqrt{\text{log}\,m})\), and an arbitrary set \(V\subseteq {\mathbb{Z}}^{m}\), \(h:V\to \text{R}\) is a distribution whose preimage is \(V\). There is a constant \(M\) making the distribution of (1), (2) less than \({2}^{-\omega (\text{log}\,m)}/M\) at statistical distance (Lyubashevsky 2012):
-
(1)
\({\varvec{c}}\stackrel{\boldsymbol{\$}}{\leftarrow }h\), \({\varvec{z}}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{Z}}^{m},\sigma ,{\varvec{c}}}\), output (\({\varvec{z}}\), \({\varvec{c}}\)) with probability \(\text{m}\text{i}\text{n}(\frac{{\mathcal{D}}_{{\mathbb{Z}}^{m},\sigma }}{M{\mathcal{D}}_{{\mathbb{Z}}^{m},\sigma ,{\varvec{c}}}}\), \(1)\).
-
(2)
\({\varvec{c}}\stackrel{\boldsymbol{\$}}{\leftarrow }h\), \({\varvec{z}}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{Z}}^{m},\sigma }\), output (\({\varvec{z}}\), \({\varvec{v}}\)) with probability \(1/M\).
Moreover, the probability that (1) outputs something is at least \((1-{2}^{-\omega (\text{log}\,m)})/M\). More concretely, if \(\sigma =\alpha \| {\varvec{c}}\|\) for any positive \(\alpha\), then \(M={\text{e}}^{\frac{12}{\alpha }+\frac{1}{2{\alpha }^{2}}}\) (\(\alpha\)=12), the output of algorithm (1) is within statistical distance \({2}^{-100}/M\) of the output of (2), and the probability that (1) outputs something is at least \((1-{2}^{-100})/M\).
For ease of use, we set the function.
Rej(\({\varvec{z}}\), \({\varvec{c}}\), \(\sigma\), \(m\)):
Return \({\varvec{z}}\) with probability of min(1,\(\frac{{\mathcal{D}}_{{\mathbb{R}}^{m},\sigma }\left({\varvec{z}}\right)}{M{\mathcal{D}}_{{\mathbb{R}}^{m},\sigma ,{\varvec{c}}}\left({\varvec{z}}\right)}) (M={\text{e}}^{\frac{12}{\alpha }+\frac{1}{2{\alpha }^{2}}}\),α = 12).
Cuckoo hashing
Cuckoo hashing (Pagh and Rodler 2004) organizes a set of elements into a table \(T\) comprising \((1+\varepsilon )n\) slots, where \(n\) denotes the maximum number of elements to be stored, and \(\varepsilon\) represents a small positive constant (typically \(0<\varepsilon \ll 1\)) that controls the table’s load factor and ensures low collision probability. The design guarantees that every slot contains at most one element. Two independent hash functions, h0 and h1, govern the placement process. Initially, an element \({x}_{i}\) is directed to \(T[{h}_{b}({x}_{i})]\). If that slot is already occupied by another element \({x}_{j}\), \({x}_{i}\) evicts \({x}_{j}\), which is then reinserted into \(T[{h}_{1-b}({x}_{j})]\). This iterative eviction chain continues until either every element finds an empty slot or a preset relocation limit is exceeded. Elements that still cannot be placed after the limit are diverted to an auxiliary stash. All fundamental operations (lookup, deletion, and insertion) retain worst-case constant complexity.
NIZKPoK
NIZKPoK (Pino et al. 2018) is a technology that is used to prove linear relationships. A NIZKPoK scheme must satisfy three core properties:
Completeness: If the prover and verifier are honest, the verifier accepts with overwhelming probability.
Honest-verifier zero-knowledge: There exists a simulator that, given the statement and the verifier’s challenge, can produce a transcript indistinguishable from a real one.
Special soundness: Given two accepting transcripts with the same commitment but different challenges, one can efficiently extract a valid witness.
Polynomial method
For a secret value \(b\in {S}_{1}\), we construct a polynomial \(f\left(x\right)=\prod_{i=1}^{p}(x-{r}_{{id}_{i}})+b\) (\({r}_{{id}_{i}}\in {\mathbb{R}}_{q}\)), we can assign \({r}_{{id}_{i}}\) to \({id}_{i}\), and only those who own \({r}_{{id}_{i}}\) can recover the secret value \(b\). When the trusted authority wants to revoke someone’s restoration rights, it only needs to resample the secret value \({b}{\prime}\) and use the remaining \({r}_{{id}_{i}}\) to recalculate the polynomial.
The commitment scheme
Our LCGS-UCSL scheme uses the lattice-based commitment scheme by Baum et al. (2018). Signers prove their identity through zero-knowledge proofs on committed values. This avoids direct identity disclosure. The specific algorithm is as follows:
KeyGen: Create public parameters \({{\varvec{A}}}_{1}\in {\mathbb{R}}_{q}^{n\times k}\) and \({{\varvec{A}}}_{2}\in {\mathbb{R}}_{q}^{{\ell}\times k}\) that can be used to commit to messages \({\varvec{x}}\in {\mathbb{R}}_{q}^{{\ell}}\).
Commit: To commit to \({\varvec{x}}\in {\mathbb{R}}_{q}^{{\ell}}\), choose a random polynomial vector \({\varvec{r}}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{\beta }^{k}\) and output the commitment \(Com({\varvec{x}}\);\({\varvec{r}})=\left[\begin{array}{c}{{\varvec{c}}}_{1}\\ {{\varvec{c}}}_{2}\end{array}\right]=\left[\begin{array}{c}{{\varvec{A}}}_{1}\\ {{\varvec{A}}}_{2}\end{array}\right]\times {\varvec{r}}+\left[\begin{array}{c}{0}^{n}\\ {\varvec{x}}\end{array}\right]\).
Open: A valid opening of a commitment \(\left[\begin{array}{c}{{\varvec{c}}}_{1}\\ {{\varvec{c}}}_{2}\end{array}\right]\) is a 3-tuple consisting of an \({\varvec{x}}\in {\mathbb{R}}_{q}^{{\ell}}\), \({\varvec{r}}=\left[\begin{array}{c}{r}_{1}\\ \vdots \\ {r}_{k}\end{array}\right]\in {\mathbb{R}}_{q}^{k}\), and \(f\in \overline{\mathcal{C} }\). The verifier checks that \(f\times \left[\begin{array}{c}{{\varvec{c}}}_{1}\\ {{\varvec{c}}}_{2}\end{array}\right]=\left[\begin{array}{c}{{\varvec{A}}}_{1}\\ {{\varvec{A}}}_{2}\end{array}\right]\times {\varvec{r}}+f\times \left[\begin{array}{c}{0}^{n}\\ {\varvec{x}}\end{array}\right]\), and that for all i, \(\Vert {{\varvec{r}}}_{i}\Vert \le 2\sqrt{\beta }\).
Specific parameters must be set in order for the commitment scheme to have the security properties of hiding and binding, see scheme (Baum et al. 2018) for more details on parameter settings.
Nth degree truncated polynomial ring units (NTRU)
The \({\text{N}\text{T}\text{R}\text{U}}_{q,r}\) problem (Ducas et al. 2014) (over the ring \({\mathbb{R}}\)) is defined as follows:
Sample ring elements f, \(g\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{r}\) and output \(h=f/g\), if \(g\) is invertible in \({\mathbb{R}}_{q}\) (otherwise, re-sample \(g\)). The \({\text{N}\text{T}\text{R}\text{U}}_{q,r}\) problem is to distinguish \(h\) from a random element in \({\mathbb{R}}_{q}\).
Key-oblivious encryption scheme
The lattice-based key-oblivious encryption scheme (Ling et al. 2019) is described as follows:
-
(1)
Setup (\(\lambda\))
Given the security parameter \(\lambda\), let \(d=O(\lambda )\), \(q\) be a prime modulus, and \(Q\) be a prime modulus. Define the rings \({\mathbb{R}}={\mathbb{Z}}[x]/({x}^{d}+1)\), \({\mathbb{R}}_{q}={\mathbb{R}}/q{\mathbb{R}}\), and \(\mathcal{C}=\{c\in {\mathbb{R}}|{\Vert c\Vert }_{1}=\kappa\), \({\Vert c\Vert }_{\infty }=1\}\). This algorithm then outputs public parameter pp = \(\{d\),\(q\), \(Q\),\({\mathbb{R}}\),\({\mathbb{R}}_{q}\), \(\mathcal{C}\)}.
-
(2)
KeyGen(pp).
Given the input pp, this algorithm samples \(({\varvec{s}}\),\({\varvec{e}})\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\times {S}_{{2}^{79}}^{3}\) and \(a\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{Q}\). Set pk = (\(a\), \({\varvec{b}}\)) = (\(a\), \(a{\varvec{s}}+{\varvec{e}}\))∈\({\mathbb{R}}_{Q}\times {\mathbb{R}}_{Q}^{3}\) and sk = \({\varvec{s}}\). It then returns (pk, sk).
-
(3)
KeyRand(pk).
Given the public key pk = (\(a\),\({\varvec{b}}\)), it samples\(g\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\),\({e}_{g,1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), and\({{\varvec{e}}}_{g,2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\). Compute (\({a}{\prime}\),\({{\varvec{b}}}{\prime}\)) = (\(ag+{e}_{g,1}\),\({\varvec{b}}g+{{\varvec{e}}}_{g,2}\)) ∈ \({\mathbb{R}}_{Q}\times {\mathbb{R}}_{Q}^{3}\). This algorithm then outputs the randomized public key as \({\text{pk}}^{{\prime}}\)=(\({a}{\prime}\),\({{\varvec{b}}}{\prime}\)).
-
(4)
Enc(\({\text{pk}}^{{\prime}}\), \({\varvec{m}}\))
Given the public key \({\text{pk}}^{{\prime}}\)=(\({a}{\prime}\), \({{\varvec{b}}}{\prime}\)) and a message \({\varvec{m}}\)∈\({S}_{1}^{3}\), it samples \({s}_{E}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({e}_{E,1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), and \({{\varvec{e}}}_{E, 2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\). Compute (\({c}_{1}\), \({{\varvec{c}}}_{2}\)) = (\(q({a}{\prime}{s}_{E}+{e}_{E,1})\), \(q({{\varvec{b}}}{\prime}{s}_{E}+{{\varvec{e}}}_{E, 2})+{\varvec{m}}\)) ∈ \({\mathbb{R}}_{Q}\times {\mathbb{R}}_{Q}^{3}\), and set \({{\varvec{m}}}^{\boldsymbol{*}}=\left({{\varvec{c}}}_{2}-{c}_{1}{\varvec{s}}\right)\overline{c} \text{mod}\,Q\) (where \(\overline{c }\in \overline{\mathcal{C} }\)). If \({\Vert {{\varvec{m}}}^{\boldsymbol{*}}\Vert }_{\infty }>Q/2\kappa\) or \({\varvec{m}}\ne {{\varvec{m}}}^{\boldsymbol{*}}{\overline{c} }^{-1} \text{mod}\,q\), resample \({s}_{E}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({e}_{E,1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), and \({{\varvec{e}}}_{E, 2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\). This algorithm returns ciphertext as ct = (\({c}_{1}\), \({{\varvec{c}}}_{2}\)).
-
(5)
Dec(sk, ct).
Given sk=\({\varvec{s}}\) and ct = (\({c}_{1}\), \({{\varvec{c}}}_{2}\)), set \({{\varvec{m}}}^{\boldsymbol{*}}=\left({{\varvec{c}}}_{2}-{c}_{1}{\varvec{s}}\right)\overline{c} \text{mod}\,Q \) (where \(\overline{c }\in \overline{\mathcal{C} }\)). If \({\Vert {{\varvec{m}}}^{\boldsymbol{*}}\Vert }_{\infty }\le Q/(2\kappa )\), compute \({\varvec{m}}={{\varvec{m}}}^{\boldsymbol{*}}{\overline{c} }^{-1} \text{mod}\,q\); otherwise, return \(\perp\).
Framework of our LCGS-UCSL
In this section, the primary framework of our LCGS-UCSL is presented, encompassing the definition of our LCGS-UCSL, security model, and threat model.
Definition of LCGS-UCSL
We refer to Refs. Diaz and Lehmann (2021), Pino et al. (2018), and Tang et al. (2023) to derive our algorithm model. An LCGS-UCSL scheme is composed of the following nine probabilistic polynomial time (PPT) algorithms.
-
(1)
GSetup(\({1}^{\lambda }\)): This algorithm takes as input the security parameter \(\lambda\), and outputs group public key \(gpk\), GM private key (group manager key \(gmk\) and group trace key \(gtk)\), and private registry CH.
-
(2)
KeyGen(\(gmk\), \(i\)): A new member \(i\) joins the group by an interactive protocol with the GM. Given \(gmk\), after completing this interaction protocol, the member receives a group signature secret key \({sk}_{i}\), group encryption public key \({gptk}_{i}\), and a unique number \({un}_{i}\), and a state \({st}_{i}\) with 1.
-
(3)
Join(\(N\), identity set \({\varvec{i}}\)(\(\left|{\varvec{i}}\right|=N\))): This algorithm takes as input \(N\) signers (identity set \({\varvec{i}}(\left|{\varvec{i}}\right|=N))\), and outputs the RPs \({f}_{j}\left(x\right)\) (\(j\in [0\), \(2)\)), the RPK \(\overline{{b }_{1}}\), and RSKs \({r}_{i} (i\in [N])\).
-
(4)
Sign(\({sk}_{i}\), \({r}_{i}\), \({gptk}_{i}\), \({un}_{i}\),\(M\), \({st}_{i}\)): This algorithm takes as input a group signature secret key \({sk}_{i}\), RSK \({r}_{i}\), group encryption public key \({gptk}_{i}\), unique number \({un}_{i}\), state \({st}_{i}\), and a message \(M\), and outputs a group signature \(\Sigma\).
-
(5)
Verify(\(gpk\), RPK \(\overline{{b }_{1}}\),\(\Sigma\)): This algorithm takes as input the group public key \(gpk\), the RPK \(\overline{{b }_{1}}\), a group signature \(\Sigma\), and outputs either “Valid” or “Invalid”.
-
(6)
SLink(\(gpk\), \(\boldsymbol{\Sigma }\), \(LM\)): This algorithm takes as input the group public key \(gpk\), group signature set \(\boldsymbol{\Sigma }\), and a message \(LM\) for verifying the linked group signature. If the group signature set \(\boldsymbol{\Sigma }\) has any invalid group signature, it outputs “Invalid”; otherwise, it outputs a sequential link group signature \({\Sigma}_{seq}\).
-
(7)
VerifySLink(\(gpk\), RPK \(\overline{{b }_{1}}\), \({\Sigma}_{seq}\)): This algorithm takes as input the group public key \(gpk\), the RPK \(\overline{{b }_{1}}\), a sequential link group signature \({\Sigma}_{seq}\), and outputs either “Valid” or “Invalid”.
-
(8)
Open(\(gtk\), \(\Sigma\)): This algorithm takes as input the group trace key \(gtk\), \({un}_{i}\),\(\Sigma\), and outputs either a member identity \(i\) or \(\perp\).
-
(9)
Revoke(\(i\), \({un}_{i}\)): This algorithm takes as input \(i\), \({un}_{i}\), and outputs the new RPK and new RPs.
In addition, our scheme is divided into implicit link, explicit link, and sequential linkability, as follows:
Implicit Linkability: Each signature is accompanied by a pseudonym, generated by the signer for a specific scope. Reusing the same scope results in the same pseudonym, making all signatures generated for the same scope immediately linkable to the signer. Pseudonymous signatures of different scopes cannot be linked unless proven by an explicit link generated by the signer.
Explicit Linkability: After generating the signatures, the signer can claim and link them. Given a set of signatures, the signer proves that he/she created all signatures, i.e., links the signatures in the set.
Sequential Linkability: While generating a signature, signers can generate a proof of sequence. A verifier can verify that a set of linked group signatures is linked in sequence.
Security model
LCGS-UCSL aims to fulfill seven essential security properties: correctness, anonymity, traceability, linkability (implicit linkability, explicit linkability, and sequential linkability), non-frameability, revocability, and Existential Unforgeability under Chosen-Message Attack (EUF-CMA). These security properties are outlined in Refs. Diaz and Lehmann (2021), Pino et al. (2018), and Tang et al. (2023). Specifically, correctness guarantees that group signatures, which are genuinely generated by non-revoked group members, are valid, and can be opened by the GM (if the signer can be traced). Anonymity ensures that the adversary cannot discern the signer’s identity from the group signature unless the group trace key is compromised. In our scheme, the adversary can query group signature secret keys, excluding the target member’s group signature secret key. Traceability guarantees that no adversary can produce a valid signature that is not traceable to any registered group member. EUF-CMA guarantees that no adversary can produce a valid signature. Non-frameability guarantees that no adversary can produce a valid signature that opens to an honest group member who did not actually sign the message. Linkability requires the existence of a PPT algorithm that can be used to determine whether two group signatures come from the same signer. Sequence linkability requires the existence of a PPT algorithm that can be used to determine whether a series of group signatures comes from the same signer and whether they are linked in sequence. Revocability ensures that signers whose signature rights have been revoked cannot generate legitimate group signatures.
The above security notions are detailed in Definitions 4, 5, 6, 7 and 8. Before that, we refer to the Ref. Tang et al. (2023) to introduce nine oracles \(\mathcal{O}\text{Add}(i)\), \(\mathcal{O}{\text{J}}_{\text{U}}(i)\), \(\mathcal{O}{\text{J}}_{\text{M}}(i)\), \(\mathcal{O}\text{Cor}(i)\), \(\mathcal{O}\text{Sign}(i\),\(M)\), \(\mathcal{O}\text{Open}(gtk\),\(\Sigma )\), \(\mathcal{O}\text{Revoke}(i\), \({un}_{i})\), \(\mathcal{O}\text{SLink}\)(\(gpk\), \(\boldsymbol{\Sigma }\),\(LM\),\(i\)), and \(\mathcal{O}{\text{Ch}}_{\text{b}}({i}_{0}\), \({i}_{1}\),\(M)\). We denote \(\mathcal{H}\), \(\mathcal{C}\mathcal{O}\) and \(\mathcal{S}\) as the sets of honest members, corrupted members, and the set of group signatures, respectively.
-
(1)
\(\mathcal{O}\text{Add}(i)\): The adding member oracle allows adding an honest member \(i\) to the group, and adds \(i\) to \(\mathcal{H}\).
-
(2)
\(\mathcal{O}{\text{J}}_{U}(i)\): The joining oracle allows the adversary \(\mathcal{A}\) (who corrupts the GM) to add member \(i\) to the group.
-
(3)
\(\mathcal{O}{\text{J}}_{M}(i)\): The joining oracle that plays the part of the GM allows a corrupt member to join the group, and adds \(i\) to \(\mathcal{C}\mathcal{O}\).
-
(4)
\(\mathcal{O}\text{Cor}(i)\): On input an honest member identity \(i\), the corruption oracle returns the signature key of \(i\). It removes \(i\) from \(\mathcal{H}\) and adds \(i\) to \(\mathcal{C}\mathcal{O}\).
-
(5)
\(\mathcal{O}\text{Sign}(i\), \({gptk}_{i}\),\(M)\): Takes as input \(i\), \({gptk}_{i}\), and \(M\). If \(i\) is an honest member in \(\mathcal{H}\), the signature oracle returns \(\Sigma \leftarrow \text{Sign}({sk}_{i}\), \({gptk}_{i}\), \(M\),\({scp}_{i})\) and adds \(\Sigma\) to \(\mathcal{S}\).
-
(6)
\(\mathcal{O}\text{Open}(gtk\), \(\Sigma )\): The opening oracle returns \(\text{Open}(gtk\), \(\Sigma )\).
-
(7)
\(\mathcal{O}\text{Revoke}(i\), \({un}_{i})\): The revocation oracle returns \(\text{Revoke}(i\), \({un}_{i})\).
-
(8)
\(\mathcal{O}{\text{Ch}}_{b}({i}_{0}\), \({i}_{1}\),\(M)\): On input two honest members \({i}_{0}\), \({i}_{1}\), the challenge oracle samples \(b\in \{\text{0,1}\}\) and returns \(\text{Sign}({sk}_{{i}_{b}}\), \({r}_{{i}_{b}}\), \({gptk}_{{i}_{b}}\), \({un}_{{i}_{b}}\), \(M\),\({st}_{{i}_{b}})\). This oracle is not allowed to be queried on the \(\mathcal{O}\text{Open}\). \({i}_{0}\), \({i}_{1}\) are not allowed as input to the \(\mathcal{O}\text{Cor}\) and the \(\mathcal{O}\text{Revoke}\).
-
(9)
\(\mathcal{O}\) SLink(\(gpk\), \(\boldsymbol{\Sigma }=({\Sigma}_{1}\),\({\Sigma}_{2})\), \(LM\),\(i\)): On input two group signatures \({\Sigma}_{1}\),\({\Sigma}_{2}\) on the message \(M\), the oracle outputs the linked group signature \({\Sigma }{\prime}\) on message \(LM\) on \(\boldsymbol{\Sigma }=({\Sigma}_{1}\),\({\Sigma}_{2})\) and adds \({\Sigma}_{1}\), \({\Sigma}_{2}\) and \({\Sigma }{\prime}\) to \(\mathcal{S}\).
Definition 4
(Anonymity). For any PPT adversary \(\mathcal{A}\), the experiment \({Exp}_{\mathcal{A}}^{an}({1}^{\lambda })\) is defined in Fig. 1. The LCGS-UCSL satisfies anonymity if the advantage
is negligible for any adversary \(\mathcal{A}\).
Definition 5
(Traceability). For any PPT adversary \(\mathcal{A}\), the experiment \({Exp}_{\mathcal{A}}^{trace}(\lambda )\) is defined in Fig. 1. The LCGS-UCSL satisfies Traceability if the advantage
is negligible for any adversary \(\mathcal{A}\).
Definition 6
(EUF-CMA). For any PPT adversary \(\mathcal{A}\), the experiment \({Exp}_{\mathcal{A}}^{EUF-CMA}(\lambda )\) is defined in Fig. 1. The LCGS-UCSL satisfies EUF-CMA if the advantage
is negligible for any adversary \(\mathcal{A}\).
Definition 7
(Non-frameability). For any PPT adversary \(\mathcal{A}\), the experiment \({Exp}_{\mathcal{A}}^{nf}(\lambda )\) is defined in Fig. 1. The LCGS-UCSL satisfies Non-frameability if the advantage
is negligible for any adversary \(\mathcal{A}\).
Definition 8
(Linkability). For any PPT adversary \(\mathcal{A}\), the experiment \({Exp}_{\mathcal{A}}^{link}({1}^{\lambda })\) is defined in Fig. 1. The LCGS-UCSL satisfies linkability if the advantage
is negligible for any adversary \(\mathcal{A}\).
Threat model
Within the framework of our LCGS-UCSL scheme, only the GM is fully trusted, while signers and verifiers may be malicious, and external eavesdroppers are considered fully malicious. We explicitly detail their potential misbehaviors and cryptographic countermeasures as follows:
Signers (malicious).
-
(1)
Inject false data: Generate signatures on malicious messages. Mitigated by the Verify algorithm’s NIZKPoK verification, ensuring only legitimate non-revoked members pass. EUF-CMA security prevents forgery. And the Revoke algorithm can update the RPs to invalidate malicious signers’ RSK \({r}_{i}\);
-
(2)
Impersonate other signers: Steal credentials to sign on behalf of others. Prevented by joint key generation, where the signer’s secret component \({{\varvec{s}}}_{i,3}\) is generated locally and never transmitted. The GM only provides a complementary secret key (\({{\varvec{s}}}_{i,1}\), \({{\varvec{s}}}_{i,2}\)), and the NIZKPoK cryptographically binds the signature to the unique key triple;
-
(3)
Launch replay attacks: Rebroadcast old signatures \(\Sigma\). Countered by the state counter \({st}_{i}\) and unique sequential link values \({seq}_{{st}_{i}}\), verified against the append-only bulletin board (BB) for freshness. BB’s uniqueness check for \({seq}_{{st}_{i}}\) prevents replay;
-
(4)
Bypass revocation. Mitigated by GM’s polynomial-based RSK updates.
Verifiers (malicious).
-
(1)
Unilateral attempt to restore the signer’s identity: Try to extract signer identities from group signature \(\Sigma\). Impossible, as Open requires the GM’s tracing key \(gtk={\varvec{s}}\) and the NIZKPoK challenge decomposition. Verifiers only possess \(gpk\) and lack \(gtk\). The encrypted component (\(h\),\({\varvec{d}}\)) is an MLWE encryption under public key (\(a\), \({{\varvec{b}}}_{2}\)) whose security relies on the MLWE assumption. Only the GM with tracing key \(gtk={\varvec{s}}\) can recover the commitment randomness to extract the identity;
-
(2)
Track signers by correlating pseudonyms: Link \(nym\) across messages. Prevented by scope-based pseudonyms that change unpredictably with \({scp}_{{st}_{i}}\) (to derive a portion of the signer’s private key from \({{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}{{\varvec{s}}}_{i,3}={nym}_{{st}_{i}}\), we need to solve the MSIS problem). User-controlled linkability ensures signatures are unlinkable unless the signer explicitly creates a sequentially linked group signature \({\Sigma}_{seq}\);
-
(3)
Collude to bypass revocation: Share information to accept signatures from revoked members. Thwarted by the revocation check embedded in NIZKPoK (\({{{\varvec{a}}}_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\)), which depends on the current RPK \(\overline{{b }_{1}}\). Only the GM can update the RPs \({f}_{j}{\prime}\left(x\right)\) and RPK \({\overline{{b }_{1}}}^{{\prime}}\) after revocation by sampling a new PRSK \({{\varvec{k}}}{\prime}\);
External adversary (malicious). Any external adversary can eavesdrop, intercept, and modify all communications. Their capabilities are bounded by:
-
(1)
Post-quantum hardness: Deriving secret keys or forging signatures requires solving MSIS/MLWE problems, infeasible even for quantum adversaries;
-
(2)
Random oracle model (ROM) security: The NIZKPoK’s security in the ROM ensures simulation-extractability against active attack;
-
(3)
Bulletin board: Acts as a trusted append-only log that verifies signatures before publication, preventing denial-of-service and ensuring a publicly verifiable state.
System component interaction and workflow
To ensure clarity and practicality, we explicitly describe the interaction logic among all core mechanisms of LCGS-UCSL:
-
(1)
During registration, the GM uses key-oblivious encryption to generate re-randomized public keys and obliviously mark users as traceable or non-traceable, while cuckoo hashing supports \(O(1)\) registry operations.
Each user key is jointly generated by the user and GM to avoid key escrow.
-
(2)
During signing, the user generates signatures with implicit, explicit, or sequential linkability, and revocation validity is checked via the public revocation polynomial in NIZKPoK.
-
(3)
Signature aggregation is used to reduce batch verification overhead by more than 80%.
-
(4)
For revocation, the GM only updates the public revocation polynomial without reissuing member keys.
-
(5)
Opening works only for traceable users to preserve privacy for non-traceable ones.
This modular, tightly coupled design ensures all components work synergistically without redundant computation or communication.
Our scheme
This section describes the construction details of LCGS-UCSL and NIZKPoK.
Detailed scheme
In this section, we will present our LCGS-UCSL, which contains nine algorithms: GSetup, KenGen, Join, Sign, Verify, SLink, VerifySLink, Open, and Revoke. Next are the detailed descriptions of the nine algorithms. In our algorithm, we use NIZKPoK to prove the correctness of our group signature, which reduces the communication overhead of our scheme. We allow users to control whether the group signature can be linked (implicit linkability, explicit linkability, and sequential linkability), use a polynomial-based revocation mechanism to efficiently revoke the signature rights of malicious signers, use KOE technology (Ling et al. 2019) to prevent the signer from knowing whether he/she can be traced, and use cuckoo hash (Pagh and Rodler 2004) to instantiate the registry. Our parameter selection refers to Refs. Pino et al. (2018), Lyubashevsky (2012), Micciancio and Peikert (2012). Our scheme relies on a BB. The BB is assumed to verify data before writing, and the written data cannot be erased. These properties make it equivalent to a trusted third party.
Algorithm 1 GSetup(\(\lambda\)).
(1) Initialization parameters. Given the security parameter \(\lambda\), sets \(d=O(\lambda )\), challenge bound \(\kappa\) (\(\left(\begin{array}{c}d\\ \kappa \end{array}\right){2}^{\kappa }\ge {2}^{128}\)), prime modulus \(q\) (\(q\equiv 1 (\text{mod}\,2d)\)), prime modulus \(Q\) (\(Q\equiv 1 (\text{mod}\,2d)\)), the SIS Gaussian parameter \(\sigma =\sqrt{2d}\times \omega \left(\sqrt{\text{log}(2d)}\right)\), the signature Gaussian parameter \({\sigma}_{i}=\alpha \| {{\varvec{S}}}_{i}c\|\) (\({{\varvec{S}}}_{i}\) is the secret key, \(c\) is the challenge vector), the set of identity \([N]\subseteq {\mathbb{Z}}_{q}\), hash functions \({H}_{1}:{\{0, 1\}}^{*}\to \mathcal{C}=\{c\in {\mathbb{R}}|{\Vert c\Vert }_{1}=\kappa\), \({\Vert c\Vert }_{\infty }=1\}\), \({H}_{2}:{\{0, 1\}}^{*}\to {\mathbb{R}}_{q}^{3}\), and \({H}_{3}:{\{0, 1\}}^{*}\to {\mathbb{R}}_{q}\). Let Gadget matrix \({{\varvec{g}}}^{T}=[1 \delta ]\in {\mathbb{R}}_{q}^{1\times 2}\), where \(\delta =\lceil\sqrt{q}\rceil\). Next, the GM performs the following operations.
(2) Sample \({{\varvec{a}}}_{1}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{3}\), \({{\varvec{a}}}_{2}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{3}\), \({{\varvec{a}}}_{3}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{2}\), \({\varvec{R}}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2\times 2}\), \(({{\varvec{s}}}_{\text{0,1}}\),\({{\varvec{s}}}_{\text{0,2}}\),\({{\varvec{s}}}_{\text{0,3}})\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2}\times {S}_{1}^{2}\times {S}_{1}^{3}\), \(({a}^{\left(1\right)}\), \({a}^{(2)})\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{Q}\times {\mathbb{R}}_{Q}\), \(({\varvec{s}}\),\({\varvec{e}})\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\times {S}_{{2}^{79}}^{3}\), and \({{\varvec{b}}}_{2}^{(1)}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{Q}^{3}\).
(3) Set \({{{\varvec{b}}}_{1}}^{T}={{{\varvec{a}}}_{3}}^{T}{\varvec{R}}\in {\mathbb{R}}_{q}^{1\times 2}\), \(u=[{{{\varvec{a}}}_{3}}^{T}| {{{\varvec{b}}}_{1}}^{T}| {{{\varvec{a}}}_{2}}^{T}]\left[\begin{array}{c}{{\varvec{s}}}_{\text{0,1}}\\ {{\varvec{s}}}_{\text{0,2}}\\ {{\varvec{s}}}_{\text{0,3}}\end{array}\right]\), and \({{\varvec{b}}}_{2}^{(2)}={a}^{(2)}{\varvec{s}}+{\varvec{e}}\in {\mathbb{R}}_{Q}^{3}\).
(4) Set up a cuckoo hash function CH as a registry. This registry is private to the GM and is initially empty. Set its counter count to 0.
(5) Return \(gpk=({{\varvec{a}}}_{1}\),\({{\varvec{a}}}_{2}\),\({{\varvec{a}}}_{3}\), \({a}^{\left(1\right)}\), \({a}^{(2)}\),\({{\varvec{b}}}_{1}\),\({{\varvec{b}}}_{2}^{(1)}\), \({{\varvec{b}}}_{2}^{(2)}\),\(u)\), \(gmk={\varvec{R}}\), registry CH, and \(gtk={\varvec{s}}\).
Algorithm 2 KeyGen(\(i\in {\mathbb{Z}}_{q}\), \(gmk\))
(1) If the signer is not traceable, then the encrypted public key of the signer is \(({a}{\prime}={a}^{\left(1\right)}\), \({{\varvec{b}}}_{2}{\prime}={{\varvec{b}}}_{2}^{(1)})\); if the signer is traceable, the encrypted public key of the signer is \(({a}{\prime}={a}^{\left(2\right)}\), \({{\varvec{b}}}_{2}{\prime}={{\varvec{b}}}_{2}^{(2)})\). The current counter value is assigned to the signer as its unique number \({un}_{i}\), and the counter is increased by 1 (that is, count = count + 1). If the signer is traceable, its unique number is added to the registry CH.
(2) The GM samples \({g}_{i}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({e}_{{g}_{i},1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), and \({{\varvec{e}}}_{{g}_{i},2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\). Let \({gtpk}_{i}=\)(\(a={a}{\prime}{g}_{i}+{e}_{{g}_{i},1}\in {\mathbb{R}}_{Q}\), \({{\varvec{b}}}_{2}={{\varvec{b}}}_{2}{\prime}{g}_{i}+{{\varvec{e}}}_{{g}_{i},2}\in {\mathbb{R}}_{Q}^{3}\)).
(3) Signer \(i\) samples a secret key \({{\varvec{s}}}_{i,3}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{3}\), and sends \({{{\varvec{a}}}_{2}}^{T}{{\varvec{s}}}_{i,3}\) to the GM.
(4) According to the SampleD algorithm, the GM can sample \({{\varvec{s}}}_{i,1}\in {\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\), \({{\varvec{s}}}_{i,2}\in {\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\) s.t
(5) Let \({sk}_{i}=({{\varvec{s}}}_{i,1}\), \({{\varvec{s}}}_{i,2}\), \({{\varvec{s}}}_{i,3})\) and send \(({{\varvec{s}}}_{i,1}\), \({{\varvec{s}}}_{i,2})\) and \({gtpk}_{i}=\)(\(a\), \({{\varvec{b}}}_{2}\), \({un}_{i}\)) to signer \(i\) through a secure channel, and set \({st}_{i}\leftarrow 1\).
Algorithm 3 Join(\(N\), \({\varvec{i}}\)(identity set),\(\left|{\varvec{i}}\right|=N\))
For \(N\) signers, the GM samples the PRSK \({\varvec{k}}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2}\), \(N\) RSKs \({r}_{i}\in {\mathbb{R}}_{q}\), computes \({{{\varvec{a}}}_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\in {\mathbb{R}}_{q}\) and \({f}_{j}\left(x\right)=\prod_{i=1}^{N}(x-{r}_{i})+{k}_{j}\) (\(j\in [0\), \(2)\)), and publishes the RP set \({f}_{j}\left(x\right)\) and the RPK \(\overline{{b }_{1}}\). Finally, the GM sends \({r}_{i}\) to signer \(i (i\in {\varvec{i}}\), \(\left|{\varvec{i}}\right|=N)\) separately.
Remark 1
Even if a malicious signer attempts to recover the RSK of another signer, the best-known approach requires a time complexity of \(O(dq+{N}^{d}d\text{log}d)\). Thus, computationally infeasible for any realistic adversary.
Algorithm 4 Sign(\({sk}_{i}\), \({r}_{i}\), \({gptk}_{i}\), \({un}_{i}\),\(M\), \({st}_{i}\)) where \(M\in {\{\text{0,1}\}}^{*}\)
In this algorithm, step (1) and step (2) are to hide the identity of the signer and confirm that the signer is a legitimate group member; step (3) and step (4) are to reveal the signer when a malicious signer is found; step (5) is used for the revocation of the signature right later; step (6) is used for the link signature; step (7), step (8), step (9) and step (10) are used for the subsequent sequential linkability of signatures. Next, signer \(i\) performs the following operations:
-
(1)
Sample \(({{\varvec{r}}}_{{st}_{i}}\),\({{\varvec{r}}}_{{st}_{i}}{\prime})\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{3}\times {S}_{1}^{3}\), and set \({{\varvec{t}}}_{{st}_{i}}=\left[\begin{array}{c}{t}_{{st}_{i}, 1}\\ {t}_{{st}_{i},2}\end{array}\right]=\left[\begin{array}{c}{{{\varvec{a}}}_{1}}^{T}\\ {{{\varvec{a}}}_{2}}^{T}\end{array}\right]\times {{\varvec{r}}}_{{st}_{i}}+\left[\begin{array}{c}0\\ i\end{array}\right]\in {\mathbb{R}}_{q}^{2}\) and \({{\varvec{t}}}_{{st}_{i}}{\prime}=\left[\begin{array}{c}{t}_{{st}_{i}, 1}{\prime}\\ {t}_{{st}_{i},2}{\prime}\end{array}\right]=\left[\begin{array}{c}{{{\varvec{a}}}_{1}}^{T}\\ {{{\varvec{a}}}_{2}}^{T}\end{array}\right]\times {{\varvec{r}}}_{{st}_{i}}{\prime}+\left[\begin{array}{c}0\\ i\delta \end{array}\right]\in {\mathbb{R}}_{q}^{2}\).
-
(2)
Compute \({{{\varvec{v}}}_{{st}_{i}}}^{T}=[{{{\varvec{a}}}_{3}}^{T}\)|\({{{\varvec{b}}}_{1}}^{T}+\left[{t}_{{st}_{i},2}| {t}_{{st}_{i},2}{\prime}\right]\)|\({{{\varvec{a}}}_{2}}^{T}]\in {\mathbb{R}}_{q}^{1\times 7}\), and set \({{\varvec{s}}}_{{st}_{i}}{\prime}=\left[\begin{array}{c}{{\varvec{s}}}_{i,1}\\ {{\varvec{s}}}_{i,2}\\ {{\varvec{s}}}_{i,3}-[{{\varvec{r}}}_{{st}_{i}}| {{\varvec{r}}}_{{st}_{i}}{\prime}]{{\varvec{s}}}_{i,2}\end{array}\right]\in {\mathbb{R}}_{q}^{7}\) satisfying \({{{\varvec{v}}}_{{st}_{i}}}^{T}{{\varvec{s}}}_{{st}_{i}}{\prime}=u\).
-
(3)
Sample \({s}_{{st}_{i}, B}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({e}_{{st}_{i},1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), and \({{\varvec{e}}}_{{st}_{i}, 2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\), compute \({h}_{{st}_{i}}=q(a{s}_{{st}_{i}, B}+{e}_{{st}_{i},1})\) and \({{\varvec{d}}}_{{st}_{i}}=q({{\varvec{b}}}_{2}{s}_{{st}_{i}, B}+{{\varvec{e}}}_{{st}_{i}, 2})+{{\varvec{r}}}_{{st}_{i}}\), and set \({{\varvec{r}}}_{{st}_{i}}^{*}=\left({{\varvec{d}}}_{{st}_{i}}-{h}_{{st}_{i}}{\varvec{s}}\right)\overline{c }\) mod \(Q\) (where \(\overline{c }\in \overline{\mathcal{C} }\)). If \({\Vert {{\varvec{r}}}_{{st}_{i}}^{*}\Vert }_{\infty }>Q/2\kappa\) or \({{\varvec{r}}}_{{st}_{i}}\ne {{\varvec{r}}}_{{st}_{i}}^{*}{\overline{c} }^{-1} \text{mod}\,q\), resample \({s}_{{st}_{i}, B}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({e}_{{st}_{i},1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), and \({{\varvec{e}}}_{{st}_{i}, 2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\).
-
(4)
Set \({{\varvec{B}}}_{1}=\left[\begin{array}{c}\begin{array}{c}\begin{array}{ccc}qa& q& \begin{array}{ccc}0& 0& \begin{array}{ccc}0& 0& \begin{array}{cc}0& 0\end{array}\end{array}\end{array}\end{array}\\ \begin{array}{ccc}q{b}_{\text{2,1}}& 0& \begin{array}{ccc}q& 0& \begin{array}{ccc}0& 1& \begin{array}{cc}0& 0\end{array}\end{array}\end{array}\end{array}\end{array}\\ \begin{array}{c}\begin{array}{ccc}q{b}_{\text{2,2}}& 0& \begin{array}{ccc}0& q& \begin{array}{ccc}0& 0& \begin{array}{cc}1& 0\end{array}\end{array}\end{array}\end{array}\\ \begin{array}{ccc}q{b}_{\text{2,3}}& 0& \begin{array}{ccc}0& 0& \begin{array}{ccc}q& 0& \begin{array}{cc}0& 1\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}\right]\), \({{\varvec{B}}}_{2}=[0| 0| 0| 0| 0| {{{\varvec{a}}}_{1}}^{T}]\), \({\varvec{B}}=\left[\genfrac{}{}{0pt}{}{{{\varvec{B}}}_{1}}{{{\varvec{B}}}_{2}}\right]\in {\mathbb{R}}_{Q}^{4\times 8}\times {\mathbb{R}}_{q}^{1\times 8}\), \({{\varvec{r}}}_{{st}_{i},B}={[{s}_{{st}_{i}, B}| {e}_{{st}_{i},1}| {{{\varvec{e}}}_{{st}_{i}, 2}}^{T}| {{{\varvec{r}}}_{{st}_{i}}}^{T}]}^{T}\in {\mathbb{R}}^{8}\), and \({{\varvec{y}}}_{{st}_{i}}={[{h}_{{st}_{i}}| {{{\varvec{d}}}_{{st}_{i}}}^{T}| {t}_{{st}_{i}, 1}]}^{T}\in {\mathbb{R}}_{Q}^{4}\times {\mathbb{R}}_{q}\) satisfying \({\varvec{B}}{{\varvec{r}}}_{{st}_{i},B}={{\varvec{y}}}_{{st}_{i}}\).
-
(5)
Compute \({{{\varvec{a}}}_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\), \({\varvec{k}}=\left[\begin{array}{c}{f}_{0}({r}_{i})\\ {f}_{1}({r}_{i})\end{array}\right]\).
-
(6)
Sample \({scp}_{{st}_{i}}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}\) and compute \({{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}{{\varvec{s}}}_{i,3}={nym}_{{st}_{i}}\).
-
(7)
Compute \({n}_{{st}_{i}}={H}_{3}({{\varvec{s}}}_{i,3}\), \(0| {st}_{i})\), \({n}_{{st}_{i}-1}={H}_{3}({{\varvec{s}}}_{i,3}\), \(0| {st}_{i}-1)\).
-
(8)
Compute \({x}_{{st}_{i}}={H}_{3}({{\varvec{s}}}_{i,3}\), \(1| {n}_{{st}_{i}})\), \({x}_{{st}_{i}-1}={H}_{3}({{\varvec{s}}}_{i,3}\), \(1| {n}_{{st}_{i}-1})\).
-
(9)
Compute \({seq}_{{st}_{i},1}={H}_{3}({x}_{{st}_{i}})\), \({seq}_{{st}_{i},2}={H}_{3}({x}_{{st}_{i}}\oplus {x}_{{st}_{i}-1})\), \({seq}_{{st}_{i},3}={n}_{{st}_{i}}\).
-
(10)
Set \({seq}_{{st}_{i}}=({seq}_{{st}_{i},1}\),\({seq}_{{st}_{i},2}\),\({seq}_{{st}_{i},3})\).
-
(11)
Generate a proof.
$${\pi}_{{st}_{i}}={\text{NIZKPoK}}^{\text{L}\text{CGS}-\text{UCSL}}\left[\left({{\varvec{s}}}_{{st}_{i}}^{{\prime}},{{\varvec{r}}}_{{st}_{i},B},{\varvec{k}},{{\varvec{s}}}_{i,3}\right): {{{\varvec{v}}}_{{st}_{i}}}^{T}{{\varvec{s}}}_{{st}_{i}}^{{\prime}}=u\wedge {\varvec{B}}{{\varvec{r}}}_{{st}_{i},B}={{\varvec{y}}}_{{st}_{i}}\wedge {{{\varvec{a}}}_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\wedge {{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}{{\varvec{s}}}_{i,3}={nym}_{{st}_{i}}\right]\left(M\right).$$ -
(12)
Return group signature \({\Sigma}_{{st}_{i}}=(M\), \({scp}_{{st}_{i}}\), \({nym}_{{st}_{i}}\), \({{\varvec{t}}}_{{st}_{i}}\),\({{\varvec{t}}}_{{st}_{i}}{\prime}\), \({\pi}_{{st}_{i}}\),\({h}_{{st}_{i}}\),\({{\varvec{d}}}_{{st}_{i}}\), \({seq}_{{st}_{i}}\), \({st}_{i}\leftarrow {st}_{i}+1\),\({un}_{i})\) to the verifier.
Remark 2
For \({{{\varvec{v}}}_{{st}_{i}}}^{T}{{\varvec{s}}}_{{st}_{i}}{\prime}=u\):
The signatures in our construction are required to be uploaded to the BB. BB verifies the signature \(\Sigma\) and checks the uniqueness of \({seq}_{{st}_{i}}\), rejecting the signature if either check fails. The uniqueness of \({seq}_{{st}_{i}}\) ensures that no \({seq}_{{st}_{i}}{\prime}=({seq}_{{st}_{i},1}{\prime}\),\({seq}_{{st}_{i},2}{\prime}\),\({seq}_{{st}_{i},3}{\prime})\) exists in BB, such that \({seq}_{{st}_{i},1}={seq}_{{st}_{i},1}{\prime}\) or \({seq}_{{st}_{i},2}={seq}_{{st}_{i},2}{\prime}\) or \({seq}_{{st}_{i},3}={seq}_{{st}_{i},3}{\prime}.\)
To compute \({\varvec{k}}=\left[\begin{array}{c}{f}_{0}({r}_{i})\\ {f}_{1}({r}_{i})\end{array}\right]\), we can use the method described in Contributors 2024; Wikipedia and by squaring, Wikipedia (2024) which has a time complexity of \(O(2(N+\text{log}N)\times d\text{log}d)\), where \(O(d\text{log}d)\) is the time complexity of multiplying two degree-\(d\) polynomials using the Number Theoretic Transform (NTT) (Contributors 2024), \(O(\text{log}N)\) is the time complexity of an element raised to the power of \(N\) using fast exponentiation (Wikipedia and by squaring, Wikipedia 2024). Due to the need for aggregation, the signer needs to save the sampled values \(({{\varvec{r}}}_{{st}_{i}}\),\({{\varvec{r}}}_{{st}_{i}}{\prime}\), \({s}_{{st}_{i}, B}\), \({e}_{{st}_{i},1}\), \({{\varvec{e}}}_{{st}_{i}, 2})\) of each signature locally.
Algorithm 5 Verify(\(gpk\), RPK \(\overline{{b }_{1}}\),\({\Sigma}_{{st}_{i}}\))
If \({\text{NIZKPoK}}^{\text{LCGS}-\text{UCSL}}\) accepts the \({\pi}_{{st}_{i}}\), verifier returns “Valid”; otherwise, verifier returns “Invalid”.
Algorithm 6 SLink(\(gpk\), \(\boldsymbol{\Sigma }\), \(LM=({M}_{1}\),\(\cdots\),\({M}_{{st}_{i}-1})\), \(i\))
Signer \(i\) performs the following operations:
-
(1)
If any \({\Sigma}_{j}\) does not exist in BB, abort.
-
(2)
If all \({un}_{j}\) are not identical, abort; otherwise, let \({un}_{i}\) be the value of \({un}_{j}\) and \({st}_{i}\) be the max value of all \({st}_{j}\).
-
(3)
Compute \(\overline{{\varvec{t}} }=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{t}}}_{j} \text{mod}\,q\), \(\overline{{{\varvec{t}} }^{{\prime}}}=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{t}}}_{j}^{{\prime}} \text{mod}\,q\) (which means \(\overline{{\varvec{r}} }=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{r}}}_{j} \text{mod}\,q\), \(\overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{r}}}_{j}{\prime} \text{mod}\,q\)).
-
(4)
Compute \({\overline{{\varvec{v}}} }^{T}=[{{{\varvec{a}}}_{3}}^{T}\)|\({{{\varvec{b}}}_{1}}^{T}+\left[\overline{{t }_{2}}| \overline{{t }_{2}{\prime}}\right]\)|\({{{\varvec{a}}}_{2}}^{T}]\in {\mathbb{R}}_{q}^{1\times 7}\) and set \(\overline{{{\varvec{s}} }{\prime}}=\left[\begin{array}{c}{{\varvec{s}}}_{i,1}\\ {{\varvec{s}}}_{i,2}\\ {{\varvec{s}}}_{i,3}-[\overline{{\varvec{r}} }| \overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}]{{\varvec{s}}}_{i,2}\end{array}\right]\in {\mathbb{R}}_{q}^{7}\) satisfying \({\overline{{\varvec{v}}} }^{T}\overline{{{\varvec{s}} }{\prime}}=u\).
-
(5)
Compute \(\overline{h }=\sum_{j\in [1,{st}_{i}-1]}{h}_{j} \text{mod}\,Q\), \(\overline{{\varvec{d}} }=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{d}}}_{j} \text{mod}\,Q\).
-
(6)
Set \(\overline{{{\varvec{r}} }_{B}}=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{r}}}_{j,B}\in {\mathbb{R}}^{8}\) and \(\overline{{\varvec{y}} }={[\overline{h }| {\overline{{\varvec{d}}} }^{T}| \overline{{t }_{1}}]}^{T}\in {\mathbb{R}}_{Q}^{4}\times {\mathbb{R}}_{q}\) satisfying \({\varvec{B}}\overline{{{\varvec{r}} }_{B}}=\overline{{\varvec{y}} }\).
-
(7)
Compute \(\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}} }=\sum_{j\in [1, {st}_{i}-1]}{H}_{2}\left({scp}_{j}\right) \text{mod}\,q\), \(\overline{nym }=\sum_{j\in [1, {st}_{i}-1]}{nym}_{j} \text{mod}\,q\) (which satisfies \(\overline{nym }={\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}}} }^{T}{{\varvec{s}}}_{i,3}\)).
-
(8)
Generate a proof
$${\pi}_{seq}={\text{N}\text{I}\text{Z}\text{K}\text{P}\text{o}\text{K}}^{\text{L}\text{C}\text{G}\text{S}-\text{U}\text{C}\text{S}\text{L}}\left[\left(\overline{{{\varvec{s}} }^{{\prime}}}, \overline{{{\varvec{r}} }_{B}},{\varvec{k}},{{\varvec{s}}}_{i,3}\right):{\overline{{\varvec{v}}} }^{T}\overline{{{\varvec{s}} }^{{\prime}}}=u\wedge {\varvec{B}}\overline{{{\varvec{r}} }_{B}}=\overline{{\varvec{y}}}\wedge {{{\varvec{a}} }_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\wedge {\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}}} }^{T}{{\varvec{s}}}_{i,3}=\overline{nym }\right]\left(LM\right).$$ -
(9)
For all \({\Sigma}_{j}\) in \(\boldsymbol{\Sigma }\), compute \({x}_{j}={H}_{3}({{\varvec{s}}}_{i,3}\),\(1| {seq}_{j,3})\).
-
(10)
Return \({\Sigma}_{seq}\leftarrow (LM\), \(\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}} }\), \(\overline{nym }\), \(\overline{{\varvec{t}} }\),\(\overline{{{\varvec{t}} }^{\boldsymbol{{\prime}}}}\), \({\pi}_{seq}\),\(\overline{h }\), \(\overline{{\varvec{d}} }\), \({\{{seq}_{j}=({seq}_{j,1}, {seq}_{j,2}), {x}_{j}\}}_{j\in [1,{st}_{i}-1]}\), \({st}_{i}\),\({un}_{i})\).
Remark 3
For \({\overline{{\varvec{v}}} }^{T}\overline{{{\varvec{s}} }{\prime}}=u\), the correctness analysis is the same as \({{{\varvec{v}}}_{{st}_{i}}}^{T}{{\varvec{s}}}_{{st}_{i}}{\prime}=u\).
Algorithm 7 VerifySLink(\(gpk\), RPK \(\overline{{b }_{1}}\), \({\Sigma}_{seq}\))
Verifier performs the following operations:
-
(1)
If \({\text{N}\text{I}\text{Z}\text{K}\text{P}\text{o}\text{K}}^{\text{L}\text{C}\text{G}\text{S}-\text{U}\text{C}\text{S}\text{L}}\) accepts the \({\pi}_{seq}\), return “Valid”; otherwise, return “Invalid”.
-
(2)
Check whether \({seq}_{\text{1,1}}={H}_{3}({x}_{1})\) or not. If not, reject.
-
(3)
For \(j\in [2\),\({st}_{i}-1]\), check \({seq}_{j,1}={H}_{3}({x}_{j})\) and \({seq}_{j,2}={H}_{3}({x}_{j}\oplus {x}_{j-1})\). If not, reject.
Algorithm 8 Open(\(gtk\), \(\Sigma\))
-
(1)
First, check whether the signer’s unique number \({un}_{i}\) is in the registry CH. If not, abort.
-
(2)
If the Verify algorithm or VerifyLink algorithm returns “Invalid” for the group signature \(\Sigma\), output \(\perp\) and terminate.
-
(3)
Let \(c\) be the challenge used in \(\pi\), sample \({c}{\prime}\stackrel{\boldsymbol{\$}}{\leftarrow }\mathcal{C}\), set \(\overline{c }=c-{c}{\prime}\).
-
(4)
Set \({{\varvec{r}}}_{{st}_{i}}^{*}=\left({{\varvec{d}}}_{{st}_{i}}-{h}_{{st}_{i}}{\varvec{s}}\right)\overline{c } mod Q\). If \({\Vert {{\varvec{r}}}_{{st}_{i}}^{*}\Vert }_{\infty }\le Q/(2\kappa )\), compute \({{\varvec{r}}}_{{st}_{i}}^{**}={{\varvec{r}}}_{{st}_{i}}^{*} \text{mod}\;q\); otherwise, return \(\perp\).
-
(5)
Compute \(i={t}_{{st}_{i},2}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}_{{st}_{i}}^{**}{\overline{c} }^{-1}\). If \(i\in [N]\), return \(i\); otherwise, return \(\perp\).
-
(6)
When \(\Sigma\) is the linked group signature, if \({\Vert {{\varvec{r}}}^{\boldsymbol{*}}\Vert }_{\infty }={\Vert \left(\overline{{\varvec{d}} }-\overline{h}{\varvec{s} }\right)\overline{c}\Vert }_{\infty } \text{mod}\;Q={\Vert (q(\left(-a\overline{{s }_{B}}-\overline{{e }_{1}}\right){\varvec{s}}+\overline{{{\varvec{e}} }_{2}}+{{\varvec{b}}}_{2}\overline{{s }_{B}})+\overline{{\varvec{r}} })\overline{c}\text{mod}\;Q\Vert }_{\infty }<\frac{Q}{2\widehat{\mathcal{C}}}=\frac{Q}{2\kappa }\), compute \({{\varvec{r}}}^{\boldsymbol{*}\boldsymbol{*}}={{\varvec{r}}}^{\boldsymbol{*}} \text{mod}\;q\); otherwise, return \(\perp\). \(\varvec{r}^{{**}} = \varvec{r}^{*} {\text{mod}}\;Q\;{\text{mod}}\;q = \left( {varvec{\bar{d}} - \bar{h}varvec{s}} \right)\bar{c}\;{\text{mod}}\;Q\;{\text{mod}}\;q = \left( {q\left( {\left( { - a\overline{{s_{B} }} - \overline{{e_{1} }} } \right)\user2{s} + \overline{{varvec{e}_{2} }} + varvec{b}_{2} \overline{{s_{B} }} } \right) + varvec{\bar{r}}} \right)\bar{c}\;{\text{mod}}\;Q\;{\text{mod}}\;q = varvec{\bar{r}}\bar{c}\;{\text{mod}}\;Q\;{\text{mod}}\;q\), \(\overline{{t }_{2}}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}^{**}{\overline{c} }^{-1}={{{\varvec{a}}}_{2}}^{T}\overline{{\varvec{r}} }+(st-1)\times i-{{{\varvec{a}}}_{2}}^{T}\overline{{\varvec{r}} }\overline{c }{\overline{c} }^{-1}=({st}_{i}-1)\times i\), then \(i=(\overline{{t }_{2}}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}^{**}{\overline{c} }^{-1})/({st}_{i}-1)\). If \((\overline{{t }_{2}}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}^{**}{\overline{c} }^{-1})\) is divisible \({st}_{i}-1\), return \((\overline{{t }_{2}}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}^{**}{\overline{c} }^{-1})/({st}_{i}-1)\); otherwise, return \(\perp\).
Remark 4
If decryption succeeds, then the proof \({\pi}_{{st}_{i}}\) verifies, which entails that there exists \({{\varvec{r}}}_{{st}_{i}}^{*{\prime}}\), \({\overline{c} }{\prime}\) such that \({{{\varvec{a}}}_{1}}^{T}{{\varvec{r}}}_{{st}_{i}}^{*{\prime}}={\overline{c} }{\prime}{t}_{1} \text{mod}\;q\) and by Lemma 5.1 of (Pino et al. 2018), we have \(\frac{{{\varvec{r}}}_{{st}_{i}}^{*}}{\overline{c}} \text{mod}\;q=\frac{{{\varvec{r}}}_{{st}_{i}}^{*{\prime}}}{{\overline{c} }{\prime}} \text{mod}\;q\). If we multiply both sides of this equation by \(\overline{c }{\overline{c} }{\prime}\), we have that \({{\varvec{r}}}_{{st}_{i}}^{*}{\overline{c} }{\prime}={{\varvec{r}}}_{{st}_{i}}^{*{\prime}}\overline{c} \text{mod}\;q\). From which we get \({{{\varvec{a}}}_{1}}^{T}{{\varvec{r}}}_{{st}_{i}}^{*}=\overline{c}{t }_{{st}_{i}, 1}\), which entails that if \({{\varvec{t}}}_{{st}_{i}}=\left[\begin{array}{c}{t}_{{st}_{i}, 1}\\ {t}_{{st}_{i},2}\end{array}\right]\) is a well-formed commitment the identity returned by the Open algorithm will be its message.
Algorithm 9 Revoke(\(i\), \({un}_{i}\))
If the signer \(i\) is traceable, then it deletes its unique number \({un}_{i}\) from the registry CH. Next, it samples a new PRSK \({{\varvec{k}}}{\prime}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2}\), computes \({{{\varvec{a}}}_{3}}^{T}{{\varvec{k}}}{\prime}={\overline{{b }_{1}}}^{\boldsymbol{{\prime}}}\in {\mathbb{R}}_{q}\) and uses the rest of the RSKs to compute the new RP set \({f}_{j}{\prime}\left(x\right)=\prod_{i=1}^{N-1}(x-{r}_{i})+{k}_{j}\) (\(j\in [0\), \(2)\)). Finally, the GM publishes the new RP set \({f}_{j}{\prime}\left(x\right)\) and the new RPK \({\overline{{b }_{1}}}^{\boldsymbol{{\prime}}}\).
The process of NIZKPoK
We show a NIZKPoK protocol called \({\text{N}\text{I}\text{Z}\text{K}\text{P}\text{o}\text{K}}^{\text{L}\text{C}\text{G}\text{S}-\text{U}\text{C}\text{S}\text{L}}\) that our scheme relies on. The details of the protocol are described as follows:
Let \({\mathbb{R}}\) be a polynomial ring \({\mathbb{Z}}[x]/({x}^{d}+1)\) and \(\lambda\), \(\kappa\), \(q\), \(Q\), \(\delta\), \(\sigma \ge \sqrt{2d}\times \omega \left(\sqrt{\text{log}\,(2d)}\right)\), \({\sigma}_{r}=\alpha \| {{\varvec{r}}}_{{st}_{i}}c\| =\alpha \sqrt{3d}\kappa\), \({\sigma}_{{s}_{\text{1,2}}}=\alpha \| {{\varvec{s}}}_{i,1}c\| =\alpha 2\sqrt{2d}\sigma \kappa\), \({\sigma}_{{s}_{3}}=\alpha \| ({{\varvec{s}}}_{i,3}-[{{\varvec{r}}}_{{st}_{i}}|{{\varvec{r}}}_{{st}_{i}}{\prime}]{{\varvec{s}}}_{i,2})c\| =\alpha (\sqrt{3d}\kappa +\alpha 4\sqrt{3d}\sigma d\kappa )\), \({\sigma}_{B}=\alpha \| {{\varvec{r}}}_{{st}_{i},B}c\| =\alpha 2\sqrt{2d}\kappa\), \({\sigma}_{k}=\alpha \| {\varvec{k}}c\| =\alpha \sqrt{2d}\kappa\) be public parameters. Given identity’s commitment \({{\varvec{t}}}_{{st}_{i}}\), \({{\varvec{t}}}_{{st}_{i}}{\prime}\) and public polynomials \({{\varvec{a}}}_{1}\), \({{\varvec{a}}}_{2}\), \({{\varvec{a}}}_{3}\), \({\varvec{v}}\), \(u\), \({\varvec{B}}\), \({{\varvec{y}}}_{{st}_{i}}\), \(\overline{{b }_{1}}\), \({scp}_{{st}_{i}}\), \({nym}_{{st}_{i}}\). Assume that the prover \(\mathcal{P}\) has a set of secrets (\(i\), \({{\varvec{s}}}_{i,1}\), \({{\varvec{s}}}_{i,2}\), \({{\varvec{s}}}_{i,3}\), \({{\varvec{r}}}_{{st}_{i}}\),\({{\varvec{r}}}_{{st}_{i}}{\prime}\), \({{\varvec{r}}}_{{st}_{i},B}\), \({\varvec{k}}\)), where \(i\) is the signer’s identity, (\({{\varvec{s}}}_{i,1}\), \({{\varvec{s}}}_{i,2}\), \({{\varvec{s}}}_{i,3}\), \({{\varvec{r}}}_{{st}_{i}}\),\({{\varvec{r}}}_{{st}_{i}}{\prime}\), \({{\varvec{r}}}_{{st}_{i},B}\), \({\varvec{k}}\)) is a set of secret vectors. The purpose of prover \(\mathcal{P}\) is to convince the verifier \(\mathcal{V}\) that \({{{\varvec{v}}}_{{st}_{i}}}^{T}\times {({{\varvec{s}}}_{i,1}, {{\varvec{s}}}_{i,2},{{\varvec{s}}}_{i,3}-\left[{{\varvec{r}}}_{{st}_{i}}| {{\varvec{r}}}_{{st}_{i}}{\prime}\right]{{\varvec{s}}}_{i,2})}^{T}=u\), \({\varvec{B}}{{\varvec{r}}}_{{st}_{i},B}={{\varvec{y}}}_{{st}_{i}}\), \({{{\varvec{a}}}_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\), \({{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}{{\varvec{s}}}_{i,3}={nym}_{{st}_{i}}\). Prover \(\mathcal{P}\) and verifier \(\mathcal{V}\) perform the following protocol:
Prover \(\mathcal{P}\) samples \(({{\varvec{y}}}_{r}\),\({{\varvec{y}}}_{r}{\prime})\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\times {\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\), \(({{\varvec{y}}}_{{s}_{1}}\), \({{\varvec{y}}}_{{s}_{2}})\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\times {\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\), \({{\varvec{y}}}_{{s}_{3}}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{{s}_{3}}}\), \({{\varvec{y}}}_{B}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{8}, {\sigma}_{B}}\), \({{\varvec{y}}}_{k}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{k}}\), computes \({w}_{1}={{{\varvec{a}}}_{1}}^{T}{{\varvec{y}}}_{r}\), \({w}_{1}{\prime}={{{\varvec{a}}}_{1}}^{T}{{\varvec{y}}}_{r}{\prime}\), \({w}_{2}=\delta {{{\varvec{a}}}_{2}}^{T}{{\varvec{y}}}_{r}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{y}}}_{r}{\prime}\), \({w}_{{s}_{1}}={{{\varvec{a}}}_{3}}^{T}{{\varvec{y}}}_{{s}_{1}}\), \({w}_{{s}_{2}}=({{{\varvec{b}}}_{1}}^{T}+[{t}_{{st}_{i},2}| {t}_{{st}_{i},2}{\prime}]){{\varvec{y}}}_{{s}_{2}}\), \({w}_{{s}_{3}}={{{\varvec{a}}}_{2}}^{T}{{\varvec{y}}}_{{s}_{3}}\), \({{\varvec{w}}}_{B}={\varvec{B}}{{\varvec{y}}}_{B}\in {\mathbb{R}}_{Q}^{4}\times {\mathbb{R}}_{q}\), \({w}_{k}={{{\varvec{a}}}_{3}}^{T}{{\varvec{y}}}_{k}\), \(c={H}_{1}({w}_{1}\), \({w}_{1}{\prime}\), \({w}_{2}\), \({w}_{{s}_{1}}\), \({w}_{{s}_{1}}+{w}_{{s}_{2}}+{w}_{{s}_{3}}\), \({{\varvec{w}}}_{B}\), \({w}_{k}\), \(M\)), \({{\varvec{z}}}_{1}={{\varvec{r}}}_{{st}_{i}}c+{{\varvec{y}}}_{r}\), \({{\varvec{z}}}_{2}={{\varvec{r}}}_{{st}_{i}}{\prime}c+{{\varvec{y}}}_{r}^{\boldsymbol{{\prime}}}\), \({{\varvec{z}}}_{{s}_{1}}={{\varvec{s}}}_{i,1}c+{{\varvec{y}}}_{{s}_{1}}\), \({{\varvec{z}}}_{{s}_{2}}={{\varvec{s}}}_{i,2}c+{{\varvec{y}}}_{{s}_{2}}\), \({{\varvec{z}}}_{{s}_{3}}=({{\varvec{s}}}_{i,3}-\left[{{\varvec{r}}}_{{st}_{i}}| {{\varvec{r}}}_{{st}_{i}}{\prime}\right]{{\varvec{s}}}_{i,2})c+{{\varvec{y}}}_{{s}_{3}}\), \({{\varvec{z}}}_{B}={{\varvec{r}}}_{{st}_{i},B}c+{{\varvec{y}}}_{B}\), \({{\varvec{z}}}_{k}={\varvec{k}}c+{{\varvec{y}}}_{k}\), performs rejection sampling \(\text{R}\text{e}\text{j}(({{\varvec{z}}}_{1}\),\({{\varvec{z}}}_{2})\),\(({{\varvec{r}}}_{{st}_{i}}c\),\({{\varvec{r}}}_{{st}_{i}}{\prime}c)\), \({\sigma}_{r}\), \(3d)\), \(\text{R}\text{e}\text{j}(({{\varvec{z}}}_{{s}_{1}}\),\({{\varvec{z}}}_{{s}_{2}})\),\(({{\varvec{s}}}_{i,1}c\),\({{\varvec{s}}}_{i,2}c)\),\({\sigma}_{{s}_{\text{1,2}}}\), \(2d)\), \(\text{R}\text{e}\text{j}({{\varvec{z}}}_{{s}_{3}}\),\(({{\varvec{s}}}_{i,3}-\left[{{\varvec{r}}}_{{st}_{i}}| {{\varvec{r}}}_{{st}_{i}}{\prime}\right]{{\varvec{s}}}_{i,2})c\), \({\sigma}_{{s}_{3}}\), \(3d)\), \(\text{R}\text{e}\text{j}({{\varvec{z}}}_{B}\), \({{\varvec{r}}}_{{st}_{i},B}c\),\({\sigma}_{B}\),\(8d)\), \(\text{R}\text{e}\text{j}({{\varvec{z}}}_{k}\), \({\varvec{k}}c\),\({\sigma}_{k}\), \(2d)\), and sends \(({{\varvec{z}}}_{1}\),\({{\varvec{z}}}_{2}\), \({{\varvec{z}}}_{{s}_{1}}\), \({{\varvec{z}}}_{{s}_{2}}\),\({{\varvec{z}}}_{{s}_{3}}\),\({{\varvec{z}}}_{B}\),\({{\varvec{z}}}_{k}\), \(M\),\(c)\) to Verifier \(\mathcal{V}\).
Verifier \(\mathcal{V}\) checks \(\Vert {{\varvec{z}}}_{1}\Vert \le 2{\sigma}_{r}\sqrt{3d}\), \(\Vert {{\varvec{z}}}_{2}\Vert \le 2{\sigma}_{r}\sqrt{3d}\), \(\Vert {{\varvec{z}}}_{{s}_{1}}\Vert \le 2{\sigma}_{{s}_{\text{1,2}}}\sqrt{2d}\), \(\Vert {{\varvec{z}}}_{{s}_{2}}\Vert \le 2{\sigma}_{{s}_{\text{1,2}}}\sqrt{2d}\),\(\Vert {{\varvec{z}}}_{{s}_{3}}\Vert \le 2{\sigma}_{{s}_{3}}\sqrt{3d}\), \(\Vert {{\varvec{z}}}_{B}\Vert \le 4{\sigma}_{B}\sqrt{2d}\), \(\Vert {{\varvec{z}}}_{k}\Vert \le 2{\sigma}_{k}\sqrt{2d}\), computes \({w}_{1}={{{\varvec{a}}}_{1}}^{T}{{\varvec{z}}}_{1}-{t}_{{st}_{i}, 1}c\), \({w}_{1}{\prime}={{{\varvec{a}}}_{1}}^{T}{{\varvec{z}}}_{2}-{t}_{{st}_{i}, 1}{\prime}c\), \({w}_{2}=\delta {{{\varvec{a}}}_{2}}^{T}{{\varvec{z}}}_{1}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{z}}}_{2}-\left(\delta {t}_{{st}_{i}, 2}-{t}_{{st}_{i}, 2}{\prime}\right)c\), \({w}_{{s}_{1}}={{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}{{\varvec{z}}}_{{s}_{1}}-{nym}_{{st}_{i}}\times c\), \({w}_{{s}_{1}}+{w}_{{s}_{2}}+{w}_{{s}_{3}}={{{\varvec{v}}}_{{st}_{i}}}^{T}\times {\left[{{{\varvec{z}}}_{{s}_{1}}}^{T}\left| {{{\varvec{z}}}_{{s}_{2}}}^{T}\right| {{{\varvec{z}}}_{{s}_{3}}}^{T}\right]}^{T}-u\times c\), \({{\varvec{w}}}_{B}={\varvec{B}}{{\varvec{z}}}_{B}-{{\varvec{y}}}_{{st}_{i}}c\in {\mathbb{R}}_{Q}^{4}\times {\mathbb{R}}_{q}\), \({w}_{k}={{{\varvec{a}}}_{3}}^{T}{{\varvec{z}}}_{k}-\overline{{b }_{1}}c\), and checks whether \(c={H}_{1}({w}_{1}\), \({w}_{1}{\prime}\), \({w}_{2}\), \({w}_{{s}_{1}}\), \({w}_{{s}_{1}}+{w}_{{s}_{2}}+{w}_{{s}_{3}}\), \({{\varvec{w}}}_{B}\), \({w}_{k}\), \(M\)) or not. If all of the above conditions hold, then return 1; otherwise, return 0.
Remark 5
Here is a simple correctness analysis. For \({w}_{1}={{{\varvec{a}}}_{1}}^{T}{{\varvec{z}}}_{1}-{t}_{{st}_{i}, 1}c\), \({{{\varvec{a}}}_{1}}^{T}{{\varvec{z}}}_{1}-{t}_{1}c={{{\varvec{a}}}_{1}}^{T}\left({{\varvec{r}}}_{{st}_{i}}c+{{\varvec{y}}}_{r}\right)-{t}_{{st}_{i}, 1}c={t}_{{st}_{i}, 1}c+{{{\varvec{a}}}_{1}}^{T}{{\varvec{y}}}_{r}-{t}_{{st}_{i}, 1}c={{{\varvec{a}}}_{1}}^{T}{{\varvec{y}}}_{r}={w}_{1}\); for \(\Vert {{\varvec{z}}}_{1}\Vert \le 2{\sigma}_{r}\sqrt{3d}\), because \({{\varvec{z}}}_{1}={{\varvec{r}}}_{{st}_{i}}c+{{\varvec{y}}}_{r} \text{mod}\;q\), where \({{\varvec{y}}}_{r}\) obeys the \({\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\) distribution. According to the rejection sampling algorithm (Lyubashevsky 2012), it can be known that the distribution satisfied by the output \({{\varvec{z}}}_{1}={{\varvec{r}}}_{{st}_{i}}c+{{\varvec{y}}}_{r} \text{mod}\;q\) with the probability of min \((1\), \(\frac{{\mathcal{D}}_{{\mathbb{R}}^{3},{\sigma}_{r}}\left({{\varvec{z}}}_{1}\right)}{M{\mathcal{D}}_{{\mathbb{R}}^{3},{\sigma}_{r},{{\varvec{r}}}_{{st}_{i}}c}\left({{\varvec{z}}}_{1}\right)})\) is statistically close to the \({\mathcal{D}}_{{\mathbb{R}}^{3},{\sigma}_{r}}\) distribution (statistical distance is \({2}^{-100}/M\), where \(M\approx 3\)), so according to Lemma 1, the signature \({{\varvec{z}}}_{1}\) satisfies \(\Vert {{\varvec{z}}}_{1}\Vert \le 2{\sigma}_{r}\sqrt{3d}\) with a probability of \(1-{2}^{-100}\). The other formulas can be proved to be correct in the same way.
Figure 2 describes the process of NIZKPoK. \({\text{N}\text{I}\text{Z}\text{K}\text{P}\text{o}\text{K}}^{\text{L}\text{C}\text{G}\text{S}-\text{U}\text{C}\text{S}\text{L}}\) satisfies the correctness, the honest-verifier zero-knowledge, and the special soundness. Lemma 4.1 of Ref. Pino et al. (2018) gives a detailed proof of NIZKPoK. We do not describe it here (we provided a simple example in Sect. “Security proofs for NIZKPoK” to illustrate this). The zero-knowledge proof process of the linked group signature is the same as above; the difference is that the Gaussian parameters \({\sigma}_{r}=\alpha \| \overline{{\varvec{r}} }c\| =\alpha ({st}_{i}-1)\sqrt{3d}\kappa\), \({\sigma}_{{s}_{3}}=\alpha \| ({{\varvec{s}}}_{i,3}-[\overline{{\varvec{r}} }|\overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}]{{\varvec{s}}}_{i,2})c\| =\alpha (\sqrt{3d}\kappa +\alpha 4({st}_{i}-1)\sqrt{3d}\sigma d\kappa )\), \({\sigma}_{B}=\alpha \| \overline{{{\varvec{r}} }_{B}}c\| =\alpha ({st}_{i}-1)2\sqrt{2d}\kappa\), and partial signature information \({w}_{{s}_{2}}=({{{\varvec{b}}}_{1}}^{T}+[\overline{{t }_{2}}| \overline{{t }_{2}{\prime}}]){{\varvec{y}}}_{{s}_{2}}\), \({{\varvec{z}}}_{1}=\overline{{\varvec{r}} }c+{{\varvec{y}}}_{r}\), \({{\varvec{z}}}_{2}=\overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}c+{{\varvec{y}}}_{r}^{\boldsymbol{{\prime}}}\), \({{\varvec{z}}}_{{s}_{3}}=({{\varvec{s}}}_{i,3}-[\overline{{\varvec{r}} }|\overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}]{{\varvec{s}}}_{i,2})c+{{\varvec{y}}}_{{s}_{3}}\), \({{\varvec{z}}}_{B}=\overline{{{\varvec{r}} }_{B}}c+{{\varvec{y}}}_{B}\), which will increase the signature length.
Correctness analysis and security proof
In this section, the correctness analysis of the Open algorithm, formal security proofs, informal security analyses, security proof for NIZKPoK, and a security analysis using the Scyther tool about our scheme are given, respectively.
The correctness analysis of the open algorithm
According to Lemma 3.1 of Ref. Lyubashevsky and Neven (2017), let \(c\) be the challenge used in \({\pi}_{{st}_{i}}\), sample \({c}{\prime}\stackrel{\boldsymbol{\$}}{\leftarrow }\mathcal{C}\), set \(\overline{c }=c-{c}{\prime}\). There must be \({s}_{{st}_{i}, B}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({e}_{{st}_{i},1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), and \({{\varvec{e}}}_{{st}_{i}, 2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\) satisfying \(\left\| {\varvec{r}_{{st_{i} }}^{*} } \right\|_{\infty } = \left\| {\left( {\varvec{d}_{{st_{i} }} - h_{{st_{i} }} \varvec{s}} \right)\bar{c}} \right\|_{\infty } ~{\text{mod}}~Q = \left\| {q\bar{c}\left[ {\left( { - as_{{st_{i} ,~B}} - e_{{st_{i} ,1}} } \right)\varvec{s} + \varvec2{e}_{{st_{i} ,~2}} + \varvec2{b}_{2} s_{{st_{i} ,~B}} } \right] + \bar{c}\varvec{r~}{\text{mod~}}Q} \right\|_{\infty } < \frac{Q}{{2{\hat{\mathcal{C}}}}} = \frac{Q}{{2\kappa }}\), where \(\widehat{\mathcal{C}}=\underset{\overline{c }\in \overline{\mathcal{C}}}{\text{max} }{\Vert \overline{c}\Vert }_{1}=\underset{c-{c}{\prime}\in \overline{\mathcal{C}}}{\text{max} }{\Vert c-{c}{\prime}\Vert }_{1}\). If \(\Sigma\) is the aggregated signature, then \({\Vert {{\varvec{r}}}^{\boldsymbol{*}}\Vert }_{\infty }={\Vert \left(\overline{{\varvec{d}} }-\overline{h}{\varvec{s} }\right)\overline{c}\Vert }_{\infty } \text{mod}\;Q={\Vert (q(\left(-a\overline{{s }_{B}}-\overline{{e }_{1}}\right){\varvec{s}}+\overline{{{\varvec{e}} }_{2}}+{{\varvec{b}}}_{2}\overline{{s }_{B}})+\overline{{\varvec{r}} })\overline{c}\text{mod}\;Q\Vert }_{\infty }<\frac{Q}{2\widehat{\mathcal{C}}}=\frac{Q}{2\kappa }\). Besides, \(\varvec{r}_{{st_{i} }}^{{**}} = \varvec{r}_{{st_{i} }}^{*} {\text{~mod}}~Q~{\text{mod}}~q = \left( {\varvec{d}_{{st_{i} }} - h_{{st_{i} }} \varvec{s}} \right)\bar{c}~{\text{mod}}~Q~{\text{mod}}~q = \left( {q\left( {\left( { - as_{{st_{i} ,~B}} - e_{{st_{i} ,1}} } \right)\varvec{s} + \user2{e}_{{st_{i} ,~2}} + \varvec{b}_{2} s_{{st_{i} ,~B}} } \right) + \varvec{r}} \right)\bar{c}\varvec{~}{\text{mod~}}Q~{\text{mod}}~q = \varvec{r}_{{st_{i} }} \bar{c}\varvec{~}{\text{mod~}}Q~{\text{mod}}~q\), \({t}_{2}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}_{{st}_{i}}^{**}{\overline{c} }^{-1}={{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}_{{st}_{i}}+i-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}_{{st}_{i}}\overline{c }{\overline{c} }^{-1}=i\). If \(\Sigma\) is an aggregated signature, \(\varvec{r}^{{\boldsymbol{**}}} = \varvec{r}^{\boldsymbol{*}} {\text{~mod}}~Q~{\text{mod}}~q = \left( {\bar{\varvec{d}} - \bar{h}\varvec{s}} \right)\bar{c}~{\text{mod}}~Q~{\text{mod}}~q = \left( {q\left( {\left( { - a\overline{{s_{B} }} - \overline{{e_{1} }} } \right)\varvec{s} + \overline{{\varvec{e}_{2} }} + \varvec{b}_{2} \overline{{s_{B} }} } \right) + {\bar{\varvec{r}}}} \right)\bar{c}{\text{mod~}}Q~{\text{mod}}~q = \varvec{\bar{r}}\bar{c}{\text{mod~}}Q~{\text{mod}}~q\), \(\overline{{t }_{2}}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}^{\boldsymbol{*}\boldsymbol{*}}{\overline{c} }^{-1}={{{\varvec{a}}}_{2}}^{T}\overline{{\varvec{r}} }+({st}_{i}-1)\times i-{{{\varvec{a}}}_{2}}^{T}\overline{{\varvec{r}} }\overline{c }{\overline{c} }^{-1}=({st}_{i}-1)\times i\), \(i=(\overline{{t }_{2}}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}^{\boldsymbol{*}\boldsymbol{*}}{\overline{c} }^{-1})/({st}_{i}-1)\).
Security proofs and analysis for linkability, sequential linkability, revocability, anonymity, traceability, EUF-CMA, and non-frameability
This section proves and analyzes the security of our scheme from both informal and formal perspectives.
Informal security analysis
To prevent adversaries from distinguishing traceable and non-traceable users via statistical analysis, based on the nature of the MLWE problem, the KOE re-randomization guarantees that re-randomized public keys are computationally statistically indistinguishable. Under the MLWE assumption, no polynomial-time adversary can distinguish the two public key types through frequency analysis, moment statistics, or distribution fitting. This oblivious classification preserves privacy and avoids indirect leakage.
Our informal security analyses include linkability security, sequential linkability security, and revocability security.
Linkability security: For a signer with identity \(i\), the linkability security of our scheme depends on the formula \({{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}{{\varvec{s}}}_{i,3}={nym}_{{st}_{i}}\), and solves \({{\varvec{s}}}_{i,3}\) by \({{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}\) and \({nym}_{{st}_{i}}\), which is equivalent to solving the MSIS problem. Since MSIS is a difficult problem, \({{\varvec{s}}}_{i,3}\) cannot be solved by \({{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}\) and \({nym}_{{st}_{i}}\) to compromise the security of linkability.
Sequential linkability security: For a group signer with identity \(i\), the sequential linkability security of our scheme depends on \({n}_{{st}_{i}}={H}_{3}({{\varvec{s}}}_{i,3}\), \(0| {st}_{i})\). The difficulty of solving \({{\varvec{s}}}_{i,3}\) through \({n}_{{st}_{i}}\) and \(0| {st}_{i}\) is equivalent to solving the one-way hash function problem. Since the hash function is one-way, it is impossible to solve \({{\varvec{s}}}_{i,3}\). through \({n}_{{st}_{i}}\) and \(0| {st}_{i}\).
Revocability security: For a group signer with identity \(i\), the revocability security of our scheme depends on the formula \({{{\varvec{a}}}_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\), \({\varvec{k}}=\left[\begin{array}{c}{f}_{0}({r}_{i})\\ {f}_{1}({r}_{i})\end{array}\right]\). The difficulty of solving \({\varvec{k}}\) through \({{{\varvec{a}}}_{3}}^{T}\) and \(\overline{{b }_{1}}\) is equivalent to solving the \({\text{M}\text{S}\text{I}\text{S}}_{q,\text{1,2},\beta }\) problem with \(\beta =4{\sigma}_{k}\sqrt{2d}+2\kappa \sqrt{2d}\). Since \({\text{M}\text{S}\text{I}\text{S}}_{q,\text{1,2},\beta }\) is a difficult problem; it is impossible to solve \({\varvec{k}}\) through \({{{\varvec{a}}}_{3}}^{T}\) and \(\overline{{b }_{1}}\).
Besides, assuming that the adversary \(\mathcal{A}\) can forge a transcript (\({{{\varvec{z}}}_{k}}^{\boldsymbol{{\prime}}}\), \({c}{\prime}\)), so that \({{{\varvec{a}}}_{3}}^{T}{{\varvec{z}}}_{k}-\overline{{b }_{1}}c={{{\varvec{a}}}_{3}}^{T}{{{\varvec{z}}}_{k}}^{\boldsymbol{{\prime}}}-\overline{{b }_{1}}{c}{\prime}\), that is, \({{{\varvec{a}}}_{3}}^{T}{{\varvec{z}}}_{k}-{{{\varvec{a}}}_{3}}^{T}{\varvec{k}}c={{{\varvec{a}}}_{3}}^{T}{{{\varvec{z}}}_{k}}^{\boldsymbol{{\prime}}}-{{{\varvec{a}}}_{3}}^{T}{\varvec{k}}{c}{\prime}\), that is, \({{{\varvec{a}}}_{3}}^{T}\left({{\varvec{z}}}_{k}-{{{\varvec{z}}}_{k}}^{\boldsymbol{{\prime}}}-{\varvec{k}}c+{\varvec{k}}{c}{\prime}\right)=0\). Because \(\Vert {{\varvec{z}}}_{k}\Vert \le 2{\sigma}_{k}\sqrt{2d}\), \(\Vert {{{\varvec{z}}}_{k}}^{\boldsymbol{{\prime}}}\Vert \le 2{\sigma}_{k}\sqrt{2d}\), \(\Vert {\varvec{k}}\Vert \le \sqrt{2d}\), \(\Vert c\Vert \le \sqrt{\kappa }\), \(\Vert {c}{\prime}\Vert \le \sqrt{\kappa }\), then \(\Vert {{\varvec{z}}}_{k}-{{{\varvec{z}}}_{k}}^{\boldsymbol{{\prime}}}-{\varvec{k}}c+{\varvec{k}}{c}{\prime}\Vert \le 4{\sigma}_{k}\sqrt{2d}+2\kappa \sqrt{2d}\). Then challenger \(\mathcal{C}\) can solve the \({\text{M}\text{S}\text{I}\text{S}}_{q,\text{1,2},\beta }\) problem with \(\beta =4{\sigma}_{k}\sqrt{2d}+2\kappa \sqrt{2d}\) with a non-negligible probability.
To resist reordering, omission, and selective disclosure attacks against sequential linkability, the scheme integrates three cryptographic protections. First, a one-way hash chain enforces strict chronological ordering, where each sequential value depends on the previous state, preventing adversarial reordering. Second, unique sequential values are publicly verified via the append-only bulletin board to prevent replay, omission, or duplication. Third, the NIZKPoK proof commits to the complete set of linked signatures, so any attempt to omit, hide, or reorder signatures will invalidate the proof. Consequently, the sequential integrity and authenticity of linked signatures are cryptographically guaranteed.
Formal security proofs
Our formal security proofs include anonymity and traceability/EUF-CMA/non-frameability.
Theorem 1
For any PPT adversary \(\mathcal{A}\), we let \({Adv}_{\mathcal{A}}^{hid}(\lambda )\) be the advantage that adversary \(\mathcal{A}\) is against the hiding of the commitment scheme (Baum et al. 2018). Let \({Adv}_{\mathcal{A}}^{ind-cpa}(\lambda )\) is the advantage that \(\mathcal{A}\) breaks the Indistinguishability under Chosen-Plaintext Attack (IND-CPA) of the verifiable encryption scheme (Lyubashevsky and Neven 2017). Then we prove that the advantage of adversary \(\mathcal{A}\) against the anonymity of our LCGS-UCSL is at most:
Proof
We use a succession of games to prove the anonymity of our scheme.
Game \({G}_{0}\): This game is the same as the definition of the anonymity experiment \({\text{E}\text{x}\text{p}}_{\mathcal{A}}^{an}({1}^{\lambda })\).
Game \({G}_{1}\): This game is the same as Game \({G}_{0}\), except that the simulator of the proof \(\pi\) is used when queried for \(\mathcal{O}{\text{C}\text{h}}_{b}({i}_{0}\), \({i}_{1}\),\(M)\). We know from honest-verifier zero-knowledge that this game is statistically indistinguishable from Game \({G}_{0}\). Then we have.
\(\left|{\text{A}\text{d}\text{v}}_{\mathcal{A}}^{{G}_{1}}(\lambda )-{\text{A}\text{d}\text{v}}_{\mathcal{A}}^{{G}_{0}}(\lambda )\right|\le {2}^{-\lambda }\).
Game \({G}_{2}\): This game is the same as Game \({G}_{1}\) except that the commitment (\({\varvec{t}}\), \({{\varvec{t}}}^{\boldsymbol{{\prime}}}\)) is replaced with a commitment of 0 when queried for \(\mathcal{O}{Ch}_{b}({i}_{0}\), \({i}_{1}\),\(M)\). This game is still indistinguishable from Game 1 due to the hiding of the commitment (Baum et al. 2018). We have.
\(\left|{\text{A}\text{d}\text{v}}_{\mathcal{A}}^{{G}_{2}}(\lambda )-{\text{A}\text{d}\text{v}}_{\mathcal{A}}^{{G}_{1}}(\lambda )\right|\le 2{\text{A}\text{d}\text{v}}_{\mathcal{A}}^{hid}(\lambda )\).
Game \({G}_{3}\): This game is the same as Game \({G}_{2}\) except that the verifiable ciphertext \(({\varvec{d}}\),\(h)\) is replaced with an encryption of 0. Since the verifiable encryption scheme (Lyubashevsky and Neven 2017) achieves the IND-CPA, game \({G}_{3}\) is indistinguishable from Game \({G}_{2}\). We have.
\(\left|{\text{A}\text{d}\text{v}}_{\mathcal{A}}^{{G}_{3}}(\lambda )-{\text{A}\text{d}\text{v}}_{\mathcal{A}}^{{G}_{2}}(\lambda )\right|\le {\text{A}\text{d}\text{v}}_{\mathcal{A}}^{ind-cpa}(\lambda )\).
Note that the signature output in Game \({G}_{3}\) is independent of identities. Therefore, the probability that the adversary \(\mathcal{A}\) outputs \(b={b}{\prime}\) is 1/2. This means that the advantage of the adversary \(\mathcal{A}\) against the anonymity of our LCGS-UCSL scheme is at most \(2{\text{A}\text{d}\text{v}}_{\mathcal{A}}^{hid}(\lambda )+{\text{A}\text{d}\text{v}}_{\mathcal{A}}^{ind-cpa}(\lambda )+{2}^{-\lambda }\), which is negligible. □
We will prove traceability/EUF-CMA/non-frameability in two steps. We will first prove that an adversary \(\mathcal{A}\) cannot distinguish between the regular traceability/EUF-CMA/non-frameability game and the traceability/EUF-CMA/non-frameability game in which the setup algorithm has been replaced by \({\text{G}\text{S}\text{e}\text{t}\text{u}\text{p}}^{*}\) which we define below. We will then prove that a challenger \(\mathcal{B}\) can extract an MSIS solution from an adversary \(\mathcal{A}\) who succeeds in producing a forgery in the traceability/EUF-CMA/non-frameability game with \({\text{G}\text{S}\text{e}\text{t}\text{u}\text{p}}^{*}\).
\({\text{G}\text{S}\text{e}\text{t}\text{u}\text{p}}^{*}\)(\({1}^{\uplambda }\)):
-
(1)
Sample \({i}^{*}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{Z}}_{q}\).
-
(2)
Sample \({{\varvec{a}}}_{1}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{3}\), \({{\varvec{a}}}_{2}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{3}\), \({{\varvec{a}}}_{3}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{2}\), \({\varvec{R}}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2\times 2}\), \(({{\varvec{s}}}_{{i}^{*},1}\),\({{\varvec{s}}}_{{i}^{*},2}\),\({{\varvec{s}}}_{{i}^{*},3})\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2}\times {S}_{1}^{2}\times {S}_{1}^{3}\), \(({a}^{\left(1\right)}\), \({a}^{(2)})\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{Q}\times {\mathbb{R}}_{Q}\).
-
(3)
Set \({{{\varvec{b}}}_{1}}^{T}={{{\varvec{a}}}_{3}}^{T}{\varvec{R}}\in {\mathbb{R}}_{q}^{1\times 2}\), and \(u=[{{{\varvec{a}}}_{3}}^{T}| {{{\varvec{b}}}_{1}}^{T}| {{{\varvec{a}}}_{1}}^{T}]\left[\begin{array}{c}{{\varvec{s}}}_{{i}^{*},1}\\ {{\varvec{s}}}_{{i}^{*},2}\\ {{\varvec{s}}}_{{i}^{*},3}\end{array}\right]\).
-
(4)
Set \(gpk=({{\varvec{a}}}_{1}\),\({{\varvec{a}}}_{2}\),\({{\varvec{a}}}_{3}\), \({a}^{\left(1\right)}\), \({a}^{(2)}\),\({{\varvec{b}}}_{1}-{i}^{*}{{\varvec{g}}}^{T}\),\(u)\).
-
(5)
For \(i\in {\mathbb{Z}}_{q}\backslash \{{i}^{*}\}\), sample \({{\varvec{s}}}_{i,3}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{3}\).
-
(6)
Sample \({{\varvec{s}}}_{i,1}\in {\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\), \({{\varvec{s}}}_{i,2}\in {\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\) s.t
\([{{{\varvec{a}}}_{3}}^{T}| {{{\varvec{b}}}_{1}}^{T}+(i-{i}^{*}){{\varvec{g}}}^{T}]\left[\begin{array}{c}{{\varvec{s}}}_{i,1}\\ {{\varvec{s}}}_{i,2}\end{array}\right]=u-{{{\varvec{a}}}_{2}}^{T}{{\varvec{s}}}_{i,3}\), where \({{\varvec{g}}}^{T}=[1 \lceil\sqrt{q}\rceil]\in {\mathbb{R}}_{q}^{1\times 2}\).
-
(7)
Set \({sk}_{i}=({{\varvec{s}}}_{i,1}\), \({{\varvec{s}}}_{i,2}\),\({{\varvec{s}}}_{i,3})\).
We consider the following advantages for an adversary \(\mathcal{A}\).
\({\text{A}\text{d}\text{v}}_{\mathcal{A}}^{trace}(\lambda )\): the advantage of adversary \(\mathcal{A}\) in the traceability/EUF-CMA/non-frameability game.
\({\text{A}\text{d}\text{v}}_{\mathcal{A}}^{trace*}(\lambda )\): the advantage of adversary \(\mathcal{A}\) in the traceability/EUF-CMA/non-frameability game, where GSetup is replaced with \({\text{G}\text{S}\text{e}\text{t}\text{u}\text{p}}^{*}\).
\({\text{A}\text{d}\text{v}}_{\mathcal{A}}^{NTRU}(\lambda )\): the advantage of adversary \(\mathcal{A}\) in solving the \({\text{N}\text{T}\text{R}\text{U}}_{q,r}\) problem.
\({\text{A}\text{d}\text{v}}_{\mathcal{A}}^{Decision-MSIS}(\lambda )\): the advantage of adversary \(\mathcal{A}\) in solving the Decision \({\text{M}\text{S}\text{I}\text{S}}_{q,\text{1,2},\sqrt{2d}}\) problem.
Theorem 2
The advantage of any PPT adversary \(\mathcal{A}\) against the traceability/EUF-CMA/non-frameability game of the group signature is at most:
Proof
We use a succession of games to prove the traceability/EUF-CMA/non-frameability of our scheme.
Game \({G}_{0}\): The challenger \(\mathcal{B}\) runs the group signature protocol honestly. It gives \({({sk}_{i})}_{i\in S}\) (for any arbitrary set \(S\subseteq [N]\)) as well as \(gmsk\) to adversary \(\mathcal{A}\) who has advantage \(\varepsilon\) in the traceability/EUF-CMA/non-frameability game.
Game \({G}_{1}\): Challenger \(\mathcal{B}\) samples \({{{\varvec{a}}}_{2}}^{T}\) as \([0| 1| f/g]\) where \(f\), \(g\in {\mathcal{D}}_{r}\). \({G}_{1}\) is indistinguishable from \({G}_{0}\) under the \({\text{N}\text{T}\text{R}\text{U}}_{q,r}\) assumption.
Game\({G}_{2}\): Challenger \(\mathcal{B}\) sets \({{{\varvec{b}}}_{1}}^{T}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{1\times 2}\). Note that if\({{{\varvec{b}}}_{1}}^{T}\ne {{{\varvec{a}}}_{3}}^{T}{\varvec{R}}\in {\mathbb{R}}_{q}^{1\times 2}\), \(\mathcal{C}\) can no longer use the MP12 trapdoor of \([{{{\varvec{a}}}_{3}}^{T}|{{{\varvec{b}}}_{1}}^{T}+i{{\varvec{g}}}^{T}]\) to sample secret keys for signer\(i\). To generate keys for\(i\), it will instead sample \({{\varvec{s}}}_{i,1}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\) and \({{\varvec{s}}}_{i,2}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\) and use the NTRU trapdoor on \({{\varvec{a}}}_{2}\) to sample\({{\varvec{s}}}_{i,3}\). This game will be computationally indistinguishable from the previous one based on the hardness of Decision \({\text{M}\text{S}\text{I}\text{S}}_{q,\text{1,2},\sqrt{2d}}\) problem.
Game \({G}_{3}\): Challenger \(\mathcal{B}\) replaces \({{{\varvec{b}}}_{1}}^{T}\) with \({{{\varvec{b}}}_{1}^{*}}^{T}={{{\varvec{b}}}_{1}}^{T}-{i}^{*}{{\varvec{g}}}^{T}\). Since \({{{\varvec{b}}}_{1}}^{T}\) is uniform; it is identical to the previous one.
Game \({G}_{4}\): Challenger \(\mathcal{B}\) sets \({{{\varvec{b}}}_{1}^{*}}^{T}={{{\varvec{a}}}_{3}}^{T}{\varvec{R}}-{i}^{*}{{\varvec{g}}}^{T}\). This game is computationally indistinguishable from the previous one based on the hardness of Decision \({\text{M}\text{S}\text{I}\text{S}}_{q,\text{1,2},\sqrt{2d}}\) problem.
Game \({G}_{5}\): \(\text{C}\text{h}\text{a}\text{l}\text{l}\text{e}\text{n}\text{g}\text{e}\text{r} \mathcal{B}\) sets \({{{\varvec{a}}}_{2}}^{T}\) as \([0| 1| {a}_{2}]\), with \({a}_{2}\leftarrow {\mathbb{R}}_{q}\) and uses the MP12 trapdoor of \([{{{\varvec{a}}}_{3}}^{T}|{{{\varvec{b}}}_{1}}^{T}+(i-{i}^{*}){{\varvec{g}}}^{T}]\) to sample secret keys for signer \(i\). This game is indistinguishable from the previous one under the \({\text{N}\text{T}\text{R}\text{U}}_{q,r}\) assumption.
Note that Game \({G}_{5}\) is the traceability/EUF-CMA/non-frameability game that uses \({\text{G}\text{S}\text{e}\text{t}\text{u}\text{p}}^{*}\) (simply by renaming \(({{\varvec{s}}}_{\text{0,1}}\),\({{\varvec{s}}}_{\text{0,2}}\),\({{\varvec{s}}}_{\text{0,3}})\) to \(({{\varvec{s}}}_{{i}^{*},1}\),\({{\varvec{s}}}_{{i}^{*},2}\),\({{\varvec{s}}}_{{i}^{*},3}))\), the result follows.
Theorem 3
Let \(\mathcal{A}\) be a PPT adversary with advantage \(\varepsilon\) in the traceability/EUF-CMA/non-frameability game with \({GSetup}^{*}\). Let \(h\) be a bound on the number of hash queries made by adversary \(\mathcal{A}\). Let \({\mathcal{B}}_{S}\ge \sqrt{{\left(8\kappa {\sigma}_{s}\sqrt{2d}+16\kappa {\sigma}_{s}d\sqrt{2d}\right)}^{2}+{\left(8\kappa {\sigma}_{{s}_{3}}\sqrt{3d}+32{\sigma}_{s}{\sigma}_{r}d\sqrt{3d}\right)}^{2}}+4{\kappa }^{2}\sqrt{{\left(2\sigma \sqrt{2d}+4d\sigma \sqrt{2d}\right)}^{2}+{\left(\sqrt{3d}\right)}^{2}.}\) There exists a challenger \(\mathcal{B}\) for the \({MSIS}_{q,1,5,{\mathcal{B}}_{S}}\) such that:
Proof
Formally, challenger \(\mathcal{B}\) is given a vector \({{\varvec{x}}}^{T}=[{x}_{1}\)|\({x}_{2}\)|\({x}_{3}\)|\({x}_{4}]\in {\mathbb{R}}_{q}^{4}\) and must outputs \({\varvec{y}}\) s.t \({{\varvec{x}}}^{T}{\varvec{y}}=0 \text{mod}\;q\) and \(\| {\varvec{y}}\| \le {B}_{S}\), w.l.o.g we consider \({{\varvec{x}}}^{T}=[{x}_{1}\)|\({x}_{2}\)|\({x}_{3}\)| 1 \(]\) instead, since with high probability one of the \({x}_{i}\) will have an inverse.
Challenger \(\mathcal{B}\) will set \({{{\varvec{a}}}_{1}}^{T}=[0\)|\(1\)|\({x}_{3}]\) and \({{{\varvec{a}}}_{3}}^{T}=[{x}_{1}\)|\({x}_{2}]\) during setup. Since \({x}_{1}\),\({x}_{2}\),\({x}_{3}\) are uniform in \({\mathbb{R}}_{q}\), this does not change the distribution of \({\text{G}\text{S}\text{e}\text{t}\text{u}\text{p}}^{*}\). When asked signature queries, challenger \(\mathcal{B}\) runs the signature algorithm honestly; when asked corrupt queries, challenger \(\mathcal{B}\) outputs the corresponding secret key. Suppose the adversary \(\mathcal{A}\) outputs a forgery \({\Sigma}_{{st}_{id}}=(M\), \({scp}_{{st}_{id}}\), \({nym}_{{st}_{id}}\), \({{\varvec{t}}}_{{st}_{id}}\),\({{\varvec{t}}}_{{st}_{id}}^{{\prime}}\), \({\pi}_{{st}_{id}}\),\({h}_{{st}_{id}}\),\({{\varvec{d}}}_{{st}_{id}}\), \({seq}_{{st}_{id}}\), \({st}_{id}\),\({un}_{id})\) by programming the random oracle with two different challenges, challenger \(\mathcal{B}\) will be able to extract \(\overline{{{\varvec{z}} }_{1}}\in {\mathbb{R}}^{3}\), \(\overline{id}\in {\mathbb{Z} }_{q}\), \(\overline{{{\varvec{z}} }_{2}}\in {\mathbb{R}}^{3}\), \(\overline{{{\varvec{z}} }_{s}}\in {\mathbb{R}}^{7}\), \(\overline{{{\varvec{z}} }_{B}}\in {\mathbb{R}}^{8}\), \(\overline{c }\in \overline{\mathcal{C} }\) such that:
such that \(\Vert \overline{{{\varvec{z}} }_{1}}\Vert \le 4{\sigma}_{r}\sqrt{3d}\wedge \Vert \overline{{{\varvec{z}} }_{2}}\Vert \le 4{\sigma}_{r}\sqrt{3d}\wedge \Vert \overline{{{\varvec{z}} }_{B}}\Vert \le 8{\sigma}_{B}\sqrt{2d}\wedge \Vert \overline{{{\varvec{z}} }_{{s}_{1}}}\Vert \le 4{\sigma}_{s}\sqrt{2d}\wedge \Vert \overline{{{\varvec{z}} }_{{s}_{1}}}\Vert \le 4{\sigma}_{s}\sqrt{2d}\wedge \Vert \overline{{{\varvec{z}} }_{{s}_{1}}}\Vert \le 4{\sigma}_{{s}_{3}}\sqrt{3d}\), with \(\overline{{{\varvec{z}} }_{s}}=(\overline{{{\varvec{z}} }_{{s}_{1}}}\), \(\overline{{{\varvec{z}} }_{{s}_{2}}}\), \(\overline{{{\varvec{z}} }_{{s}_{3}}})\). Using the General Forking Lemma of Bellare and Neven (2006), challenger \(\mathcal{B}\) will be able to do this with probability at least \(\varepsilon (\frac{\varepsilon }{h}-{2}^{-\lambda })\). Let \((\widetilde{{\varvec{r}}}\), \(\widetilde{c})=\text{D}\text{e}\text{c}(h\),\({\varvec{d}})\), by soundness of the verifiable encryption scheme, with overwhelming probability \(\widetilde{{\varvec{r}}}\overline{c }=\overline{{{\varvec{z}} }_{1}}\widetilde{c}\) over the integers, which implies that \(\text{O}\text{p}\text{e}\text{n}({\Sigma}_{{st}_{id}})\in {\mathbb{Z}}_{q}\), i.e., the forgery opens to an identity in \({\mathbb{Z}}_{q}\) and not \(\perp\). Since \({i}^{*}\) is taken uniformly at random in \({\text{G}\text{S}\text{e}\text{t}\text{u}\text{p}}^{*}\), \(\Sigma\) will open to this identity with probability \(1/q\). Suppose that \(\Sigma\) opens to \({i}^{*}\). Then.
If we multiply the third equation by \(\overline{c }\) and replace \(\overline{c }\left[{t}_{{st}_{{i}^{*}},2}| {t}_{{st}_{{i}^{*}},2}{\prime}\right]\), we get: \(\left[\overline{c}{{{\varvec{a}} }_{3}}^{T}\left|\overline{c}{{{\varvec{b}} }_{1}}^{T}+\left[{{{\varvec{a}}}_{2}}^{T}\overline{{{\varvec{z}} }_{1}}| {{{\varvec{a}}}_{2}}^{T}\overline{{{\varvec{z}} }_{2}}\right]\right| {{{\varvec{a}}}_{2}}^{T}\right]\overline{{{\varvec{z}} }_{s}}={\overline{c} }^{2}u\). Let \(\widetilde{{\varvec{z}}}=\left[\begin{array}{c}\overline{c }\overline{{{\varvec{z}} }_{{s}_{1}}}+{\varvec{R}}\overline{c }\overline{{{\varvec{z}} }_{{s}_{2}}}\\ \overline{c }\overline{{{\varvec{z}} }_{{s}_{3}}}+[\overline{{{\varvec{z}} }_{1}}| \overline{{{\varvec{z}} }_{2}}]\overline{{{\varvec{z}} }_{{s}_{2}}}\end{array}\right]\), then \(\left[{{{\varvec{a}}}_{3}}^{T}| {{{\varvec{a}}}_{2}}^{T}\right]\widetilde{{\varvec{z}}}={\overline{c} }^{2}u\). Since adversary \(\mathcal{A}\) has to output a valid forgery, this means that he/she has never obtained the key \({sk}_{{i}^{*}}\), we can thus consider that \({{\varvec{s}}}_{{i}^{*}}\) was sampled after receiving the forgery, conditioned on \([{{{\varvec{a}}}_{3}}^{T}| {{{\varvec{b}}}_{1}}^{T}| {{{\varvec{a}}}_{2}}^{T}]{{\varvec{s}}}_{{i}^{*}}=u\). Let \({{\varvec{s}}}^{\boldsymbol{*}}=[{{\varvec{s}}}_{{i}^{*},1}+{\varvec{R}}{{\varvec{s}}}_{{i}^{*},2}| {{\varvec{s}}}_{{i}^{*},3}]\), the probability that \({\overline{c} }^{2}{{\varvec{s}}}^{\boldsymbol{*}}=\widetilde{{\varvec{z}}}\) is negligible. Finally, we have a solution \(\widetilde{{\varvec{z}}}-{\overline{c} }^{2}{{\varvec{s}}}^{\boldsymbol{*}}\) to the MSIS problem defined by \([{{{\varvec{a}}}_{3}}^{T}| {{{\varvec{a}}}_{2}}^{T}]\). Using the bounds on the extracted values and the distribution of \({{\varvec{s}}}^{\boldsymbol{*}}\), we have the following bound on the norm of the solution:
\(\le \sqrt{{\left(8\kappa {\sigma}_{{s}_{\text{1,2}}}\sqrt{2d}+16\kappa {\sigma}_{{s}_{\text{1,2}}}d\sqrt{2d}\right)}^{2}+{\left(8\kappa {\sigma}_{{s}_{3}}\sqrt{3d}+32{\sigma}_{{s}_{\text{1,2}}}{\sigma}_{r}d\sqrt{3d}\right)}^{2}}+4{\kappa }^{2}\sqrt{{\left(2\sigma \sqrt{2d}+4d\sigma \sqrt{2d}\right)}^{2}+{\left(\sqrt{3d}\right)}^{2}}\). □
Remark 6
(On the Unified Proof Structure for Traceability, EUF-CMA, and Non-frameability). We clarify why traceability, EUF-CMA, and non-frameability are proved within a single unified framework in our LCGS-UCSL scheme, and how the three properties are formally distinguished:
-
(1)
(1) Shared Algebraic Core. All three properties reduce to the same fundamental task: extracting a valid MSIS solution from a forged signature. The algebraic structure of the forgery, comprising commitments (\({{\varvec{t}}}_{s{t}_{i}}\), \({{\varvec{t}}}_{s{t}_{i}}{\prime}\)), verifiable encryption (\({h}_{s{t}_{i}}\), \({{\varvec{d}}}_{s{t}_{i}}\)), and the NIZKPoK proof \({\pi}_{s{t}_{i}}\), is identical across all three experiments. The extraction algorithm (Theorem 3) uses the General Forking Lemma (Bellare and Neven 2006) to obtain two accepting transcripts with different challenges, from which it recovers the secret randomness and solves MSIS. This shared algebraic backbone justifies the unified presentation.
-
(2)
Distinguishing the Three Properties via Adversarial Goals and Oracle Access. While the reduction technique is shared, the three properties are formally separated by what the adversary aims to achieve and which oracles it is given:
Traceability. The adversary plays the GM (via \(\mathcal{O}{\text{J}}_{M}\)) and arbitrary users (via \(\mathcal{O}\text{C}\text{o}\text{r}\)). It wins by outputting (\(M\), \(\Sigma\)) such that Verify(\(gpk\), \(\Sigma\))\(=\) Valid but Open(\(gtk\), \(\Sigma\)) = \(\perp\), i.e., the signature is valid yet untraceable to any registered member. This captures the requirement that the GM must always be able to identify the signer of any valid signature.
EUF-CMA. The adversary has access to the signing oracle \(\mathcal{O}\text{S}\text{i}\text{g}\text{n}(i\),\(M)\) for adaptively chosen messages. It wins by outputting (\(M\), \(\Sigma\)) such that Verify(\(gpk\), \(\Sigma\)) = Valid and \(M\) was never queried to \(\mathcal{O}\text{S}\text{i}\text{g}\text{n}\). The opening result is irrelevant; the focus is on existential unforgeability under chosen-message attacks.
Non-frameability. The adversary corrupts the GM and some users, but a target honest user \(i\) remains uncorrupted (not queried to \(\mathcal{O}\text{C}\text{o}\text{r}\)). The adversary wins by outputting (\(M\), \(\Sigma\)) such that Verify(gpk, \(\Sigma\)) = Valid and Open(gtk, \(\Sigma\)) = \(i\), despite \(i\) never having signed \(M\). This ensures that honest users cannot be falsely accused.
-
(3)
Explicit Assumption Mapping. Each property is grounded in specific hardness assumptions:
Anonymity \(\to\) Hiding of commitment (Baum et al. 2018) + IND-CPA of verifiable encryption (Lyubashevsky and Neven 2017) (Theorem 1);
Traceability \(\to\) \(NTR{U}_{q,r}\) + \(\text{D}\text{e}\text{c}\text{i}\text{s}\text{i}\text{o}\text{n}-{\text{MSIS}}_{q,\text{1,2},\sqrt{2d}}\) (Theorem 2);
EUF-CMA and Non-frameability \(\to\) \({\text{MSIS}}_{q,\text{1,5},{\mathcal{B}}_{\mathcal{S}}}\) (Theorem 3, via the forking lemma);
Linkability Sequential Linkability \(\to\) MSIS + one-wayness of \({H}_{3}\) (Sect. “Informal security analysis”);
Revocability \(\to\) \({\text{MSIS}}_{q,\text{1,2},\beta }\) (Sect. “Informal security analysis”).
-
(4)
Why Unified Presentation is Standard. This treatment follows the established paradigm in lattice-based group signature literature (Pino et al. 2018; Lyubashevsky et al. 2021), where the hardness of forging signatures simultaneously implies traceability, unforgeability, and non-frameability. The separation is achieved through experiment definitions (adversary capabilities and winning conditions) rather than through structurally different proofs. The modular game sequence in Theorem 2 (\({G}_{0}\to {G}_{5}\)) transforms the real scheme into a simulated \({\text{GSetup}}^{*}\) where the extraction succeeds with the same probability bound for all three properties, as the adversary’s forgery must satisfy the same algebraic relations regardless of which security property is being violated.
Security proofs for NIZKPoK
Theorem 4
Our revocation method and signature scheme can be viewed as an NIZKPoK scheme, which satisfies completeness, honest-verifier zero-knowledge, and special soundness (we will only use the revocation portion as an example to illustrate this).
Proof
Completeness: The verifier accepts the proof with overwhelming probability.
Due to \({{{\varvec{a}}}_{3}}^{T}{{\varvec{z}}}_{k}-\overline{{b }_{1}}c\)
Honest-verifier zero-knowledge: The transcripts with an honest verifier can be simulated with a statistically indistinguishable distribution.
Let \(\mathcal{S}({{{\varvec{a}}}_{3}}^{T}\), \(\overline{{b }_{1}})\) be the following PPT algorithm.
(1) Sample \(c\stackrel{\boldsymbol{\$}}{\leftarrow }\mathcal{C}\), \({{\varvec{z}}}_{k}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{k}}\);
(2) Compute \({w}_{k}={{{\varvec{a}}}_{3}}^{T}{{\varvec{z}}}_{k}-\overline{{b }_{1}}c\);
(3) Output (\({w}_{k}\), \(c\), \({{\varvec{z}}}_{k}\)).
It is clear that \({{\varvec{z}}}_{k}\) is accepted with overwhelming probability. According to the rejection sampling (Pino et al. 2018), we know that in the real protocol, the distribution of \({{\varvec{z}}}_{k}\) is \({\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{k}}\). Since \({w}_{k}\) is completely determined by \({{{\varvec{a}}}_{3}}^{T}\), \(\overline{{b }_{1}}\), \({{\varvec{z}}}_{k}\), \(c\), the distribution of (\({w}_{k}\), \(c\), \({{\varvec{z}}}_{k}\)) output by \(\mathcal{S}\) matches their distribution in the actual protocol.
Special Soundness: Given two accepting transcripts, one can extract valid openings \({{\varvec{z}}}_{k}\) and \(c-{c}^{{\prime}}\) of \(\overline{{b }_{1}}\) such that \(\overline{c }\in \overline{\mathcal{C} }\), \(\Vert \overline{{\varvec{z}}}\Vert \le 4{\sigma }_{k}\sqrt{2d}\).
Let (\({w}_{k}\), \(c\), \({{\varvec{z}}}_{k}\)) and (\({w}_{k}\), \({c}^{\boldsymbol{{\prime}}}\), \({{{\varvec{z}}}_{k}}{\prime}\)) be two accepting transcripts with \({{\varvec{z}}}_{k}\ne {{{\varvec{z}}}_{k}}{\prime}\) and \(c\ne {c}{\prime}\), then (\({{\varvec{z}}}_{k}-{{{\varvec{z}}}_{k}}{\prime}\), \(c-{c}{\prime}\)) is a valid opening of \(\overline{{b }_{1}}\). By computing the difference of the verification equations for both transcripts, we obtain:
\({{{\varvec{a}}}_{3}}^{T}({{\varvec{z}}}_{k}-{{{\varvec{z}}}_{k}}{\prime})=\overline{{b }_{1}}(c-{c}{\prime}\)) (\(c-{c}{\prime}\) has an inverse in \({\mathbb{R}}_{q}\)).
with \(\Vert {{\varvec{z}}}_{k}-{{{\varvec{z}}}_{k}}{\prime}\Vert \le 4{\sigma}_{k}\sqrt{2d}\). □
We note that the security proofs of this work are established in the ROM, which is consistent with all state-of-the-art lattice-based group signature schemes that simultaneously support user-controlled sequential linkability, efficient revocation, and traceability. Designing such schemes with comprehensive functionality in the standard model remains a well-known open problem due to the inherent difficulty of supporting dynamic membership, linkability, and non-interactive zero-knowledge proofs without random oracles. In practice, our hash functions are instantiated using SHAKE-256 (Documentation 2023), a NIST-standardized and post-quantum secure hash algorithm. Combined with the formal verification results via the Scyther tool and extensive performance evaluation, the scheme provides strong, practically convincing security for real-world deployment.
Formal security analysis using the Scyther tool
We conducted a formal analysis of our LCGS-UCSL using the latest stable version of Scyther (v1.1.3) (Cremers 2023), released April 4, 2014. Scyther is an automated security protocol verification tool. To validate the security of our scheme, we write our scheme in the security protocol description language. Figure 3 depicts the Scyther-generated plot of the signature mechanism in action among a GM, a signer, and a verifier, showing the successful security verification of our scheme.
Performance evaluation
In this section, we analyze the performance of characteristics, the performance of the computation overhead and the storage overhead, and the performance of the communication overhead, compare its characteristics performance with that of related works such as Bao et al. (2023a), Diaz and Lehmann(2021), Ling et al. (2019), Pino et al. (2018), Lyubashevsky et al. (2021), Tang et al. (2023), Gao et al. (2024), Tang et al. (2024), Bao et al. (2023b), and Chen et al. (2025), and compare the computation overhead and the storage overhead with scheme (Lyubashevsky et al. 2021).
Comparison of characteristics among different schemes
Based on the comparative analysis summarized in Table 2, the proposed scheme uniquely achieves all eight critical security and functionality properties, namely revocability (without leaking the privacy of the revoked signer and eliminating the need to update the token each time through a secure channel), distinguishing traceability, avoidance of malicious GM and key escrow, batched aggregation verification, linkability, sequential linkability, user-controlled linkability, and post-quantum security, thereby establishing a new benchmark for group signature constructions. While prior works satisfy partial requirements, fundamental trade-offs persist: Schemes (Bao et al. 2023a, 2023b; Diaz and Lehmann 2021) lack post-quantum security and revocability, rendering them unsuitable for future-proof systems requiring dynamic membership management. The schemes proposed by Tang et al. (2023) and Gao et al. (2024) provide revocation but lack linkability features entirely and need to verify the revocation list, resulting in a lack of flexibility and efficiency in the scheme. Similarly, the scheme proposed by scheme (Yue et al. 2021) also provides revocation, but requires updating the revocation token through a secure channel each time, which requires a lot of computational overhead. Ling et al. (2019) achieve post-quantum security and distinguishing traceability through KOE, but also forfeit linkability and aggregate-batch verification. Schemes (Pino et al. 2018; Lyubashevsky et al. 2021) achieve post-quantum security but lack revocability, distinguishing traceability, all forms of linkability, and batched aggregation verification, limiting its applicability in dynamic privacy-preserving environments. Scheme (Tang et al. 2024) supports linkability yet omits revocability, traceability control, and batched aggregation verification. Scheme (Chen et al. 2025) provides revocation and user-controlled linkability, but lacks sequential linkability. Moreover, its revocation requires verifying the revocation list. Only our lattice-based construction integrates the efficient and secure polynomial-based revocation method, scope-based pseudonyms for user-controlled linking, signature aggregation for efficient batch verification, and KOE to simultaneously enable distinguishing traceability while preventing malicious signers from detecting their traceable status. This comprehensive scheme, proven secure in the ROM, addresses the limitations of existing approaches and provides a practical solution for privacy-preserving authentication in the post-quantum era.
In terms of revocation efficiency, our polynomial-based revocation achieves constant-time verification regardless of group size or the number of revoked users. Unlike VLR, which incurs linear verification overhead proportional to the revocation list length, our scheme only requires a lightweight polynomial check within the NIZKPoK. For large-scale groups, this yields significant savings in computation and communication. The revocation polynomial is updated without reissuing member keys, making the mechanism scalable and privacy-preserving.
Computation overhead and storage overhead
In this section, we discuss the selection of parameters and the evaluation of the storage and time overhead of our scheme. We implement our scheme using the SageMath computer algebra system, version 10.7 (Developers and SageMath 2025 (Version 10.7). Available, https://www.sagemath.org Experiments were conducted on a Lenovo ThinkPad T480s laptop running Windows 10, equipped with an Intel Core i7-8650U CPU @ 1.90 GHz and 16 GB of RAM. Table 3 describes some common parameters, and the selection method refers to Ref. Pino et al. (2018), Lyubashevsky (2012), and Micciancio and Peikert (2012). We use SHAKE-256 (Documentation 2023) to instantiate our hash function and the Lattice Estimator tool (Lattice Estimator Documentation 2021) to evaluate the security of our parameters. We put the detailed description in the Appendix. Based on expensive mathematical operations, we compare the costs (storage and time) of our scheme with schemes (Pino et al. 2018; Lyubashevsky et al. 2021), which are shown in Tables 4 and 7. Notably, our scheme achieves comprehensive functionality, including revocability, multiple linkability modes, batch verification, and distinguishing traceability, which is absent in schemes (Pino et al. 2018; Lyubashevsky et al. 2021), with only modest increases in key/signature sizes and computational overhead, demonstrating its superior versatility for advanced privacy-preserving applications in the post-quantum era. From the result of Table 4, it can be seen that the aggregation rate of linked signature size is 31.0259/(500 \(\times\) 0.3323)\(\approx\) 19%, which means that it is reduced by 81%; the compression ratio of VerifyLink time is 17.2487/(500 \(\times\) 0.2052)\(\approx\) 17%, which means that the time overhead is reduced by 83% (Tables 5 and 6). As can be seen from Table 7, the runtimes of GSetup and KeyGen, Verify, and Open are all within one second; Sign and Revoke are all within 3.5 s; Join, Slink, and VerifySLink are slightly longer, but still within an acceptable range (the join time displayed in the table refers to the total time it took for 500 users to join simultaneously while offline (\(\approx\) 982 s); in reality, the actual time for a single user to join, as same as the time to withdraw, is approximately 3.5 s; SLink time is about 92 s, this process will not affect online communication efficiency; VerifySLink time is about 18 s under the conditions of \(st\) = 501 and \(N\) = 500).
Size evaluation
In this section, we calculate the public key size, secret key size, single signature size, and aggregated signature size, as detailed below:
Public key size: Signer \(i\)’s public key is \({gtpk}_{i}=\)(\(a\), \({{\varvec{b}}}_{2}\), \({un}_{i}\)), where \(a\in {\mathbb{R}}_{Q}\), \({{\varvec{b}}}_{2}\in {\mathbb{R}}_{Q}^{3}\), and \({un}_{i}\in {\mathbb{Z}}_{q}\). The size of the public key \(\approx \frac{4\times d\times \lceil\text{log}\,Q\rceil+\lceil\text{log}\,q\rceil}{8}\) Bytes.
Secret key size: Signer \(i\)’s secret key is \({sk}_{i}=({{\varvec{s}}}_{i,1}\), \({{\varvec{s}}}_{i,2}\), \({{\varvec{s}}}_{i,3})\in {\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\times {\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\times {S}_{1}^{3}\), and RSK is \({r}_{i}\in {\mathbb{R}}_{q}\) The size of the secret key \(\approx \frac{4\times d\times \lceil\text{log}\,(4\sigma )\rceil+3\times d+d\times \lceil\text{log}\,q\rceil}{8}\) Bytes.
Single signature size: The single signature is \({\Sigma}_{{st}_{i}}=(M\), \({scp}_{{st}_{i}}\), \({nym}_{{st}_{i}}\), \({{\varvec{t}}}_{{st}_{i}}\),\({{\varvec{t}}}_{{st}_{i}}{\prime}\), \({\pi}_{{st}_{i}}\),\({h}_{{st}_{i}}\),\({{\varvec{d}}}_{{st}_{i}}\), \({seq}_{{st}_{i}}\), \({st}_{i}\leftarrow {st}_{i}+1\),\({un}_{i})\) and \({\pi}_{{st}_{i}}=({{\varvec{z}}}_{1}\),\({{\varvec{z}}}_{2}\), \({{\varvec{z}}}_{{s}_{1}}\), \({{\varvec{z}}}_{{s}_{2}}\),\({{\varvec{z}}}_{{s}_{3}}\),\({{\varvec{z}}}_{B}\),\({{\varvec{z}}}_{k}\),\(c)\), where \({scp}_{{st}_{i}}\in {\mathbb{R}}_{q}\), \({nym}_{{st}_{i}}\in {\mathbb{R}}_{q}\), \({{\varvec{t}}}_{{st}_{i}}\in {\mathbb{R}}_{q}^{2}\), \({{\varvec{t}}}_{{st}_{i}}{\prime}\in {\mathbb{R}}_{q}^{2}\), \({{\varvec{z}}}_{1}\in {\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\),\({{\varvec{z}}}_{2}\in {\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\), \({{\varvec{z}}}_{{s}_{1}}\in {\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\), \({{\varvec{z}}}_{{s}_{2}}\in {\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\),\({{\varvec{z}}}_{{s}_{3}}\in {\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{{s}_{3}}}\),\({{\varvec{z}}}_{B}\in {\mathcal{D}}_{{\mathbb{R}}^{8}, {\sigma}_{B}}\),\({{\varvec{z}}}_{k}\in {\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{k}}\),\(c\in \mathcal{C}\), \({h}_{{st}_{i}}\in {\mathbb{R}}_{Q}\),\({{\varvec{d}}}_{{st}_{i}}\in {\mathbb{R}}_{Q}^{3}\) and \({seq}_{{st}_{i}}\in {\mathbb{R}}_{q}^{3}\). The size of a single signature \(\approx \frac{\begin{gathered} 6 \times d \times \left[ {{\text{log}}q} \right] + 6 \times d \times \left[ {{\text{log}}\left( {4\sigma _{r} } \right)} \right] + 4 \times d \times \left[ {{\text{log}}\left( {4\sigma _{{s_{{1,2}} }} } \right)} \right] + 3 \times d \times \left[ {{\text{log}}\left( {4\sigma _{{s_{3} }} } \right)} \right] \hfill \\ + 8 \times d \times \left[ {{\text{log}}\left( {4\sigma _{B} } \right)} \right] + 2 \times d \times \left[ {{\text{log}}\left( {4\sigma _{k} } \right)} \right] + d + 4 \times d \times \left[ {{\text{log}}Q} \right] + 3 \times d \times \left[ {{\text{log}}q} \right] \hfill \\ \end{gathered} }{8}\) Bytes.
Aggregated signature size: The aggregated signature is \({\Sigma}_{seq}=(LM\), \(\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}} }\), \(\overline{nym }\), \(\overline{{\varvec{t}} }\),\(\overline{{{\varvec{t}} }^{\boldsymbol{{\prime}}}}\), \({\pi}_{seq}\),\(\overline{h }\), \(\overline{{\varvec{d}} }\), \({\{{seq}_{j}=({seq}_{j,1}, {seq}_{j,2}), {x}_{j}\}}_{j\in [1,st-1]}\), \({st}_{i}\),\({un}_{i})\) and \({\pi}_{seq}=({{\varvec{z}}}_{1}\),\({{\varvec{z}}}_{2}\), \({{\varvec{z}}}_{{s}_{1}}\), \({{\varvec{z}}}_{{s}_{2}}\),\({{\varvec{z}}}_{{s}_{3}}\),\({{\varvec{z}}}_{B}\),\({{\varvec{z}}}_{k}\),\(c)\), where \(\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}}}\in {\mathbb{R} }_{q}^{3}\), \(\overline{nym}\in {\mathbb{R} }_{q}\), \(\overline{{\varvec{t}}}\in {\mathbb{R} }_{q}^{2}\), \(\overline{{{\varvec{t}} }^{\boldsymbol{{\prime}}}}\in {\mathbb{R}}_{q}^{2}\), \({{\varvec{z}}}_{1}\in {\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\),\({{\varvec{z}}}_{2}\in {\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\), \({{\varvec{z}}}_{{s}_{1}}\in {\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\), \({{\varvec{z}}}_{{s}_{2}}\in {\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\),\({{\varvec{z}}}_{{s}_{3}}\in {\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{{s}_{3}}}\),\({{\varvec{z}}}_{B}\in {\mathcal{D}}_{{\mathbb{R}}^{8}, {\sigma}_{B}}\),\({{\varvec{z}}}_{k}\in {\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{k}}\),\(c\in \mathcal{C}\), \(h\in {\mathbb{R}}_{Q}\),\(\overline{{\varvec{d}}}\in {\mathbb{R} }_{Q}^{3}\), and (\({seq}_{j}\in {\mathbb{R}}_{q}^{2}\), \({x}_{j}\in {\mathbb{R}}_{q}\))\((j\in [1\), \({st}_{i}-1])\). The size of the aggregated signature \(\approx \frac{\begin{gathered} 8 \times d \times \left[ {{\text{log}}q} \right] + 6 \times d \times \left[ {\log \left( {4\sigma _{r} } \right)} \right] + 4 \times d \times \left[ {\log \left( {4\sigma _{{s_{{1,2}} }} } \right)} \right] + 3 \times d \times \left[ {\log \left( {4\sigma _{{s_{3} }} } \right)} \right] \hfill \\ + 8 \times d \times \left[ {{\text{log}}\left( {4\sigma _{B} } \right)} \right] + 2 \times d \times \left[ {{\text{log}}\left( {4\sigma _{k} } \right)} \right] + d + 4 \times d \times \left[ {{\text{log}}Q} \right] + 3 \times \left( {st_{i} - 1} \right) \times d \times \left[ {{\text{log}}q} \right] \hfill \\ \end{gathered} }{8}\) Bytes.
Runtime evaluation
The execution time of various basic operations is shown in Table 6. According to Sect. “Our scheme”, we can calculate time costs as follows:
In the GSetup and KeyGen phase, the GM samples \({{\varvec{a}}}_{1}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{3}\), \({{\varvec{a}}}_{2}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{3}\), \({{\varvec{a}}}_{3}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}^{2}\), \({\varvec{R}}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2\times 2}\), \(({{\varvec{s}}}_{\text{0,1}}\),\({{\varvec{s}}}_{\text{0,2}}\),\({{\varvec{s}}}_{\text{0,3}})\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2}\times {S}_{1}^{2}\times {S}_{1}^{3}\), \(({a}^{\left(1\right)}\), \({a}^{(2)})\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{Q}\times {\mathbb{R}}_{Q}\), \(({\varvec{s}}\),\({\varvec{e}})\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\times {S}_{{2}^{79}}^{3}\), and \({{\varvec{b}}}_{2}^{(1)}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{Q}^{3}\), computes \({{{\varvec{b}}}_{1}}^{T}={{{\varvec{a}}}_{3}}^{T}{\varvec{R}}\in {\mathbb{R}}_{q}^{1\times 2}\), \(u=[{{{\varvec{a}}}_{3}}^{T}| {{{\varvec{b}}}_{1}}^{T}| {{{\varvec{a}}}_{2}}^{T}]\left[\begin{array}{c}{{\varvec{s}}}_{\text{0,1}}\\ {{\varvec{s}}}_{\text{0,2}}\\ {{\varvec{s}}}_{\text{0,3}}\end{array}\right]\), and \({{\varvec{b}}}_{2}^{(2)}={a}^{(2)}{\varvec{s}}+{\varvec{e}}\in {\mathbb{R}}_{Q}^{3}\). After that, the GM samples \({g}_{i}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({e}_{{g}_{i},1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({{\varvec{e}}}_{{g}_{i},2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\), and computes \(a={a}{\prime}{g}_{i}+{e}_{{g}_{i},1}\), and \({{\varvec{b}}}_{2}={{\varvec{b}}}_{2}{\prime}{g}_{i}+{{\varvec{e}}}_{{g}_{i},2}\). Signer \(i\) samples a secret key \({{\varvec{s}}}_{i,3}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{3}\), computes \({{{\varvec{a}}}_{2}}^{T}{{\varvec{s}}}_{i,3}\), and send \({{{\varvec{a}}}_{2}}^{T}{{\varvec{s}}}_{i,3}\) to the GM. The GM can sample \({{\varvec{s}}}_{i,1}\in {\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\), \({{\varvec{s}}}_{i,2}\in {\mathcal{D}}_{{\mathbb{R}}^{2},\sigma }\) using the SampleD algorithm s.t
The execution time for each signer is \(8\times {T}_{q}^{sp}+11\times {T}_{1}^{sp}+5\times {T}_{Q}^{sp}+6\times {T}_{{2}^{79}}^{sp}+4\times {T}_{Mq}+2\times {T}_{Aq}+7\times {T}_{Mq1}+6\times {T}_{Aq}+3\times {T}_{MQ{2}^{79}}+3\times {T}_{AQ{2}^{79}}+5\times {T}_{{2}^{79}}^{sp}+4\times {T}_{MQ{2}^{79}}+4{T}_{AQ{2}^{79}}+3\times {T}_{1}^{sp}+3\times {T}_{Mq1}+2\times {T}_{Aq}+4\times {T}_{\sigma }^{sp}+4\times {T}_{Mq\sigma }+2\times {T}_{M{\mathbb{Z}}_{q}}+5\times {T}_{Aq}\). Combining with Table 6, we can calculate the time for the GSetup and KeyGen phase in Table 7.
In the Join phase, for \(N\) signers, the GM samples the PRSK \({\varvec{k}}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2}\), \(N\) RSKs \({r}_{i}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathbb{R}}_{q}\), computes \({{{\varvec{a}}}_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\in {\mathbb{R}}_{q}\) and \({f}_{j}\left(x\right)=\prod_{i=1}^{N}(x-{r}_{i})+{k}_{j}\) (\(j\in [0\), \(2)\)), the time is \(2 \times T_{1}^{{sp}} + N \times T_{q}^{{sp}} + 2 \times T_{{Mq1}} + T_{{Aq}} + 2 \times \left( {\left( {N + 2} \right) \times \left( {N - 1} \right) \times T_{{Mq}} + \frac{{N^{2} - N}}{2} \times T_{{Aq}} + T_{{Aq1}} } \right)\). Combining with Table 6, we can calculate the time for the Join phase in Table 7.
The Sign phase can be divided into steps:
-
(1)
Sample \(({{\varvec{r}}}_{{st}_{i}}\),\({{\varvec{r}}}_{{st}_{i}}{\prime})\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{3}\times {S}_{1}^{3}\), and set \({{\varvec{t}}}_{{st}_{i}}=\left[\begin{array}{c}{t}_{{st}_{i}, 1}\\ {t}_{{st}_{i},2}\end{array}\right]=\left[\begin{array}{c}{{{\varvec{a}}}_{1}}^{T}\\ {{{\varvec{a}}}_{2}}^{T}\end{array}\right]\times {{\varvec{r}}}_{{st}_{i}}+\left[\begin{array}{c}0\\ i\end{array}\right]\), \({{\varvec{t}}}_{{st}_{i}}{\prime}=\left[\begin{array}{c}{t}_{{st}_{i}, 1}{\prime}\\ {t}_{{st}_{i},2}{\prime}\end{array}\right]=\left[\begin{array}{c}{{{\varvec{a}}}_{1}}^{T}\\ {{{\varvec{a}}}_{2}}^{T}\end{array}\right]\times {{\varvec{r}}}_{{st}_{i}}{\prime}+\left[\begin{array}{c}0\\ i\delta \end{array}\right]\). The time cost is \(6\times {T}_{1}^{sp}+12\times {T}_{Mq1}+8\times {T}_{Aq}+2\times {T}_{Aq{\mathbb{Z}}_{q}}+{T}_{M{\mathbb{Z}}_{q}}\).
-
(2)
Compute \({{{\varvec{v}}}_{{st}_{i}}}^{T}=[{{{\varvec{a}}}_{3}}^{T}\)|\({{{\varvec{b}}}_{1}}^{T}+\left[{t}_{{st}_{i},2}| {t}_{{st}_{i},2}{\prime}\right]\)|\({{{\varvec{a}}}_{2}}^{T}]\in {\mathbb{R}}_{q}^{1\times 7}\), and set \({{\varvec{s}}}_{{st}_{i}}{\prime}=\left[\begin{array}{c}{{\varvec{s}}}_{i,1}\\ {{\varvec{s}}}_{i,2}\\ {{\varvec{s}}}_{i,3}-[{{\varvec{r}}}_{{st}_{i}}| {{\varvec{r}}}_{{st}_{i}}{\prime}]{{\varvec{s}}}_{i,2}\end{array}\right]\in {\mathbb{R}}_{q}^{7}\) satisfying \({{{\varvec{v}}}_{{st}_{i}}}^{T}{{\varvec{s}}}_{{st}_{i}}{\prime}=u\). The time cost is \(2\times {T}_{Aq}+6\times {T}_{M1\sigma }+3\times {T}_{Aq}+3\times {T}_{Aq1}\).
-
(3)
Sample \({s}_{{st}_{i}, B}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({e}_{{st}_{i},1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), and \({{\varvec{e}}}_{{st}_{i}, 2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\), and computes \({h}_{{st}_{i}}=q(a{s}_{{st}_{i}, B}+{e}_{{st}_{i},1})\) and \({{\varvec{d}}}_{{st}_{i}}=q({{\varvec{b}}}_{2}{s}_{{st}_{i}, B}+{{\varvec{e}}}_{{st}_{i}, 2})+{{\varvec{r}}}_{{st}_{i}}\), and set \({{\varvec{r}}}_{{st}_{i}}^{*}=\left({{\varvec{d}}}_{{st}_{i}}-{h}_{{st}_{i}}{\varvec{s}}\right)\overline{c} \text{mod}\;Q\). If \({\Vert {{\varvec{r}}}_{{st}_{i}}^{*}\Vert }_{\infty }>Q/2\kappa\) or \({{\varvec{r}}}_{{st}_{i}}\ne {{\varvec{r}}}_{{st}_{i}}^{*}{\overline{c} }^{-1} \text{mod}\;q\), resample \({s}_{{st}_{i}, B}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), \({e}_{{st}_{i},1}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}\), and \({{\varvec{e}}}_{{st}_{i}, 2}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{{2}^{79}}^{3}\). The time cost is \(5\times {T}_{{2}^{79}}^{sp}+4\times {T}_{MQ{2}^{79}}+4\times {T}_{AQ{2}^{79}}+4\times {T}_{MQ{\mathbb{Z}}_{q}}+3\times {T}_{AQ1}\).
-
(4)
Set \({{\varvec{B}}}_{1}=\left[\begin{array}{c}\begin{array}{c}\begin{array}{ccc}qa& q& \begin{array}{ccc}0& 0& \begin{array}{ccc}0& 0& \begin{array}{cc}0& 0\end{array}\end{array}\end{array}\end{array}\\ \begin{array}{ccc}q{b}_{\text{2,1}}& 0& \begin{array}{ccc}q& 0& \begin{array}{ccc}0& 1& \begin{array}{cc}0& 0\end{array}\end{array}\end{array}\end{array}\end{array}\\ \begin{array}{c}\begin{array}{ccc}q{b}_{\text{2,2}}& 0& \begin{array}{ccc}0& q& \begin{array}{ccc}0& 0& \begin{array}{cc}1& 0\end{array}\end{array}\end{array}\end{array}\\ \begin{array}{ccc}q{b}_{\text{2,3}}& 0& \begin{array}{ccc}0& 0& \begin{array}{ccc}q& 0& \begin{array}{cc}0& 1\end{array}\end{array}\end{array}\end{array}\end{array}\end{array}\right]\), \({{\varvec{B}}}_{2}=[0| 0| 0| 0| 0| {{{\varvec{a}}}_{1}}^{T}]\), \({\varvec{B}}=\left[\genfrac{}{}{0pt}{}{{{\varvec{B}}}_{1}}{{{\varvec{B}}}_{2}}\right]\in {\mathbb{R}}_{Q}^{4\times 8}\times {\mathbb{R}}_{q}^{1\times 8}\), \({{\varvec{r}}}_{{st}_{i},B}={[{s}_{{st}_{i}, B}| {e}_{{st}_{i},1}| {{{\varvec{e}}}_{{st}_{i}, 2}}^{T}| {{{\varvec{r}}}_{{st}_{i}}}^{T}]}^{T}\in {\mathbb{R}}^{8}\), and \({{\varvec{y}}}_{{st}_{i}}={[{h}_{{st}_{i}}| {{{\varvec{d}}}_{{st}_{i}}}^{T}| {t}_{{st}_{i}, 1}]}^{T}\in {\mathbb{R}}_{Q}^{4}\times {\mathbb{R}}_{q}\) satisfying \({\varvec{B}}{{\varvec{r}}}_{{st}_{i},B}={{\varvec{y}}}_{{st}_{i}}\). The time cost is \(4\times {T}_{MQ{\mathbb{Z}}_{q}}\).
-
(5)
Compute \({{{\varvec{a}}}_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\), where \({\varvec{k}}=\left[\begin{array}{c}{f}_{0}({r}_{i})\\ {f}_{1}({r}_{i})\end{array}\right]\). The time cost is \(2\times (2N\times {T}_{Aq}+(N+\text{log}\,N)\times {T}_{Mq})+2\times {T}_{Mq1}+{T}_{Aq}\).
-
(6)
Sample \({scp}_{{st}_{i}}\in {\mathbb{R}}_{q}\) and compute \({{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}{{\varvec{s}}}_{i,3}={nym}_{{st}_{i}}\). The time cost is \({T}_{q}^{sp}+{T}_{{H}_{2}}+3\times {T}_{Mq1}+2\times {T}_{Aq}\).
-
(7)
Compute \({n}_{{st}_{i}}={H}_{3}({{\varvec{s}}}_{i,3}\), \(0| {st}_{i})\), \({n}_{{st}_{i}-1}={H}_{3}({{\varvec{s}}}_{i,3}\), \(0| {st}_{i}-1)\). The time cost is \(2\times {T}_{{H}_{3}}\).
-
(8)
Compute \({x}_{{st}_{i}}={H}_{3}({{\varvec{s}}}_{i,3}\), \(1| {n}_{{st}_{i}})\), \({x}_{{st}_{i}-1}={H}_{3}({{\varvec{s}}}_{i,3}\), \(1| {n}_{{st}_{i}-1})\). The time cost is \(2\times {T}_{{H}_{3}}\).
-
(9)
Compute \({seq}_{{st}_{i},1}={H}_{3}({x}_{{st}_{i}})\), \({seq}_{{st}_{i},2}={H}_{3}({x}_{{st}_{i}}\oplus {x}_{{st}_{i}-1})\), \({seq}_{{st}_{i},3}={n}_{{st}_{i}}\). The time cost is \(2\times {T}_{{H}_{3}}\).
-
(10)
Generate a proof
$${\pi}_{{st}_{i}}={\text{N}\text{I}\text{Z}\text{K}\text{P}\text{o}\text{K}}^{\text{L}\text{C}\text{G}\text{S}-\text{U}\text{C}\text{S}\text{L}}\left[\left({{\varvec{s}}}_{{st}_{i}}^{{\prime}},{{\varvec{r}}}_{{st}_{i},B},{\varvec{k}},{{\varvec{s}}}_{i,3}\right):{{{\varvec{v}}}_{{st}_{i}}}^{T}{{\varvec{s}}}_{{st}_{i}}^{{\prime}}=u\wedge {\varvec{B}}{{\varvec{r}}}_{{st}_{i},B}={{\varvec{y}}}_{{st}_{i}}\wedge {{{\varvec{a}}}_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\wedge {{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}{{\varvec{s}}}_{i,3}={nym}_{{st}_{i}}\right]\left(M\right).$$
Prover \(\mathcal{P}\) samples \(({{\varvec{y}}}_{r}\),\({{\varvec{y}}}_{r}{\prime})\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\times {\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\), \(({{\varvec{y}}}_{{s}_{1}}\), \({{\varvec{y}}}_{{s}_{2}})\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\times {\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\), \({{\varvec{y}}}_{{s}_{3}}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{{s}_{3}}}\), \({{\varvec{y}}}_{B}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{8}, {\sigma}_{B}}\), and \({{\varvec{y}}}_{k}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{k}}\). It also computes \({w}_{1}={{{\varvec{a}}}_{1}}^{T}{{\varvec{y}}}_{r}\), \({w}_{1}{\prime}={{{\varvec{a}}}_{1}}^{T}{{\varvec{y}}}_{r}{\prime}\), \({w}_{2}=\delta {{{\varvec{a}}}_{2}}^{T}{{\varvec{y}}}_{r}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{y}}}_{r}{\prime}\), \({w}_{{s}_{1}}={{{\varvec{a}}}_{3}}^{T}{{\varvec{y}}}_{{s}_{1}}\), \({w}_{{s}_{2}}=({{{\varvec{b}}}_{1}}^{T}+[{t}_{{st}_{i},2}| {t}_{{st}_{i},2}{\prime}]){{\varvec{y}}}_{{s}_{2}}\), \({w}_{{s}_{3}}={{{\varvec{a}}}_{2}}^{T}{{\varvec{y}}}_{{s}_{3}}\), \({{\varvec{w}}}_{B}={\varvec{B}}{{\varvec{y}}}_{B}\in {\mathbb{R}}_{Q}^{4}\times {\mathbb{R}}_{q}\), \({w}_{k}={{{\varvec{a}}}_{3}}^{T}{{\varvec{y}}}_{k}\), \(c={H}_{1}({w}_{1}\), \({w}_{1}{\prime}\), \({w}_{2}\), \({w}_{{s}_{1}}\), \({w}_{{s}_{1}}+{w}_{{s}_{2}}+{w}_{{s}_{3}}\), \({{\varvec{w}}}_{B}\), \({w}_{k}\), \(M\)), \({{\varvec{z}}}_{1}={{\varvec{r}}}_{{st}_{i}}c+{{\varvec{y}}}_{r}\), \({{\varvec{z}}}_{2}={{\varvec{r}}}_{{st}_{i}}{\prime}c+{{\varvec{y}}}_{r}^{\boldsymbol{{\prime}}}\), \({{\varvec{z}}}_{{s}_{1}}={{\varvec{s}}}_{i,1}c+{{\varvec{y}}}_{{s}_{1}}\), \({{\varvec{z}}}_{{s}_{2}}={{\varvec{s}}}_{i,2}c+{{\varvec{y}}}_{{s}_{2}}\), \({{\varvec{z}}}_{{s}_{3}}=({{\varvec{s}}}_{i,3}-\left[{{\varvec{r}}}_{{st}_{i}}| {{\varvec{r}}}_{{st}_{i}}{\prime}\right]{{\varvec{s}}}_{i,2})c+{{\varvec{y}}}_{{s}_{3}}\), \({{\varvec{z}}}_{B}={{\varvec{r}}}_{{st}_{i},B}c+{{\varvec{y}}}_{B}\), \({{\varvec{z}}}_{k}={\varvec{k}}c+{{\varvec{y}}}_{k}\). The time cost is \(6\times {T}_{{\sigma}_{r}}^{sp}+4\times {T}_{{\sigma}_{{s}_{\text{1,2}}}}^{sp}+3\times {T}_{{\sigma}_{{s}_{3}}}^{sp}+8\times {T}_{{\sigma}_{{s}_{B}}}^{sp}+2\times {T}_{{\sigma}_{k}}^{sp}+12\times {T}_{Mq{\sigma}_{r}}+{T}_{Mq{\mathbb{Z}}_{q}}+9\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Aq}+2\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Aq}+3\times {T}_{Mq{\sigma}_{{s}_{3}}}+2\times {T}_{Aq}+32\times {T}_{MQ{\sigma}_{B}}+28\times {T}_{AQ}+8\times {T}_{Mq{\sigma}_{B}}+7\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{k}}+{T}_{Aq}+{T}_{{H}_{1}}+2\times {T}_{Aq}+6\times {T}_{M1\mathcal{C}}+6\times {T}_{Aq{\sigma}_{r}}+4\times {T}_{M\sigma \mathcal{C}}+4\times {T}_{Aq{\sigma}_{{s}_{\text{1,2}}}}+6\times {T}_{M1\sigma }+3\times {T}_{Aq}+3\times {T}_{Aq1}+3\times {T}_{Mq\mathcal{C}}+3\times {T}_{Aq{\sigma}_{{s}_{3}}}+5\times {T}_{MQ\mathcal{C}}+3\times {T}_{M1\mathcal{C}}+5\times {T}_{AQ{\sigma}_{B}}+3\times {T}_{Aq{\sigma}_{B}}+2\times {T}_{M1\mathcal{C}}+2\times {T}_{Aq{\sigma}_{k}}\).
It performs rejection sampling \(\text{R}\text{e}\text{j}(({{\varvec{z}}}_{1}\),\({{\varvec{z}}}_{2})\),\(({{\varvec{r}}}_{{st}_{i}}c\),\({{\varvec{r}}}_{{st}_{i}}{\prime}c)\), \({\sigma}_{r}\), \(3d)\), \(\text{R}\text{e}\text{j}(({{\varvec{z}}}_{{s}_{1}}\),\({{\varvec{z}}}_{{s}_{2}})\),\(({{\varvec{s}}}_{i,1}c\),\({{\varvec{s}}}_{i,2}c)\),\({\sigma}_{{s}_{\text{1,2}}}\), \(2d)\), \(\text{R}\text{e}\text{j}({{\varvec{z}}}_{{s}_{3}}\),\(({{\varvec{s}}}_{i,3}-\left[{{\varvec{r}}}_{{st}_{i}}| {{\varvec{r}}}_{{st}_{i}}{\prime}\right]{{\varvec{s}}}_{i,2})c\), \({\sigma}_{{s}_{3}}\), \(3d)\), \(\text{R}\text{e}\text{j}({{\varvec{z}}}_{B}\), \({{\varvec{r}}}_{B}c\),\({\sigma}_{B}\),\(8d)\), \(\text{R}\text{e}\text{j}({{\varvec{z}}}_{k}\), \({\varvec{k}}c\),\({\sigma}_{k}\), \(2d)\), and sends \(({{\varvec{z}}}_{1}\),\({{\varvec{z}}}_{2}\), \({{\varvec{z}}}_{{s}_{1}}\), \({{\varvec{z}}}_{{s}_{2}}\),\({{\varvec{z}}}_{{s}_{3}}\),\({{\varvec{z}}}_{B}\),\({{\varvec{z}}}_{k}\), \(M\),\(c)\) to Verifier \(\mathcal{V}\). The expected number of repetitions \(\text{REP}\approx {\text{e}}^{\frac{12}{12}+\frac{1}{2\times {(12)}^{2}}}\).
From (1) to (10), the total time for Signature Generation is \(6\times {T}_{1}^{sp}+12\times {T}_{Mq1}+8\times {T}_{Aq}+2\times {T}_{Aq{\mathbb{Z}}_{q}}+{T}_{M{\mathbb{Z}}_{q}}+2\times {T}_{Aq}+6\times {T}_{M1\sigma }+6\times {T}_{Aq}+5\times {T}_{{2}^{72}}^{sp}+4\times {T}_{MQ{2}^{72}}+4\times {T}_{AQ{2}^{72}}+4\times {T}_{MQ{\mathbb{Z}}_{q}}+3\times {T}_{AQ1}+4\times {T}_{MQ{\mathbb{Z}}_{q}}+2\times ((N+N)\times {T}_{Aq}+(N+\text{log}\,N)\times {T}_{Mq})+2\times {T}_{Mq1}+{T}_{Aq}+{T}_{{H}_{2}}+3\times {T}_{Mq1}+2\times {T}_{Aq}+2\times {T}_{{H}_{3}}+2\times {T}_{{H}_{3}}+2\times {T}_{{H}_{3}}+\text{REP}\times (6\times {T}_{{\sigma}_{r}}^{sp}+4\times {T}_{{\sigma}_{{s}_{\text{1,2}}}}^{sp}+3\times {T}_{{\sigma}_{{s}_{3}}}^{sp}+8\times {T}_{{\sigma}_{{s}_{B}}}^{sp}+2\times {T}_{{\sigma}_{k}}^{sp}+12\times {T}_{Mq{\sigma}_{r}}+{T}_{Mq{\mathbb{Z}}_{q}}+9\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Aq}+2\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Aq}+3\times {T}_{Mq{\sigma}_{{s}_{3}}}+2\times {T}_{Aq}+32\times {T}_{MQ{\sigma}_{B}}+28\times {T}_{AQ}+8\times {T}_{Mq{\sigma}_{B}}+7\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{k}}+{T}_{Aq}+{T}_{{H}_{1}}+2\times {T}_{Aq}+6\times {T}_{M1\mathcal{C}}+6\times {T}_{Aq{\sigma}_{r}}+4\times {T}_{M\sigma \mathcal{C}}+4\times {T}_{Aq{\sigma}_{{s}_{\text{1,2}}}}+6\times {T}_{M1\sigma }+3\times {T}_{Aq}+3\times {T}_{Aq1}+3\times {T}_{Mq\mathcal{C}}+3\times {T}_{Aq{\sigma}_{{s}_{3}}}+5\times {T}_{MQ\mathcal{C}}+3\times {T}_{M1\mathcal{C}}+5\times {T}_{AQ{\sigma}_{B}}+3\times {T}_{Aq{\sigma}_{B}}+2\times {T}_{M1\mathcal{C}}+2\times {T}_{Aq{\sigma}_{k}})\). Combining with Table 6, we can calculate the time for the Sign phase in Table 7.
In the Verify phase, the verifier checks \(\Vert {{\varvec{z}}}_{1}\Vert \le 2{\sigma}_{r}\sqrt{3d}\), \(\Vert {{\varvec{z}}}_{2}\Vert \le 2{\sigma}_{r}\sqrt{3d}\), \(\Vert {{\varvec{z}}}_{{s}_{1}}\Vert \le 2{\sigma}_{{s}_{\text{1,2}}}\sqrt{2d}\), \(\Vert {{\varvec{z}}}_{{s}_{2}}\Vert \le 2{\sigma}_{{s}_{\text{1,2}}}\sqrt{2d}\),\(\Vert {{\varvec{z}}}_{{s}_{3}}\Vert \le 2{\sigma}_{{s}_{3}}\sqrt{3d}\), \(\Vert {{\varvec{z}}}_{B}\Vert \le 4{\sigma}_{B}\sqrt{2d}\), \(\Vert {{\varvec{z}}}_{k}\Vert \le 2{\sigma}_{k}\sqrt{2d}\), computes \({w}_{1}={{{\varvec{a}}}_{1}}^{T}{{\varvec{z}}}_{1}-{t}_{{st}_{i}, 1}c\), \({w}_{1}{\prime}={{{\varvec{a}}}_{1}}^{T}{{\varvec{z}}}_{2}-{t}_{{st}_{i}, 1}{\prime}c\), \({w}_{2}=\delta {{{\varvec{a}}}_{2}}^{T}{{\varvec{z}}}_{1}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{z}}}_{2}-\left(\delta {t}_{{st}_{i}, 2}-{t}_{{st}_{i}, 2}{\prime}\right)c\), \({w}_{{s}_{1}}={{H}_{2}\left({scp}_{{st}_{i}}\right)}^{T}{{\varvec{z}}}_{{s}_{1}}-{nym}_{{st}_{i}}\times c\), \({w}_{{s}_{1}}+{w}_{{s}_{2}}+{w}_{{s}_{3}}={{\varvec{v}}}^{T}\times {\left[{{{\varvec{z}}}_{{s}_{1}}}^{T}\left| {{{\varvec{z}}}_{{s}_{2}}}^{T}\right| {{{\varvec{z}}}_{{s}_{3}}}^{T}\right]}^{T}-u\times c\), \({{\varvec{w}}}_{B}={\varvec{B}}{{\varvec{z}}}_{B}-{{\varvec{y}}}_{{st}_{i}}c\in {\mathbb{R}}_{Q}^{4}\times {\mathbb{R}}_{q}\), \({w}_{k}={{{\varvec{a}}}_{3}}^{T}{{\varvec{z}}}_{k}-\overline{{b }_{1}}c\), and checks whether \(c={H}_{1}({w}_{1}\), \({w}_{1}{\prime}\), \({w}_{2}\), \({w}_{{s}_{1}}\), \({w}_{{s}_{1}}+{w}_{{s}_{2}}+{w}_{{s}_{3}}\), \({{\varvec{w}}}_{B}\), \({w}_{k}\), \(M\)) or not. The time cost is \(6\times {T}_{Mq{\sigma}_{r}}+4\times {T}_{Aq}+2\times {T}_{Mq\mathcal{C}}+2\times {T}_{Aq}+6\times {T}_{Mq{\sigma}_{r}}+2\times {T}_{Mq{\mathbb{Z}}_{q}}+7\times {T}_{Aq}+{T}_{Mq\mathcal{C}}+{T}_{{H}_{2}}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Mq\mathcal{C}}+2\times {T}_{Aq}+2\times {T}_{Aq}+4\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+3\times {T}_{Mq{\sigma}_{{s}_{3}}}+7\times {T}_{Aq}+{T}_{Mq\mathcal{C}}+32\times {T}_{MQ{\sigma}_{B}}+8\times {T}_{Mq{\sigma}_{B}}+28\times {T}_{AQ}+7\times {T}_{Aq}+4\times {T}_{MQ\mathcal{C}}+{T}_{Mq\mathcal{C}}+4\times {T}_{AQ}+{T}_{Aq}+2\times {T}_{Mq{\sigma}_{k}}+2\times {T}_{Aq}+{T}_{Mq\mathcal{C}}+{T}_{{H}_{1}}\). Combining with Table 6, we can calculate the time for the Verify phase in Table 7.
The SLink phase can be divided into steps:
-
(1)
Compute \(\overline{{\varvec{t}} }=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{t}}}_{j} \text{mod}\;q\) and \(\overline{{{\varvec{t}} }^{{\prime}}}=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{t}}}_{j}^{{\prime}} \text{mod}\;q\) (which means \(\overline{{\varvec{r}} }=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{r}}}_{j} \text{mod}\;q\) and \(\overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{r}}}_{j}{\prime} \text{mod}\;q\)). The time cost is \(4\times ({st}_{i}-2)\times {T}_{Aq}+6\times ({st}_{i}-2)\times {T}_{A1}\).
-
(2)
Compute \({\overline{{\varvec{v}}} }^{T}=[{{{\varvec{a}}}_{3}}^{T}| {{{\varvec{b}}}_{1}}^{T}+\left[\overline{{t }_{2}}| \overline{{t }_{2}{\prime}}\right]| {{{\varvec{a}}}_{2}}^{T}]\in {\mathbb{R}}_{q}^{1\times 7}\), and set \(\overline{{{\varvec{s}} }{\prime}}=\left[\begin{array}{c}{{\varvec{s}}}_{i,1}\\ {{\varvec{s}}}_{i,2}\\ {{\varvec{s}}}_{i,3}-[\overline{{\varvec{r}} }| \overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}]{{\varvec{s}}}_{i,2}\end{array}\right]\in {\mathbb{R}}_{q}^{7}\) satisfying \({\overline{{\varvec{v}}} }^{T}\overline{{{\varvec{s}} }{\prime}}=u\). The time cost is \(2\times {T}_{Aq}+6\times {T}_{Mq\sigma }+3\times {T}_{Aq}+3\times {T}_{Aq1}\).
-
(3)
Compute \(\overline{h }=\sum_{j\in [1,{st}_{i}-1]}{h}_{j}\) and \(\overline{{\varvec{d}} }=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{d}}}_{j}\). The time cost is \(4\times ({st}_{i}-2)\times {T}_{AQ}\).
-
(4)
Set \(\overline{{{\varvec{r}} }_{B}}=\sum_{j\in [1,{st}_{i}-1]}{{\varvec{r}}}_{j,B}\in {\mathbb{R}}^{8}\) and \(\overline{{\varvec{y}} }={[\overline{h }| {\overline{{\varvec{d}}} }^{T}| \overline{{t }_{1}}]}^{T}\in {\mathbb{R}}_{Q}^{4}\times {\mathbb{R}}_{q}\) satisfying \({\varvec{B}}\overline{{{\varvec{r}} }_{B}}=\overline{{\varvec{y}}}\in {\mathbb{R} }_{Q}^{4}\times {\mathbb{R}}_{q}\). The time cost is \(5\times ({st}_{i}-2)\times {T}_{A{2}^{72}}+3\times ({st}_{i}-2)\times {T}_{A1}\).
-
(5)
Compute \(\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}} }=\sum_{j\in [1, {st}_{i}-1]}{H}_{2}\left({scp}_{j}\right)\) and \(\overline{nym }=\sum_{j\in [1, st-1]}{nym}_{j}\) (which satisfies \(\overline{nym }={\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}}} }^{T}{{\varvec{s}}}_{i,3}\)). The time cost is \(3\times ({st}_{i}-2)\times {T}_{Aq}+({st}_{i}-2)\times {T}_{{H}_{2}}+({st}_{i}-2)\times {T}_{Aq}\).
-
(6)
Generate a proof
$${\pi}_{seq}={\text{N}\text{I}\text{Z}\text{K}\text{P}\text{o}\text{K}}^{\text{L}\text{C}\text{G}\text{S}-\text{U}\text{C}\text{S}\text{L}}\left[\left(\overline{{{\varvec{s}} }^{{\prime}}},\overline{{{\varvec{r}} }_{B}}, {\varvec{k}},{{\varvec{s}}}_{i,3}\right):{\overline{{\varvec{v}}} }^{T}\overline{{{\varvec{s}} }^{{\prime}}}=u\wedge {\varvec{B}}\overline{{{\varvec{r}} }_{B}}=\overline{{\varvec{y}}}\wedge {{{\varvec{a}} }_{3}}^{T}{\varvec{k}}=\overline{{b }_{1}}\wedge {\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}}} }^{T}{{\varvec{s}}}_{i,3}=\overline{nym }\right]\left(LM\right).$$
Prover \(\mathcal{P}\) samples \(({{\varvec{y}}}_{r}\),\({{\varvec{y}}}_{r}{\prime})\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\times {\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{r}}\), \(({{\varvec{y}}}_{{s}_{1}}\), \({{\varvec{y}}}_{{s}_{2}})\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\times {\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{{s}_{\text{1,2}}}}\), \({{\varvec{y}}}_{{s}_{3}}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{3}, {\sigma}_{{s}_{3}}}\), \({{\varvec{y}}}_{B}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{8}, {\sigma}_{B}}\), and \({{\varvec{y}}}_{k}\stackrel{\boldsymbol{\$}}{\leftarrow }{\mathcal{D}}_{{\mathbb{R}}^{2}, {\sigma}_{k}}\). It also computes \({w}_{1}={{{\varvec{a}}}_{1}}^{T}{{\varvec{y}}}_{r}\), \({w}_{1}{\prime}={{{\varvec{a}}}_{1}}^{T}{{\varvec{y}}}_{r}{\prime}\), \({w}_{2}=\delta {{{\varvec{a}}}_{2}}^{T}{{\varvec{y}}}_{r}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{y}}}_{r}{\prime}\), \({w}_{{s}_{1}}={{{\varvec{a}}}_{3}}^{T}{{\varvec{y}}}_{{s}_{1}}\), \({w}_{{s}_{2}}=({{{\varvec{b}}}_{1}}^{T}+[\overline{{t }_{2}}| \overline{{t }_{2}{\prime}}]){{\varvec{y}}}_{{s}_{2}}\), \({w}_{{s}_{3}}={{{\varvec{a}}}_{2}}^{T}{{\varvec{y}}}_{{s}_{3}}\), \({{\varvec{w}}}_{B}={\varvec{B}}{{\varvec{y}}}_{B}\), \({w}_{k}={{{\varvec{a}}}_{3}}^{T}{{\varvec{y}}}_{k}\), \(c={H}_{1}({w}_{1}\), \({w}_{1}{\prime}\), \({w}_{2}\), \({w}_{{s}_{1}}\), \({w}_{{s}_{1}}+{w}_{{s}_{2}}+{w}_{{s}_{3}}\), \({{\varvec{w}}}_{B}\), \({w}_{k}\), \(LM\)), \({{\varvec{z}}}_{1}=\overline{{\varvec{r}} }c+{{\varvec{y}}}_{r}\), \({{\varvec{z}}}_{2}=\overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}c+{{\varvec{y}}}_{r}^{\boldsymbol{{\prime}}}\), \({{\varvec{z}}}_{{s}_{1}}={{\varvec{s}}}_{i,1}c+{{\varvec{y}}}_{{s}_{1}}\), \({{\varvec{z}}}_{{s}_{2}}={{\varvec{s}}}_{i,2}c+{{\varvec{y}}}_{{s}_{2}}\), \({{\varvec{z}}}_{{s}_{3}}=({{\varvec{s}}}_{i,3}-[\overline{{\varvec{r}} }|\overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}]{{\varvec{s}}}_{i,2})c+{{\varvec{y}}}_{{s}_{3}}\), \({{\varvec{z}}}_{B}=\overline{{{\varvec{r}} }_{B}}c+{{\varvec{y}}}_{B}\), \({{\varvec{z}}}_{k}={\varvec{k}}c+{{\varvec{y}}}_{k}\). The time cost is \(6\times {T}_{{\sigma}_{r}}^{sp}+4\times {T}_{{\sigma}_{{s}_{\text{1,2}}}}^{sp}+3\times {T}_{{\sigma}_{{s}_{3}}}^{sp}+8\times {T}_{{\sigma}_{{s}_{B}}}^{sp}+2\times {T}_{{\sigma}_{k}}^{sp}+12\times {T}_{Mq{\sigma}_{r}}+{T}_{Mq{\mathbb{Z}}_{q}}+9\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Aq}+2\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Aq}+3\times {T}_{Mq{\sigma}_{{s}_{3}}}+2\times {T}_{Aq}+32\times {T}_{MQ{\sigma}_{B}}+28\times {T}_{AQ}+8\times {T}_{Mq{\sigma}_{B}}+7\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{k}}+{T}_{Aq}+{T}_{{H}_{1}}+2\times {T}_{Aq}+6\times {T}_{M1\mathcal{C}}+6\times {T}_{Aq{\sigma}_{r}}+4\times {T}_{M\sigma \mathcal{C}}+4\times {T}_{Aq{\sigma}_{{s}_{\text{1,2}}}}+6\times {T}_{M1\sigma }+3\times {T}_{Aq}+3\times {T}_{Aq1}+3\times {T}_{Mq\mathcal{C}}+3\times {T}_{Aq{\sigma}_{{s}_{3}}}+5\times {T}_{MQ\mathcal{C}}+3\times {T}_{M1\mathcal{C}}+5\times {T}_{AQ{\sigma}_{B}}+3\times {T}_{Aq{\sigma}_{B}}+2\times {T}_{M1\mathcal{C}}+2\times {T}_{Aq{\sigma}_{k}}\).
Perform rejection sampling \(\text{R}\text{e}\text{j}(({{\varvec{z}}}_{1}\),\({{\varvec{z}}}_{2})\),\((\overline{{\varvec{r}} }c\),\(\overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}c)\), \({\sigma}_{r}\), \(3d)\), \(\text{R}\text{e}\text{j}(({{\varvec{z}}}_{{s}_{1}}\),\({{\varvec{z}}}_{{s}_{2}})\),\(({{\varvec{s}}}_{i,1}c\),\({{\varvec{s}}}_{i,2}c)\),\({\sigma}_{{s}_{\text{1,2}}}\), \(2d)\), \(\text{R}\text{e}\text{j}({{\varvec{z}}}_{{s}_{3}}\),\(({{\varvec{s}}}_{i,3}-[\overline{{\varvec{r}} }|\overline{{{\varvec{r}} }^{\boldsymbol{{\prime}}}}]{{\varvec{s}}}_{i,2})c\), \({\sigma}_{{s}_{3}}\), \(3d)\), \(\text{R}\text{e}\text{j}({{\varvec{z}}}_{B}\), \(\overline{{{\varvec{r}} }_{B}}c\),\({\sigma}_{B}\),\(8d)\), \(\text{R}\text{e}\text{j}({{\varvec{z}}}_{k}\), \({\varvec{k}}c\),\({\sigma}_{k}\), \(2d)\), and sends \(({{\varvec{z}}}_{1}\),\({{\varvec{z}}}_{2}\), \({{\varvec{z}}}_{{s}_{1}}\), \({{\varvec{z}}}_{{s}_{2}}\),\({{\varvec{z}}}_{{s}_{3}}\),\({{\varvec{z}}}_{B}\),\({{\varvec{z}}}_{k}\), \(M\),\(c)\) to Verifier \(\mathcal{V}\). The expected number of repetitions \(\text{REP}\approx {\text{e}}^{\frac{12}{\sqrt{2d}}+\frac{1}{2\times 2d}}\).
(7) For all \({\Sigma}_{j}\) in \(\boldsymbol{\Sigma }\), compute \({x}_{j}={H}_{3}({{\varvec{s}}}_{i,3}\),\(1| {seq}_{j,3})\). The time cost is \(({st}_{i}-1)\times {T}_{{H}_{3}}\).
From (1) to (7), the total time for SLink phase is \(4\times ({st}_{i}-2)\times {T}_{Aq}+6\times ({st}_{i}-2)\times {T}_{A1}+2\times {T}_{Aq}+6\times {T}_{Mq\sigma }+3\times {T}_{Aq}+3\times {T}_{Aq1}+4\times ({st}_{i}-2)\times {T}_{AQ}+5\times ({st}_{i}-2)\times {T}_{A{2}^{72}}+3\times ({st}_{i}-2)\times {T}_{A1}+3\times ({st}_{i}-2)\times {T}_{Aq}+({st}_{i}-2)\times {T}_{{H}_{2}}+({st}_{i}-2)\times {T}_{Aq}+\text{REP}\times (6\times {T}_{{\sigma}_{r}}^{sp}+4\times {T}_{{\sigma}_{{s}_{\text{1,2}}}}^{sp}+3\times {T}_{{\sigma}_{{s}_{3}}}^{sp}+8\times {T}_{{\sigma}_{{s}_{B}}}^{sp}+2\times {T}_{{\sigma}_{k}}^{sp}+12\times {T}_{Mq{\sigma}_{r}}+{T}_{Mq{\mathbb{Z}}_{q}}+9\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Aq}+2\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Aq}+3\times {T}_{Mq{\sigma}_{{s}_{3}}}+2\times {T}_{Aq}+32\times {T}_{MQ{\sigma}_{B}}+28\times {T}_{AQ}+8\times {T}_{Mq{\sigma}_{B}}+7\times {T}_{Aq}+2\times {T}_{Mq{\sigma}_{k}}+{T}_{Aq}+{T}_{{H}_{1}}+2\times {T}_{Aq}+6\times {T}_{M1\mathcal{C}}+6\times {T}_{Aq{\sigma}_{r}}+4\times {T}_{M\sigma \mathcal{C}}+4\times {T}_{Aq{\sigma}_{{s}_{\text{1,2}}}}+6\times {T}_{M1\sigma }+3\times {T}_{Aq}+3\times {T}_{Aq1}+3\times {T}_{Mq\mathcal{C}}+3\times {T}_{Aq{\sigma}_{{s}_{3}}}+5\times {T}_{MQ\mathcal{C}}+3\times {T}_{M1\mathcal{C}}+5\times {T}_{AQ{\sigma}_{B}}+3\times {T}_{Aq{\sigma}_{B}}+2\times {T}_{M1\mathcal{C}}+2\times {T}_{Aq{\sigma}_{k}})+({st}_{i}-1)\times {T}_{{H}_{3}}\). Combining with Table 6, we can calculate the time for the SLink phase in Table 7.
The VerifySLink phase can be divided into steps:
-
(1)
The verifier checks \(\Vert {{\varvec{z}}}_{1}\Vert \le 2{\sigma}_{r}\sqrt{3d}\), \(\Vert {{\varvec{z}}}_{2}\Vert \le 2{\sigma}_{r}\sqrt{3d}\), \(\Vert {{\varvec{z}}}_{{s}_{1}}\Vert \le 2{\sigma}_{{s}_{\text{1,2}}}\sqrt{2d}\), \(\Vert {{\varvec{z}}}_{{s}_{2}}\Vert \le 2{\sigma}_{{s}_{\text{1,2}}}\sqrt{2d}\),\(\Vert {{\varvec{z}}}_{{s}_{3}}\Vert \le 2{\sigma}_{{s}_{3}}\sqrt{3d}\), \(\Vert {{\varvec{z}}}_{B}\Vert \le 4{\sigma}_{B}\sqrt{2d}\), \(\Vert {{\varvec{z}}}_{k}\Vert \le 2{\sigma}_{k}\sqrt{2d}\), computes \({w}_{1}={{{\varvec{a}}}_{1}}^{T}{{\varvec{z}}}_{1}-\overline{{t }_{1}}c\), \({w}_{1}{\prime}={{{\varvec{a}}}_{1}}^{T}{{\varvec{z}}}_{2}-\overline{{t }_{1}{\prime}}c\), \({w}_{2}=\delta {{{\varvec{a}}}_{2}}^{T}{{\varvec{z}}}_{1}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{z}}}_{2}-\left(\delta \overline{{t }_{2}}-\overline{{t }_{2}{\prime}}\right)c\), \({w}_{{s}_{1}}={\overline{{\varvec{h}}{\varvec{s}}{\varvec{c}}{\varvec{p}}} }^{T}{{\varvec{z}}}_{{s}_{1}}-\overline{nym }\times c\), \({w}_{{s}_{1}}+{w}_{{s}_{2}}+{w}_{{s}_{3}}={\overline{{\varvec{v}}} }^{T}\times {\left[{{\varvec{z}}}_{{s}_{1}}| {{\varvec{z}}}_{{s}_{2}}| {{\varvec{z}}}_{{s}_{3}}\right]}^{T}-u\times c\), \({{\varvec{w}}}_{B}={\varvec{B}}{{\varvec{z}}}_{B}-\overline{{\varvec{y}}}c\in {\mathbb{R} }_{Q}^{4}\times {\mathbb{R}}_{q}\), and \({w}_{k}={{{\varvec{a}}}_{3}}^{T}{{\varvec{z}}}_{k}-\overline{{b }_{1}}c\), and checks whether \(c={H}_{1}({w}_{1}\), \({w}_{1}{\prime}\), \({w}_{2}\), \({w}_{{s}_{1}}\), \({w}_{{s}_{1}}+{w}_{{s}_{2}}+{w}_{{s}_{3}}\), \({{\varvec{w}}}_{B}\), \({w}_{k}\), \(M\)) or not. The time cost is \(6\times {T}_{Mq{\sigma}_{r}}+4\times {T}_{Aq}+2\times {T}_{Mq\mathcal{C}}+2\times {T}_{Aq}+6\times {T}_{Mq{\sigma}_{r}}+2\times {T}_{Mq{\mathbb{Z}}_{q}}+7\times {T}_{Aq}+{T}_{Mq\mathcal{C}}+{T}_{{H}_{2}}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Mq\mathcal{C}}+2\times {T}_{Aq}+2\times {T}_{Aq}+4\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+3\times {T}_{Mq{\sigma}_{{s}_{3}}}+7\times {T}_{Aq}+{T}_{Mq\mathcal{C}}+32\times {T}_{MQ{\sigma}_{B}}+8\times {T}_{Mq{\sigma}_{B}}+28\times {T}_{AQ}+7\times {T}_{Aq}+4\times {T}_{MQ\mathcal{C}}+{T}_{Mq\mathcal{C}}+4\times {T}_{AQ}+{T}_{Aq}+2\times {T}_{Mq{\sigma}_{k}}+2\times {T}_{Aq}+{T}_{Mq\mathcal{C}}+{T}_{{H}_{1}}\).
-
(2)
Check whether \({seq}_{\text{1,1}}={H}_{3}({x}_{1})\) or not. If not, reject. The time cost is \({T}_{{H}_{3}}\).
-
(3)
For \(j\in [2\),\({st}_{i}-1]\), check whether \({seq}_{j,1}={H}_{3}({x}_{j})\) and \({seq}_{j,2}={H}_{3}({x}_{j}\oplus {x}_{j-1})\) or not. If not, reject. The time cost is \(2\times ({st}_{i}-2)\times {T}_{{H}_{3}}\).
From (1) to (3), the total time for the VerifySLink phase is \(6\times {T}_{Mq{\sigma}_{r}}+4\times {T}_{Aq}+2\times {T}_{Mq\mathcal{C}}+2\times {T}_{Aq}+6\times {T}_{Mq{\sigma}_{r}}+2\times {T}_{Mq{\mathbb{Z}}_{q}}+7\times {T}_{Aq}+{T}_{Mq\mathcal{C}}+{T}_{{H}_{2}}+2\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+{T}_{Mq\mathcal{C}}+2\times {T}_{Aq}+2\times {T}_{Aq}+4\times {T}_{Mq{\sigma}_{{s}_{\text{1,2}}}}+3\times {T}_{Mq{\sigma}_{{s}_{3}}}+7\times {T}_{Aq}+{T}_{Mq\mathcal{C}}+32\times {T}_{MQ{\sigma}_{B}}+8\times {T}_{Mq{\sigma}_{B}}+28\times {T}_{AQ}+7\times {T}_{Aq}+4\times {T}_{MQ\mathcal{C}}+{T}_{Mq\mathcal{C}}+4\times {T}_{AQ}+{T}_{Aq}+2\times {T}_{Mq{\sigma}_{k}}+2\times {T}_{Aq}+{T}_{Mq\mathcal{C}}+{T}_{{H}_{1}}+{T}_{{H}_{3}}+2\times (st-2)\times {T}_{{H}_{3}}\). Combining with Table 6, we can calculate the time for the VerifySLink phase in Table 7.
In the Open phase, the GM sets \({{\varvec{r}}}_{{st}_{i}}^{*}=\left({{\varvec{d}}}_{{st}_{i}}-{h}_{{st}_{i}}{\varvec{s}}\right)\overline{c} \text{mod}\;Q\). If \({\Vert {{\varvec{r}}}_{{st}_{i}}^{*}\Vert }_{\infty }\le Q/(2\kappa )\), compute \({{\varvec{r}}}_{{st}_{i}}^{**}={{\varvec{r}}}_{{st}_{i}}^{*} \text{mod}\;q\); otherwise, return \(\perp\). Next, the GM computes \(i={t}_{{st}_{i},2}-{{{\varvec{a}}}_{2}}^{T}{{\varvec{r}}}_{{st}_{i}}^{**}{\overline{c} }^{-1}\). If \(i\in [N]\), return \(i\), otherwise, return \(\perp\). The time cost is \(3\times {T}_{MQ{2}^{72}}+3\times {T}_{AQ}+3\times {T}_{MQ\mathcal{C}}+3\times {T}_{Mq1}+2\times {T}_{Aq}+{T}_{inv}+{T}_{Mq}+{T}_{Aq}\). Combining with Table 6, we can calculate the time for the Open phase in Table 7.
In the Revoke phase, once the GM discovers that any signer has sent false information, he first performs the open algorithm to recover the true identity \(i\) of the signer. If the signer is traceable, then it deletes its unique number \({un}_{i}\) from the registry, and then samples a new PRSK \({{\varvec{k}}}{\prime}\stackrel{\boldsymbol{\$}}{\leftarrow }{S}_{1}^{2}\), computes \({{{\varvec{a}}}_{3}}^{T}{{\varvec{k}}}{\prime}={\overline{{b }_{1}}}^{\boldsymbol{{\prime}}}\in {\mathbb{R}}_{q}\) and uses the rest of the RSKs to construct the new RP set \({f}_{j}{\prime}\left(x\right)=\prod_{i=1}^{N-1}(x-{r}_{i})+{k}_{j}\) (\(j\in [0\), \(2)\)). Finally, the GM publishes the new RP set \({f}_{j}{\prime}\left(x\right)\) and the new RPK \({\overline{{b }_{1}}}^{\boldsymbol{{\prime}}}\). Besides, we use polynomial division to remove the revoked RSK which time complexity is \(O(Nq\text{log}\,q)\). The time cost is \(2\times N\times {T}_{Mq}\). Combining with Table 6, we can calculate the time for the Revoke phase in Table 7.
Communication overhead
In our scheme, the communication overhead mainly includes the communication cost between the GM and the signer when generating the signer’s public keys and private keys (C1), the communication cost when the GM distributes the RSKs (C2), and the communication cost when the signer sends the signature (C3). Table 5 shows the calculation formulas for these partial communication overheads. The communication overhead under different numbers of signers is shown in Fig. 4. The results show that our scheme only incurs a small communication overhead for large parameter sets, so our scheme is practical.
Trade-off analysis and large-scale practicality
We further analyze the trade-offs between functionality, efficiency, and security, as well as system behavior in large-scale and dynamic scenarios. LCGS-UCSL provides full post-quantum security, user-controlled sequential linkability, efficient polynomial-based revocation, balanced traceability, and anti-key-escrow properties simultaneously. Experiments under large-scale settings (\(N=500\), \(st\) = 501) and frequent revocation events confirm that:
-
(1)
Verification time remains constant regardless of the number of revoked users;
-
(2)
Communication overhead grows mildly and linearly with group size;
-
(3)
Revocation polynomial updates remain efficient even for large groups.
The complexity introduced by integration is justified by the comprehensive functionality. All modules are provably secure under lattice assumptions, so no new attack surfaces are introduced. Lightweight arithmetic and friendly parameters further ensure practical deployability.
Conclusion and future work
We propose an LCGS-UCSL (implicit linkability, explicit linkability, and sequential linkability). Our scheme enhances the GM with conditional opening and revocation capabilities, while preserving user-controlled linkability, which has the advantage that the open function of group signature is not lost, and our scheme can perform signature aggregation, which improves the efficiency of verifying signatures and reduces communication overhead. Our scheme is revocable, that is, when a malicious signer is found, the GM can revoke the signer’s signature authority. Our revocation method avoids both the time overhead of verifying the revocation list and the communication overhead of transmitting new revocation tokens through a secure channel each time. Our scheme uses NIZKPoK to verify the validity of signatures, reducing communication overhead. To reduce the power of GMs (i.e., their ability to trace the identity of signers at will), we divide signers into two categories: traceable signers and non-traceable signers. We use Cuckoo hash as a registry; the worst-case complexity of insertion, search, and deletion is \(O(1)\). We use KOE technology to randomize the public key, which hides information about whether the signer can be traced. We analyze the correctness, linkability (implicit linkability, explicit linkability, and sequential linkability), and the revocability, and prove the anonymity, the traceability, EUF-CMA, and non-frameability of our LCGS-UCSL in the ROM and the security of NIZKPoK of our scheme in the ROM. Finally, we simulate the time cost, storage overhead, and communication overhead of our scheme under secure parameters, and compare these metrics with those of other schemes. The results demonstrate that our scheme is practical and secure.
Currently, GM must recalculate RP after each revocation operation. This costs time. Moreover, the GM has to store each legitimate signer’s RSK. As the signer base grows, so does the storage demand. Future work will optimize the polynomial update to save time. We will also seek smaller secret keys and lighter management to reduce space.
Consent to publish
All authors agree to publish the paper in the journal.
Data availability
No datasets were generated or analysed during the current study.
References
Ajtai M (1999) Generating hard instances of the short basis problem. In Proceedings of international colloquium on automata, languages, and programming, pp 1–9
Bao Z, He D, Wang H et al (2023a) A group signature scheme with selective linkability and traceability for blockchain-based data sharing systems in E-health services. IEEE Internet Things J 10(23):21115–21128
Bao Z, He D, Wang H et al (2023b) BAP: a blockchain-assisted privacy-preserving authentication protocol with user-controlled data linkability for VANETs. IEEE Trans Intell Veh 9(02):4206–4220
Baum C, Damgård I, Lyubashevsky V, et al (2018) More efficient commitments from structured lattice assumptions. In International conference on security and cryptography for networks, pp. 368–385
Bellare M, Neven G (2006) Multi-signatures in the plain public-key model and a general forking lemma. In the 13th ACM conference on computer and communications security, pp 390–399
Bellare M, Shi H, Zhang C et al (2005) Foundations of group signatures: the case of dynamic groups. In Cryptographers’ Track at the RSA Conference, pp 136–153
Chaum D, Heyst E (1991) Group signatures. In 10th Annual international conference on the theory and applications of cryptographic techniques, pp. 257–265
Chen Y, He D, Peng C et al (2025) Lattice-based group signatures with user-controlled linkability and verifier conditional revocation. J Softw 36(10):4444–4460
Cowan G (1996) Lecture notes on data analysis. Universität Siegen, Siegen, Germany
Cremers C (2023) Scyther Manual. Security Protocol Verification Tool. Available: https://github.com/cascremers/scyther/blob/master/gui/scyther-manual.pdf 2023
Diaz J, Lehmann A (2021) Group signatures with user-controlled and sequential linkability. In 24th IACR international conference on practice and theory of public key cryptography, pp 360–388
Ducas L, Lyubashevsky V, Prest T (2014) Efficient identity-based encryption over NTRU lattices. In 20th International conference on the theory and application of cryptology and information security, pp. 22–41
Fiore D, Garms L, Kolonelos D, et al (2022) Ring signatures with user-controlled linkability. In 27th European symposium on research in computer security, pp 405–426
Gao S, Chen X, Li H et al (2024) Post-quantum secure group signature with verifier local revocation and backward unlinkability. Comput Stand Interfaces. https://doi.org/10.1016/j.csi.2023.103782
Garms L, Lehmann A (2019) Group signatures with selective linkability. In 22nd IACR International conference on practice and theory of public-key cryptography, pp 190–220
Gordon S, Katz J, Vaikuntanathan V (2010) A group signature scheme from lattice assumptions. In 16th International conference on the theory and application of cryptology and information security, pp 395–412
Grover L (1996) A fast quantum mechanical algorithm for database search, In 28th Annual ACM symposium on theory of computing, pp 212–219
Kohlweiss M, Miers I (2015) Accountable metadata-hiding escrow: a group signature case study. Proc Priv Enhanc Technol 2:206–221
Krenn S, Samelin K, Striecks C (2019) Practical group-signatures with privacy-friendly openings. In 14th International conference on availability, reliability and security, pp 1–10
Lattice Estimator Documentation (2021) Lattice Estimator 0.1 documentation. Available: https://lattice-estimator.readthedocs.io/en/latest/
Ling S, Nguygen K, Wang H, et al (2019) Accountable tracing signatures from lattices. In Cryptographers' track at the RSA conference, pp 556–576
London C, Gardham D, Drăgan C (2025) Dynamic group signatures with verifier-local revocation. In IEEE 38th computer security foundations symposium, pp 473–488
Lyubashevsky L (2012) Lattice signatures without trapdoors. In 31st annual international conference on the theory and applications of cryptographic techniques, pp 738–755
Lyubashevsky V, Neven G (2017) One-shot verifiable encryption from lattices. In 36th Annual international conference on the theory and applications of cryptographic techniques, pp 293–323
Lyubashevsky V, Nguyen N, Plancon M, et al (2021) Shorter lattice-based group signatures via ‘almost free’ encryption and other optimizations. In 27th international conference on the theory and application of cryptology and information security, pp 218–248
Micciancio D, Peikert C (2012) Trapdoors for lattices: simpler, tighter, faster, smaller. In 31st annual international conference on the theory and applications of cryptographic techniques, pp. 700–718
Micciancio D, Regev O (2007) Worst-case to average-case reductions based on Gaussian measures. SIAM J Comput 37(01):267–302
Nielsen M, Chuang I (2001) Quantum computation and quantum information. Cambridge University Press, Cambridge, p 02
Pagh R, Rodler F (2004) Cuckoo hashing. J Algorithms 51(2):122–144
Pino R, Lyubashevsky V, Seiler G (2018) Lattice-based group signatures and zero-knowledge proofs of automorphism stability. In ACM SIGSAC conference on computer and communications security, pp 574–591
PyCryptodome Documentation (2023) SHAKE256, PyCryptodome 3.23.0 documentation. Available: https://pycryptodome.readthedocs.io/en/latest/src/hash/shake256.html
Shor P (1999) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev 41(02):303–332
Tang Y, Li Y, Ye Q et al (2023) Lattice-based group signatures with time-bound keys via redactable signatures. IEEE Trans Inf Forensics Secur 18:2696–2708
Tang Y, Pan D, Ye Q et al (2024) Event-oriented linkable group signature from lattice. IEEE Trans Consum Electron 70(01):2224–2234
Tran N, Nguyen K, Liu D, et al (2025) Lattice-based group signatures in the standard model, revisited. In The international conference on the theory and application of cryptology and information security, pp 70–102
The Sage Developers (2025), SageMath (Version 10.7). Available: https://www.sagemath.org
Wikipedia (2024), Exponentiation by squaring, Wikipedia, The Free Encyclopedia, Available: https://en.wikipedia.org/wiki/Exponentiation_by_squaring
Wikipedia Contributors (2024) Discrete Fourier transform over a ring—Number-theoretic transform, Wikipedia, The Free Encyclopedia. Available: https://en.wikipedia.org/wiki/Discrete_Fourier_transform_over_a_ring#Number-theoretic_transform
Yue X, Xi M, Chen B et al (2021) A revocable group signatures scheme to provide privacy-preserving authentications. Mob Netw Appl 26(4):1412–1429
Funding
This work was supported by New Generation Artificial Intelligence National Science and Technology Major Project (Grant No. 2025ZD0123704), the National Natural Science Foundation of China (Grant No. 62572025), Beijing Natural Science Foundation (Grant No. 4242024), Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing (Grant No. GJJ-25-xxx), the Fundamental Research Funds for the Central Universities, China, and the Ant Group.
Author information
Authors and Affiliations
Contributions
Songshou Dong conceived and wrote this paper, and Yanqing Yao polished and revised it.
Corresponding author
Ethics declarations
Competing interests
The authors declare that they have no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendices
Appendix
For a single signature, Fig.
5 shows the results of the lattice estimator on (MSIS (\(n=1\), \(q={2}^{148}+100353\), \(\kappa =26\), length_bound = \(\sqrt{{\left(8\kappa {\sigma}_{{s}_{\text{1,2}}}\sqrt{2d}+16\kappa {\sigma}_{{s}_{\text{1,2}}}d\sqrt{2d}\right)}^{2}+{\left(8\kappa {\sigma}_{{s}_{3}}\sqrt{3d}+32{\sigma}_{{s}_{\text{1,2}}}{\sigma}_{r}d\sqrt{3d}\right)}^{2}}+4{\kappa }^{2}\sqrt{{\left(2\sigma \sqrt{2d}+4d\sigma \sqrt{2d}\right)}^{2}+{\left(\sqrt{3d}\right)}^{2}}\approx 171591679048461184\), \(m=5\), \(d=1152\), norm = 2-norm) and MLWE (\(n=1\), \(Q={2}^{149}+306689\), \(m=+\infty\), \({\sigma}_{s}=\frac{{2}^{79}}{\sqrt{3}}\approx 348986823692397603454976\), \({\sigma}_{e}=\frac{{2}^{79}}{\sqrt{3}}\approx 348986823692397603454976\))).
Result analysis
Result analysis:
SIS:
Lattice reduction attack: The computational cost is approximately \({2}^{177.3}\) operations.
LWE:
Unique shortest vector problem attack: The computational cost is approximately \({2}^{133.7}\) operations.
Bounded distance decoding attack: The computational cost is approximately \({2}^{132.5}\) operations.
Dual attacks: These have computational costs of approximately \({2}^{135.8}\) operations.
All of these computational costs are extremely high, far exceeding the practical computational capabilities available now and for the foreseeable future.
For aggregated signature, Fig.
6 shows the results of the lattice estimator on (MSIS (\(n=1\), \({2}^{148}+100353\), \(\kappa =26\), length_bound = \(\sqrt{{\left(8\kappa {\sigma}_{{s}_{\text{1,2}}}\sqrt{2d}+16\kappa {\sigma}_{{s}_{\text{1,2}}}d\sqrt{2d}\right)}^{2}+{\left(8\kappa {\sigma}_{{s}_{3}}\sqrt{3d}+32{\sigma}_{{s}_{\text{1,2}}}{\sigma}_{r}d\sqrt{3d}\right)}^{2}}+4{\kappa }^{2}\sqrt{{\left(2\sigma \sqrt{2d}+4d\sigma \sqrt{2d}\right)}^{2}+{\left(\sqrt{3d}\right)}^{2}}\approx 85795782064014163968\), \(m=5\), \(d=1152\), norm = 2-norm) and MLWE (\(n=1\), \(Q={2}^{149}+306689\), \(m=+\infty\), \({\sigma}_{s}=\frac{{2}^{79}\times ({st}_{i}-1)}{\sqrt{3}}\approx 170403722506053506564096\), \({\sigma}_{e}=\frac{{2}^{79}\times ({st}_{i}-1)}{\sqrt{3}}\approx 170403722506053506564096\))).
Result analysis
SIS:
Lattice reduction attack: The computational cost is approximately \({2}^{128.2}\) operations.
LWE:
Unique shortest vector problem attack: The computational cost is approximately \({2}^{237.4}\) operations.
Bounded distance decoding attack: The computational cost is approximately \({2}^{235.5}\) operations.
Dual attacks: These have computational costs of approximately \({2}^{243.4}\) operations.
All of these computational costs are extremely high, far exceeding the practical computational capabilities available now and for the foreseeable future.
Remark 7
Ref. Cowan (1996) introduced how to convert a bounded uniform distribution into a Gaussian distribution, as follows:
For the interval \([-l\), \(l)\), the transformed Gaussian distribution is \({\mathcal{D}}_{{\mathbb{Z}}, \sigma }\) (\(\sigma =\frac{l}{\sqrt{3}}\)).
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/
About this article
Cite this article
Dong, S., Yao, Y. An efficient lattice-based conditional privacy-preserving group signature with user-controlled and sequential linkability. Cybersecurity 9, 210 (2026). https://doi.org/10.1186/s42400-026-00613-3
Received:
Accepted:
Published:
Version of record:
DOI: https://doi.org/10.1186/s42400-026-00613-3