Paper 2026/2890

Byzantine Agreement with Signature Tokens

Yuval Efron, IAS
Mahimna Kelkar, Purdue University West Lafayette
Saachi Mutreja, Columbia University
Tim Roughgarden, IAS
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.