International Association for Cryptologic Research

International Association
for Cryptologic Research


Efficient Adaptively-Secure Byzantine Agreement for Long Messages

Amey Bhangale , UC Riverside
Chen-Da Liu-Zhang , NTT Research
Julian Loss , CISPA Helmholtz Center
Kartik Nayak , Duke University
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: We investigate the communication complexity of Byzantine agreement protocols for long messages against an adaptive adversary. In this setting, prior $n$-party protocols either achieved a communication complexity of $O(nl\cdot\poly(\kappa))$ or $O(nl + n^2 \cdot \poly(\kappa))$ for $l$-bit long messages and security parameter $\kappa$. 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 'almost optimal' corruption thresholds.
Video from ASIACRYPT 2022
  title={Efficient Adaptively-Secure Byzantine Agreement for Long Messages},
  author={Amey Bhangale and Chen-Da Liu-Zhang and Julian Loss and Kartik Nayak},