Cryptology ePrint Archive: Report 2020/1569

Optimal Communication Complexity of Byzantine Agreement, Revisited

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 $f < n/3$ by Berman et al. but a considerable gap remains for $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.

Category / Keywords: cryptographic protocols / Byzantine agreement, communication complexity

Date: received 16 Dec 2020

Contact author: momose at sqlab jp

Available format(s): PDF | BibTeX Citation

Version: 20201217:095722 (All versions of this report)

Short URL: ia.cr/2020/1569


[ Cryptology ePrint archive ]