Welcome to the resource topic for 2021/1403
Title:
Efficient Adaptively-Secure Byzantine Agreement for Long Messages
Authors: Amey Bhangale, Chen-Da Liu-Zhang, 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 ‘all but simple’ and involves an interesting new application of Mc Diarmid’s inequality to obtain ‘optimal’ corruption thresholds.
ePrint: https://eprint.iacr.org/2021/1403
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .