Briefing
Existing multi-signature schemes fail to achieve the critical combination of tight security in the multi-user setting and the efficiency of key aggregation, leading to security loss that scales with the number of participants. This research introduces two novel constructions, Skewer-NI and Skewer-PF, which are the first to be formally proven tightly secure under the Discrete Logarithm assumption in the Random Oracle Model while simultaneously supporting key aggregation. This new primitive enables the creation of highly efficient, cryptographically robust wallets and on-chain governance systems where security loss does not scale with the number of users, fundamentally improving the security model for decentralized applications.
Context
The prevailing challenge in multi-signature design was the “security loss” inherent in multi-user environments, where the security reduction factor scales linearly with the number of users in the system. This non-tight reduction means that as a decentralized network grows, the assumed security margin of its cryptographic primitives effectively shrinks. While prior work achieved tight security for a single user or multi-user security without aggregation, a foundational limitation persisted → no scheme could combine the cryptographic efficiency of key aggregation with a tight security proof in the multi-user setting, leaving large-scale decentralized systems vulnerable to increasingly efficient attacks as user bases grew.
Analysis
The paper’s core mechanism is a novel integration of key-evolving techniques with a strengthened cryptographic primitive called trapdoor-detectable zero-knowledge. The new schemes, Skewer-NI and Skewer-PF, are designed from the ground up to operate within a multi-user environment, rather than attempting to adapt a single-user scheme. Skewer-NI is a pairing-based construction that produces a single, constant-size signature proof in a non-interactive manner, optimizing for verification efficiency.
Skewer-PF achieves a two-round, pairing-free construction, optimizing for deployment in resource-constrained environments. By focusing the design on the multi-user setting, the security reduction becomes independent of the total number of signers, ensuring the cryptographic security remains constant regardless of network size.
Parameters
- Tight Multi-User Security → The security reduction factor is independent of the total number of signers, preventing security degradation as the system scales.
- Key Aggregation Feature → The final signature is a single, compact proof, significantly reducing on-chain data and verification cost.
- Skewer-NI Construction → A non-interactive, pairing-based scheme resulting in a constant-size, single-element signature.
- Skewer-PF Construction → A two-round, pairing-free scheme that achieves the same security properties with simpler cryptographic assumptions.
Outlook
This research opens a new avenue for constructing highly scalable and secure cryptographic primitives. In the near term, the Skewer schemes will be crucial for developing next-generation, non-interactive threshold wallets and private governance protocols that can scale to millions of users without compromising their security model. The long-term implication is the potential for all foundational blockchain primitives → from block production to transaction authorization → to be re-architected using tight multi-user security, which will be essential for enterprise adoption and the eventual transition to quantum-resistant systems.
Verdict
The introduction of tightly secure, aggregatable multi-signatures establishes a new foundational security standard for all decentralized systems relying on collective authorization.
