DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2021.32

Optimal Communication Complexity of Authenticated Byzantine Agreement

Authors: Atsuki Momose and Ling Ren

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

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.

Cite as

Atsuki Momose and Ling Ren. Optimal Communication Complexity of Authenticated Byzantine Agreement. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{momose_et_al:LIPIcs.DISC.2021.32,
  author =	{Momose, Atsuki and Ren, Ling},
  title =	{{Optimal Communication Complexity of Authenticated Byzantine Agreement}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.32},
  URN =		{urn:nbn:de:0030-drops-148341},
  doi =		{10.4230/LIPIcs.DISC.2021.32},
  annote =	{Keywords: Byzantine Agreement, Communication Complexity, Lower Bound}
}

Search Results

Documents authored by Momose, Atsuki

Optimal Communication Complexity of Authenticated Byzantine Agreement

Abstract

Cite as

Thanks for your feedback!

Could not send message