**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: **ia.cr/2021/1403

[ Cryptology ePrint archive ]