Asymptotically Optimal Early Termination for Dishonest Majority Broadcast

Giovanni Deligios; Ivana Klasovita; Chen-Da Liu-Zhang

Paper 2024/1656

Asymptotically Optimal Early Termination for Dishonest Majority Broadcast

Giovanni Deligios

, ETH Zurich

Ivana Klasovita, ETH Zurich

Chen-Da Liu-Zhang

, Lucerne University of Applied Sciences and Arts, Web3 Foundation

Abstract

Deterministic broadcast protocols among $n$ parties tolerating $t$ corruptions require $min {f + 2, t + 1}$ rounds, where $f \leq t$ is the actual number of corruptions in an execution of the protocol. We provide the first protocol which is optimally resilient, adaptively secure, and asymptotically matches this lower bound for any $t < (1 - ε) n$ . By contrast, the best known algorithm in this regime by Loss and Nielsen (EUROCRYPT'24) always requires rounds. Our main technical tool is a generalization of the notion of polarizer introduced by Loss and Nielsen, which allows parties to obtain transferable cryptographic evidence of missing messages with fewer rounds of interaction.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published by the IACR in EUROCRYPT 2025
DOI: 10.1007/978-3-031-91092-0_5
Keywords: Broadcast Early Stopping Dishonest Majority Round Complexity
Contact author(s): gdeligios @ ethz ch
ivanakl @ ethz ch
chendaliu @ gmail com
History: 2025-05-16: revised; 2024-10-14: received; See all versions
Short URL: https://ia.cr/2024/1656
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1656,
      author = {Giovanni Deligios and Ivana Klasovita and Chen-Da Liu-Zhang},
      title = {Asymptotically Optimal Early Termination for Dishonest Majority Broadcast},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1656},
      year = {2024},
      doi = {10.1007/978-3-031-91092-0_5},
      url = {https://eprint.iacr.org/2024/1656}
}