Byzantine Fault-Tolerant Post-Quantum Distributed Quorum Signatures
2026-07-20 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors address the challenge of creating small, efficient post-quantum quorum signatures, which prove that a group agreed on something with minimal data. Since current solutions get bigger and slower as more nodes sign, they propose a new method called Distributed Quorum Signature (DQS). DQS uses regular digital signatures combined with a special broadcast protocol to turn network messages into local events, keeping message size constant regardless of group size. This approach keeps security strong and communication overhead manageable, and it performs comparably to existing pre-quantum methods in large systems.
Threshold signaturesAggregate signaturesMulti-signaturesPost-quantum cryptographyByzantine fault toleranceDistributed systemsDigital signaturesBracha broadcastQuorum certificatesNetwork communication complexity
Authors
Quentin Kniep, Jakub Sliwinski, Roger Wattenhofer
Abstract
Threshold, aggregate, and multi-signatures -- which we collectively call quorum signatures -- certify that a quorum of nodes endorsed a statement, with a certificate as small as a single signature. No constant-size post-quantum quorum signature is known: all candidates grow with the number of signers and are slow to aggregate, making quorum signatures the hardest obstacle to migrating byzantine fault-tolerant systems to post-quantum security. In this paper, we sidestep this open cryptographic problem by changing how the protocol communicates. We introduce a primitive we call Distributed Quorum Signature (DQS), built solely from ordinary digital signatures and a Bracha-style approval broadcast. DQS turns certificates from network messages into local events. Two event types divide the roles certificates play: weak certificates capture safety, strong certificates capture liveness. In DQS every message is constant size, fitting a single datagram regardless of the number of nodes. The total communication is quadratic, and no security assumptions change. In a large distributed system, the overhead of post-quantum DQS is competitive with the canonical pre-quantum BLS scheme.