CISPA
Browse
2021-1403.pdf (895.76 kB)

Efficient Adaptively-Secure Byzantine Agreement for Long Messages.

Download (895.76 kB)
preprint
posted on 2024-04-11, 14:45 authored by Amey Bhangale, Chen-Da Liu-Zhang, Julian Loss, 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 · poly(κ)) or O(nl+n 2 · poly(κ)) for l-bit long messages. We improve the state of the art by presenting protocols with communication complexity O(nl + n · poly(κ)) in both the synchronous and asynchronous communication models. The synchronous protocol tolerates t ≤ (1 − ε) n 2 corruptions and assumes a VRF setup, while the asynchronous protocol tolerates t ≤ (1 − ε) 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.

History

Primary Research Area

  • Algorithmic Foundations and Cryptography

BibTeX

@misc{Bhangale:Liu-Zhang:Loss:Nayak:2021, title = "Efficient Adaptively-Secure Byzantine Agreement for Long Messages.", author = "Bhangale, Amey" AND "Liu-Zhang, Chen-Da" AND "Loss, Julian" AND "Nayak, Kartik", year = 2021, month = 10 }

Usage metrics

    Categories

    No categories selected

    Licence

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC