CISPA
Browse
cispa_all_3866.pdf (895.76 kB)

Efficient Adaptively-Secure Byzantine Agreement for Long Messages

Download (895.76 kB)
conference contribution
posted on 2023-11-29, 18:26 authored by Amey Bhangale, Chen-Da Liu-Zhang, Julian LossJulian Loss, Kartik Nayak
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.

History

Preferred Citation

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

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)

Legacy Posted Date

2022-10-21

Open Access Type

  • Unknown

BibTeX

@inproceedings{cispa_all_3866, title = "Efficient Adaptively-Secure Byzantine Agreement for Long Messages", author = "Bhangale, Amey and Liu-Zhang, Chen-Da and Loss, Julian and Nayak, Kartik", booktitle="{International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT)}", year="2022", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC