Paper 2020/1569

Optimal Communication Complexity of Authenticated Byzantine Agreement

Atsuki Momose and Ling Ren

Abstract

Byzantine Agreement (BA) is one of the most fundamental problems in distributed computing, and its communication complexity is an important efficiency metric. It is well known that quadratic communication is necessary for BA in the worst case due to a lower bound by Dolev and Reischuk. This lower bound has been shown to be tight for the unauthenticated setting with $f < n/3$ by Berman et al. but a considerable gap remains for the authenticated setting with $n/3 \le f < n/2$. This paper provides two results towards closing this gap. Both protocols have a quadratic communication complexity and have different trade-offs in resilience and assumptions. The first protocol achieves the optimal resilience of $f < n/2$ but requires a trusted setup for threshold signature. The second protocol achieves near optimal resilience $f \le (1/2 - \varepsilon)n$ in the standard PKI model.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Byzantine agreementcommunication complexity
Contact author(s)
momose @ sqlab jp
History
2021-01-29: revised
2020-12-17: received
See all versions
Short URL
https://ia.cr/2020/1569
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1569,
      author = {Atsuki Momose and Ling Ren},
      title = {Optimal Communication Complexity of Authenticated Byzantine Agreement},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1569},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1569}},
      url = {https://eprint.iacr.org/2020/1569}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.