Paper 2021/1403

Efficient Adaptively-Secure Byzantine Agreement for Long Messages

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


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
Byzantine agreementblockchaincommunication complexity
Contact author(s)
cliuzhan @ andrew cmu edu
kartik @ cs duke edu
lossjulian @ gmail com
amey bhangale @ ucr edu
2021-10-18: received
Short URL
Creative Commons Attribution


      author = {Amey Bhangale and Chen-Da Liu-Zhang and Julian Loss and Kartik Nayak},
      title = {Efficient Adaptively-Secure Byzantine Agreement for Long Messages},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1403},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.