Gradecast in Synchrony and Reliable Broadcast in Asynchrony with Optimal Resilience, Efficiency, and Unconditional Security

Ittai Abraham; Gilad Asharov

Paper 2022/264

Gradecast in Synchrony and Reliable Broadcast in Asynchrony with Optimal Resilience, Efficiency, and Unconditional Security

Ittai Abraham, VMWare Research

Gilad Asharov

, Bar-Ilan University

Abstract

We revisit Gradecast (Feldman and Micali, STOC'88) in Synchrony and Reliable Broadcast (Bracha, Information and Computation'87) in Asynchrony. For both tasks ,we provide new protocols that have three desirable properties: (1) \emph{optimal resilience}, tolerating $t<n/3$ malicious parties; (2) are \emph{communication-efficient}, where honest parties send just $O(n L)$ bits for a sender with a message of $L = \Omega(n \log n)$ bits; (3) and are \emph{unconditionally secure}, without needing to rely on any computational or setup assumptions (while having a statistical error probability). To the best of our knowledge, no previous work obtains all three properties simultaneously.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. PODC 2022
Keywords: gradecast reliable broadcast
Contact author(s): iabraham @ vmware com
Gilad Asharov @ biu ac il
History: 2022-05-30: last of 3 revisions; 2022-03-02: received; See all versions
Short URL: https://ia.cr/2022/264
License: CC BY

BibTeX

@misc{cryptoeprint:2022/264,
      author = {Ittai Abraham and Gilad Asharov},
      title = {Gradecast in Synchrony and Reliable Broadcast in Asynchrony with Optimal Resilience, Efficiency, and Unconditional Security},
      howpublished = {Cryptology ePrint Archive, Paper 2022/264},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/264}},
      url = {https://eprint.iacr.org/2022/264}
}