Cryptology ePrint Archive: Report 2021/1403

Efficient Adaptively-Secure Byzantine Agreement for Long Messages

Amey Bhangale and Chen-Da Liu-Zhang and Julian Loss and Kartik Nayak

Abstract: We investigate the communication complexity of Byzantine agreement protocols for long messages against an adaptive adversary. In this setting, prior results either achieved a communication complexity of $O(nl\cdot\poly(\kappa))$ or $O(nl + n^2 \cdot \poly(\kappa))$ for $l$-bit long messages. We improve the state of the art by presenting protocols with communication complexity $O(nl + n \cdot \poly(\kappa))$ in both the synchronous and asynchronous communication models. The synchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{2}$ corruptions and assumes a VRF setup, while the asynchronous protocol tolerates $t \le (1-\epsilon) \frac{n}{3}$ corruptions under further cryptographic assumptions. Our protocols are very simple and combine subcommittee election with the recent approach of Nayak et al. (DISC `20). Surprisingly, the analysis of our protocols is \emph{all but simple} and involves an interesting new application of Mc Diarmid's inequality to obtain {\em optimal} corruption thresholds.

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

Date: received 17 Oct 2021

Contact author: cliuzhan at andrew cmu edu, kartik at cs duke edu, lossjulian at gmail com, amey bhangale at ucr edu

Available format(s): PDF | BibTeX Citation

Version: 20211018:061706 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]