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:
- Anonymity Sets: In ring signatures used for blockchain privacy, signature size scales linearly with the number of decoy users. Michael Backes et al. demonstrate this limitation in Signatures with Flexible Public Key: A Unified Approach to Privacy-Preserving Signatures (Full Version), while Xiaofang Li et al. highlight how this forces ledgers to choose between small, vulnerable anonymity sets or bloated transaction sizes in A Blockchain Privacy Protection Scheme Based on Ring Signature. Jia Wang argues in An efficient anonymous revocable ring signature scheme that this linear growth creates a performance barrier for national-scale deployments like voting systems, where the participant pool could reach millions.
- User Revocation: In group signatures, kicking out a malicious user often requires a revocation list. Giuseppe Ateniese et al. point out in Quasi-Efficient Revocation of Group Signatures that standard schemes require signers to perform computational work that grows linearly with the number of revoked members, creating an efficiency drag over time.
- Threshold and Multi-Recipient Constraints: In threshold ring signatures, even if you decouple the signature size from the total group size, the data still scales linearly with the number of actual signers required to clear the threshold, as shown by Alexander Munch-Hansen et al. in Stronger Notions and a More Efficient Construction of Threshold Ring Signatures. Similarly, for multi-designated verifier signatures, Ivan Damgård et al. prove a theoretical lower bound in Stronger Notions and Constructions for Multi-Designated Verifier Signatures: any scheme providing both strong unforgeability and any-subset deniability must accept a signature size that scales linearly with the number of recipients.
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.