Welcome to the resource topic for 2024/376
Title:
Õptimal Parallel Broadcast
Authors: Gilad Asharov, Anirudh Chandramouli
Abstract:We study broadcast protocols in the information-theoretic model under optimal conditions, where the number of corruptions t is at most one-third of the parties, n. While worst-case \Omega(n) round broadcast protocols are known to be impossible to achieve, protocols with an expected constant number of rounds have been demonstrated since the seminal work of Feldman and Micali [STOC’88]. Communication complexity for such protocols has gradually improved over the years, reaching O(nL) plus expected O(n^4\log n) for broadcasting a message of size L bits.
This paper presents a perfectly secure broadcast protocol with expected constant rounds and communication complexity of O(nL) plus expected O(n^3 \log^2n) bits. In addition, we consider the problem of parallel broadcast, where n senders, each wish to broadcast a message of size L. We show a parallel broadcast protocol with expected constant rounds and communication complexity of O(n^2L) plus expected O(n^3 \log^2n) bits. Moreover, we show a lower bound for parallel broadcast, showing that our protocol is optimal up to logarithmic factors and in expectation.
Our main contribution is a framework for obtaining perfectly secure broadcast with an expected constant number of rounds from a statistically secure verifiable secret sharing. Moreover, we provide a new statistically secure verifiable secret sharing where the broadcast cost per participant is reduced from O(n \log n) bits to only O({\sf poly} \log n) bits. All our protocols are adaptively secure.
ePrint: https://eprint.iacr.org/2024/376
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 .