Overcoming Linear Scaling in Group and Ring Signatures

33 concepts24 papers1 proposal

Imagine you want to sign a message anonymously on behalf of a group. In a classic ring signature, you prove that one of the public keys in a given set belongs to you, without revealing which one. To achieve this mathematically, traditional schemes construct an equation that explicitly binds every single public key in the anonymity set. If there are 10 keys, the signature contains 10 elements; if there are 10,000 keys, the signature balloons to 10,000 elements.

This is the linear scaling bottleneck. As noted by Xiaofeng Chen et al. in A New ID-based Group Signature Scheme from Bilinear Pairings, this lack of constant-size parameters severely limits deployment in large-scale or resource-constrained environments. Whether it is the size of the signature, the public key, or the verification time, linear growth forces a painful trade-off between strong privacy and system performance.

Where Linear Scaling Manifests

Linear overhead isn't confined to just the number of potential signers. It appears across several dimensions of multi-party and privacy-preserving cryptography:

Why Does It Scale Linearly?

To understand why this happens, consider how a verifier checks a signature. In a standard setting, the verifier must touch every identity share or public key to ensure no unauthorized party slipped through. For instance, in dynamic threshold decryption, Brian John King et al. explain in A Dynamic Threshold Decryption Scheme Using Bilinear Pairings that public shares are mathematically tied to specific user identities. This entanglement means adding or removing a participant triggers system-wide updates proportional to the group size.

The same linear bottleneck affects decentralized auditing and consensus. Yining Qi et al. demonstrate in Blockchain-Based Privacy-Preserving Public Auditing for Group Shared Data that verification costs scale linearly with the number of group participants, creating a computational bottleneck for large organizations. In distributed networks, Xiaohai Dai et al. note in Falcon: Advancing Asynchronous BFT Consensus for Lower Latency and Enhanced Throughput that the cumulative cost of threshold signature verification can bottleneck overall system throughput as the network scales to thousands of nodes.

Furthermore, post-quantum alternatives like lattice-based or code-based cryptography exacerbate this issue. As Martianus Frederic Ezerman et al. show in Provably Secure Group Signature Schemes from Code-Based Assumptions, early post-quantum group signatures inherently suffer from public key and signature sizes that scale linearly with the user base. Bin Xiao et al. note in Efficient and Post-Quantum Zero-Knowledge Proofs for Blockchain Confidential Transaction Protocols that lattice-based linear sum proofs naturally lack the logarithmic compression properties found in discrete-logarithm systems.

Breaking the Linear Barrier

To scale systems to millions of users—such as national voting or global decentralized identity schemes—cryptographers must compress these linear dependencies into sublinear or logarithmic forms.

The primary mechanism for doing this is replacing explicit set listings with cryptographic accumulators or succinct membership proofs. Instead of verifying against $N$ individual keys, the keys are hashed into a compressed root (like a Merkle tree). The signer then uses a zero-knowledge proof to demonstrate: "I know a secret key, and its corresponding public key exists within this compressed root."

Linear Scaling (Traditional):
Signature = [Key 1] + [Key 2] + [Key 3] + ...

+ [Key N] + [Proof]
(Size grows with N)

Logarithmic Scaling (Accumulator-based):
Signature = [Accumulator Root] + [Succinct Membership Proof]
(Size grows with log(N))

Using this approach, Benôıt Libert et al. designed zero-knowledge arguments for lattice-based accumulators in Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors, compressing signature sizes from $O(N)$ down to $O(\log N)$. Similarly, Gongxian Zeng et al. leverage non-interactive zero-knowledge functional proofs in Non-interactive Zero-Knowledge Functional Proofs to bypass the linear growth typically required when proving a secret belongs to a specific set.

The Trade-offs of Sublinear Scaling

While logarithmic scaling sounds strictly superior, it introduces a performance floor. Logarithmic proof systems often require heavy cryptographic machinery (such as complex zero-knowledge setups or recursive proof aggregation).

As Tsz Hon Yuen et al. observe in RingCT 3.0 for Blockchain Confidential Transaction: Shorter Size and Stronger Security, logarithmic proof systems incur a constant computational and storage overhead. For small anonymity sets, this constant overhead actually makes them less efficient than simple linear methods. The advantages of logarithmic scaling are only unlocked once the participant pool crosses a certain threshold.

Furthermore, achieving a fully compact signature—one that remains completely constant regardless of both the anonymity set and the number of actual signers—remains a steep challenge. As Alexander Munch-Hansen et al. note, fully compact systems currently rely on computationally expensive proof systems that are too heavy for high-performance, real-time applications.

Key Foundational Work

A New ID-based Group Signature Scheme from Bilinear Pairings (2003) — contributed 1 concept elements to this direction.
Quasi-Efficient Revocation of Group Signatures (2001) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_signature_scaling_9e0c5ab5,
  title = {linear signature scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-signature-scaling/rdr_9e0c5ab57bde488db17198734ab0d69d},
  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_linear_signature_scaling_9e0c5ab5_v1,
  title = {linear signature scaling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-signature-scaling/rdr_9e0c5ab57bde488db17198734ab0d69d/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake