New Quantum-Proof Group Signature Puts Privacy Control in Users’ Hands

Cryptographers at Beihang University have unveiled a new digital signature scheme designed to survive the quantum era while handing ordinary users unprecedented control over their own privacy. The scheme, described in the open-access journal Cybersecurity, is called LCGS-UCSL, short for lattice-based conditional privacy-preserving group signature with user-controlled and sequential linkability. Songshou Dong and Yanqing Yao, both affiliated with the School of Cyber Science and Technology and the Beijing Advanced Innovation Center for Future Blockchain and Privacy Computing, argue that their construction fills a long-standing gap: no previous group signature scheme has simultaneously offered post-quantum security, user-controlled linkability, efficient revocation, and balanced traceability.

Group signatures, first proposed by David Chaum and Eugene van Heyst in 1991, allow a member of a group to sign messages anonymously on behalf of the collective. Anyone holding the group’s public key can verify that a valid group member signed the message, but the signer’s individual identity remains hidden within the anonymity set. To prevent abuse of this anonymity, a designated opener typically holds the power to reveal who signed a given message. The tension at the heart of the technology is obvious: anonymity is valuable, but so is accountability, and traditional designs concentrate enormous tracing power in the hands of the group manager.

The new work builds on a concept pioneered by Diaz and Lehmann at the PKC 2021 conference: group signatures with user-controlled and sequential linkability, or GS-UCSL. In such schemes, signers themselves decide which signatures can be linked, rather than depending on a central authority to perform the linking. Linkability matters in practical settings. A vehicle broadcasting sensor readings to a data lake, for example, may need to prove that a sequence of anonymous reports arrived in the original chronological order, because the ordering itself carries meaning. A fuel-level sequence of 35, 45, 30 and then 40 liters within a short window might signal tampering, whereas 45, 40, 35 and 30 would look normal. Contact tracing systems face similar demands when pseudonymous data spans multiple rotating pseudonyms. The original GS-UCSL scheme, however, suffered three fatal limitations: it was not post-quantum secure, it offered no mechanism to revoke malicious signers, and it omitted traceability entirely.

Dong and Yao’s answer rests on lattice cryptography, the mathematical foundation underlying most post-quantum proposals. Lattice problems such as Module Learning With Errors (MLWE) and Module Short Integer Solution (MSIS) are believed to resist attacks even by large-scale quantum computers running Shor’s algorithm, which would demolish schemes built on integer factorization or discrete logarithms. The authors prove their scheme’s anonymity, traceability, existential unforgeability under chosen-message attack, and non-frameability in the random oracle model, grounding each property in the hardness of these lattice assumptions. Parameter analysis with the Lattice Estimator tool suggests attack costs far beyond practical reach, with the cheapest known attacks requiring on the order of 2 to the power 128 operations or more.

One of the scheme’s most distinctive features is its approach to revocation. Existing revocable group signatures typically rely on revocation lists, whose verification cost grows with the number of revoked members, or on revocation tokens distributed through secure channels, which impose heavy communication overhead. The new design instead uses a revocation polynomial. The group manager encodes each legitimate signer’s revocation secret into a polynomial and publishes it; a signer proves membership in a zero-knowledge proof by evaluating the polynomial at their own secret value. When a malicious member must be expelled, the manager simply resamples the secret and recomputes the polynomial from the remaining values. No revocation list needs to be checked at verification time, no member keys need to be reissued, and the privacy of revoked users is preserved. Verification cost remains constant regardless of how many users have been revoked.

To curb the group manager’s tracing power, the scheme borrows key-oblivious encryption, a primitive introduced by Kohlweiss and Miers and later instantiated on lattices by Ling and colleagues. During registration, the manager rerandomizes each user’s encryption public key. Thanks to the key-oblivious property, no one without the original secret key and the randomness can tell whether a given randomized key is traceable. The manager silently tags some users as traceable and others as non-traceable, and the users themselves cannot detect which category they fall into. When signing, each user encrypts identity information under their own randomized key; only traceable users’ identities can later be recovered by the opener. This splits the group into traceable and non-traceable types without anyone’s awareness, restraining the manager from arbitrarily unmasking every signer. A cuckoo hash table, which guarantees worst-case constant-time insertion, lookup and deletion, serves as the manager’s private registry of traceable users.

Linkability in the scheme comes in three flavors, all under user control. Implicit linkability assigns each signature a pseudonym derived from a scope value and the signer’s secret key: signatures within the same scope are automatically linkable, while those across different scopes remain unlinkable unless the signer proves otherwise. Explicit linkability lets a signer voluntarily claim a set of signatures after the fact. Sequential linkability goes further, allowing a signer to produce a proof that a chain of linked signatures was generated in strict chronological order with no omissions. The mechanism uses lightweight hash chains derived from the signer’s secret key and a state counter, with unique sequential values checked against an append-only bulletin board to defeat replay, reordering and selective disclosure attacks. Recovering the signer’s secret from a pseudonym would require solving the MSIS problem, which is computationally infeasible.

Efficiency was a central design goal. The scheme integrates signature aggregation with non-interactive zero-knowledge proofs of knowledge to enable batch verification of sequentially linked signatures. In experiments implemented in SageMath on a laptop with an Intel Core i7-8650U processor, the authors report that aggregating 500 linked signatures compresses the signature size by roughly 81 percent and cuts verification time by about 83 percent. Setup, key generation, verification and opening all complete within one second; signing and revocation finish within about 3.5 seconds. Joining 500 users simultaneously offline took roughly 982 seconds in total, though a single user’s join takes only a few seconds. Communication overhead grows only mildly and linearly with group size, and verification time stays constant regardless of the number of revoked users, which the authors highlight as critical for large-scale deployments such as vehicular networks and blockchain-based data sharing.

The formal security analysis proceeds through sequences of games. Anonymity reduces to the hiding property of an underlying lattice commitment scheme by Baum and colleagues plus the indistinguishability of a verifiable encryption scheme by Lyubashevsky and Neven. Traceability, unforgeability and non-frameability share a unified proof structure: any adversary who forges a signature can be used, via the general forking lemma, to extract a solution to the MSIS problem, with the three properties distinguished by the adversary’s goals and oracle access rather than by structurally different proofs. The authors also validated the protocol with the automated verification tool Scyther, which confirmed the security of the message flows among the group manager, signer and verifier. They acknowledge that the security proofs rely on the random oracle model, consistent with all state-of-the-art lattice-based group signatures of this scope, and note that achieving such comprehensive functionality in the standard model remains an open problem. Hash functions are instantiated with the NIST-standardized, post-quantum-secure SHAKE-256.

The researchers acknowledge remaining limitations and outline future work. Currently, the group manager must recompute the revocation polynomial after every revocation operation, which costs time, and the manager must store each legitimate signer’s revocation secret, so storage demand grows with the signer base. The team plans to optimize polynomial updates and to seek smaller secret keys and lighter management overhead. Even so, the authors conclude that LCGS-UCSL achieves comprehensive functionality with competitive efficiency, marking the first post-quantum-secure group signature scheme to combine user-controlled sequential linkability, lightweight polynomial revocation, oblivious traceability classification and batch verification. For privacy-critical sequential scenarios ranging from intelligent transportation to contact tracing and time-series data authentication, the scheme offers a blueprint for staying anonymous, staying accountable, and staying secure against the quantum computers of the future.

Subject of Research: A post-quantum lattice-based group signature scheme with user-controlled and sequential linkability and efficient revocation

Article Title: An efficient lattice-based conditional privacy-preserving group signature with user-controlled and sequential linkability

Article References: Dong, S., & Yao, Y. (2026). An efficient lattice-based conditional privacy-preserving group signature with user-controlled and sequential linkability. Cybersecurity, 9(1), Article 210. https://doi.org/10.1186/s42400-026-00613-3

Image Credits: AI Generated

DOI: 10.1186/s42400-026-00613-3

Keywords: group signatures, lattice cryptography, post-quantum security, user-controlled linkability, sequential linkability, revocation, zero-knowledge proofs, key-oblivious encryption, cuckoo hashing, anonymity, traceability, batch verification