Paper 2026/2890
Byzantine Agreement with Signature Tokens
Abstract
We investigate the power and limitations of quantum cryptography in distributed consensus protocols. Specifically, we study the fundamental problem of Byzantine Agreement in partial synchrony, in a setting in which each party has access to a finite number $k$ of signature tokens. Classically, this problem is solvable only when less than one-third of the parties can be faulty (Dwork, Lynch, Stockmeyer 1988). We prove that protocols with signature tokens can bypass this lower bound by designing a protocol that remains secure against up to a $\frac{2^{k+1}-1}{2^{k+2}-1}$-fraction of faults. In particular, with $k=\Theta(\log n)$, where $n$ denotes the number of parties, our protocol solves Byzantine Agreement in partial synchrony assuming only an honest majority. Conversely, we prove that $\Omega(\log n)$ signature tokens are necessary for such a result. Finally, for $k=1$, we prove that the fault-tolerance threshold of $3/7$ achieved by our protocol is the best possible.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- ConsensusByzantine AgreementQuantum Cryptography
- Contact author(s)
-
efronyuv @ ias edu
mahimna @ purdue edu
sm5540 @ columbia edu
tim roughgarden @ gmail com - History
- 2026-11-16: approved
- 2026-11-13: received
- See all versions
- Short URL
- https://ia.cr/2026/2890
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2890,
author = {Yuval Efron and Mahimna Kelkar and Saachi Mutreja and Tim Roughgarden},
title = {Byzantine Agreement with Signature Tokens},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2890},
year = {2026},
url = {https://eprint.iacr.org/2026/2890}
}