Scaling Anonymity Sets in Privacy Preserving Signatures

This direction is merged into another direction: linear signature scaling. Its last version stays readable and citable here.

Version 1 of 118 papers18 conceptsfrozen 2026-10-04

In digital privacy, there is a fundamental tension between the size of a "crowd" you can hide in and the cost of proving you belong to it. Privacy-preserving signatures—specifically ring signatures and group signatures—allow a user to sign a message on behalf of a set of participants without revealing which specific member they are.

However, for years, these schemes hit a "linear wall": as the number of potential signers (the anonymity set) grew, the size of the signature and the time required to verify it grew in lockstep. Recent research has focused on breaking this linear dependency, moving toward logarithmic or even constant-size signatures that allow for massive, global-scale anonymity.

The Linear Scaling Problem

To understand the breakthrough, we must first understand the bottleneck. In a traditional ring signature, a signer proves they possess one of the private keys corresponding to a list of public keys. Early constructions, such as those discussed by Xiaofeng Chen and Kwangjo Kim in A New ID-based Group Signature Scheme from Bilinear Pairings, often resulted in signatures that grew proportionally with the group size ($O(N)$).

As Jia Wang notes in An efficient anonymous revocable ring signature scheme, this linear growth makes large-scale applications like national electronic voting or global decentralized networks impractical. If a ring size reaches millions, an $O(N)$ signature becomes a massive data burden that drains battery life on mobile devices and clogs network bandwidth.

Achieving Logarithmic Efficiency

The shift from linear ($O(N)$) to logarithmic ($O(\log N)$) scaling is the most significant leap in recent years. This is often achieved by replacing a flat list of public keys with a hierarchical structure, such as a Merkle tree or a cryptographic accumulator.

In Zero-Knowledge Arguments for Lattice-Based Accumulators, Benôıt Libert, San Ling, and Khoa Nguyen demonstrate how to use lattice-based accumulators to prove set membership. Instead of attaching every public key to the signature, the signer provides a "membership proof" relative to a single compressed value (the accumulator). Because the proof size corresponds to the depth of a tree rather than the number of leaves, the signature size only increases slightly even as the group size doubles.

This efficiency is critical for blockchain privacy. Tsz Hon Yuen and colleagues introduced RingCT 3.0, which leverages these sub-linear membership proofs to reduce signature sizes by up to 98% compared to earlier confidential transaction protocols. This allows blockchains like Monero to support much larger anonymity sets without sacrificing performance.

The Challenge of Revocation

While ring signatures are ad-hoc, group signatures involve a group manager who can "unmask" a signer if necessary. The difficulty here is revocation: how do you kick a member out of the group without forcing every remaining member to update their keys or making the signature size explode?

Giuseppe Ateniese, Dawn Song, and Gene Tsudik pioneered Quasi-Efficient Revocation, which maintains constant-length signatures regardless of how many members are revoked. More recently, Saba Eskandarian and Ben Fisch explored Post-Quantum Group Signatures from Symmetric Primitives, showing that even when using quantum-resistant building blocks like hash functions, it is possible to maintain practical signature sizes for large-scale hardware attestation.

Practical Deployments and Constraints

The push for sub-linear scaling isn't just theoretical; it's driven by the constraints of modern infrastructure:

  1. Mobile and IoT: In EPDA: Enhancing Privacy-Preserving Data Authentication for Mobile Crowd Sensing, Jingwei Liu and Liehuang Zhu emphasize that mobile devices cannot handle the computational drain of linear-time verification.
  2. Vehicular Networks (VANETs): Mingxing He and Xiao Zheng highlight in Privacy-preserving Communication for Vehicular that real-time safety messages require signatures that can be verified in milliseconds, even when the "crowd" of nearby cars is large.
  3. Decentralized Identity: Bin Xiao and Keke Gai propose SLVC-DIDA, a "signature-less" approach to verifiable credentials that aims to bypass the performance degradation of traditional ring signatures entirely.

Future Directions: Post-Quantum and Beyond

As we move toward a post-quantum world, the math becomes harder. Lattice-based and code-based assumptions, such as those explored by Martianus Frederic Ezerman in Provably Secure Group Signature Schemes from Code-Based Assumptions, naturally result in larger keys and signatures than classical elliptic curve cryptography. The current frontier of research is finding ways to apply logarithmic scaling to these "heavy" primitives, ensuring that even in a world with quantum computers, we can still hide in a crowd of millions without the crowd becoming a burden.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_scaling_anonymity_sets_in_privacy_preser_5cc1986f,
  title = {Scaling Anonymity Sets in Privacy Preserving Signatures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-anonymity-sets-in-privacy-preserving-signatures/rdr_5cc1986fbf4f4916a6f782cc726fbcc1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_scaling_anonymity_sets_in_privacy_preser_5cc1986f_v1,
  title = {Scaling Anonymity Sets in Privacy Preserving Signatures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/scaling-anonymity-sets-in-privacy-preserving-signatures/rdr_5cc1986fbf4f4916a6f782cc726fbcc1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}