Optimal communication complexity of authenticated byzantine agreement

Atsuki Momose, Ling Ren

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ≤ 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 ≤ (1/2 − ε)n in the standard PKI model.

Original languageEnglish (US)
Title of host publication35th International Symposium on Distributed Computing, DISC 2021
EditorsSeth Gilbert
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772105
DOIs
StatePublished - Oct 1 2021
Event35th International Symposium on Distributed Computing, DISC 2021 - Virtual, Freiburg, Germany
Duration: Oct 4 2021Oct 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume209
ISSN (Print)1868-8969

Conference

Conference35th International Symposium on Distributed Computing, DISC 2021
Country/TerritoryGermany
CityVirtual, Freiburg
Period10/4/2110/8/21

Keywords

  • Byzantine Agreement
  • Communication Complexity
  • Lower Bound

ASJC Scopus subject areas

  • Software

Fingerprint

Dive into the research topics of 'Optimal communication complexity of authenticated byzantine agreement'. Together they form a unique fingerprint.

Cite this