Cryptology ePrint Archive: Report 2018/1028

Synchronous Byzantine Agreement with Expected $O(1)$ Rounds, Expected $O(n^2)$ Communication, and Optimal Resilience

Ittai Abraham and Srinivas Devadas and Danny Dolev and Kartik Nayak and Ling Ren

Abstract: We present new protocols for Byzantine agreement in the synchronous and authenticated setting, tolerating the optimal number of $f$ faults among $n=2f+1$ parties. Our protocols achieve an expected $O(1)$ round complexity and an expected $O(n^2)$ communication complexity. The exact round complexity in expectation is 10 for a static adversary and 16 for a strongly rushing adaptive adversary. For comparison, previous protocols in the same setting require expected 29 rounds and expected $\Omega(n^3)$ communication. We also give a lower bound showing that expected $\Omega(f^2)$ communication is necessary against a strongly rushing adaptive adversary.

Category / Keywords:

Date: received 22 Oct 2018, last revised 7 Dec 2018

Contact author: kartik1507 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20181207:224035 (All versions of this report)

Short URL: ia.cr/2018/1028


[ Cryptology ePrint archive ]