Paper 2021/1403

Efficient Adaptively-Secure Byzantine Agreement for Long Messages

Amey Bhangale, University of California, Riverside
Chen-Da Liu-Zhang, Carnegie Mellon University
Julian Loss, Helmholtz Center for Information Security
Kartik Nayak, Duke University
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 'all but simple' and involves an interesting new application of Mc Diarmid's inequality to obtain 'optimal' corruption thresholds.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Byzantine agreement blockchain communication complexity
Contact author(s)
amey bhangale @ ucr edu
cliuzhan @ andrew cmu edu
lossjulian @ gmail com
kartik @ cs duke edu
History
2022-06-06: revised
2021-10-18: received
See all versions
Short URL
https://ia.cr/2021/1403
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1403,
      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{https://eprint.iacr.org/2021/1403}},
      url = {https://eprint.iacr.org/2021/1403}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.