Search papers, labs, and topics across Lattice.
This paper introduces Distributed Quorum Signatures (DQS), a novel primitive that enables post-quantum quorum signatures by transforming certificates from network messages into local events, thus sidestepping the limitations of existing candidates that grow with the number of signers. By utilizing ordinary digital signatures and a Bracha-style approval broadcast, DQS achieves constant-size messages regardless of the number of nodes, while maintaining quadratic total communication. The results show that DQS can compete with the pre-quantum BLS scheme in large distributed systems, making it a viable solution for achieving Byzantine fault tolerance in a post-quantum world.
Constant-size post-quantum quorum signatures are finally achievable, revolutionizing Byzantine fault tolerance in distributed systems.
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.
ETH