Efficient Adaptively-Secure Byzantine Agreement for Long Messages

Bhangale, Amey and Liu-Zhang, Chen-Da and Loss, Julian and Nayak, Kartik
(2022) Efficient Adaptively-Secure Byzantine Agreement for Long Messages.
In: ASIACRYPT 2022, 5-9 December 2022, Taipei, Taiwan.
Conference: ASIACRYPT International Conference on the Theory and Application of Cryptology and Information Security
(In Press)


Download (917kB) | Preview


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 \emph{all but simple} and involves an interesting new application of Mc Diarmid's inequality to obtain {\em almost optimal} corruption thresholds.


Actions (login required)

View Item View Item