Paper 2024/376

Perfect (Parallel) Broadcast in Constant Expected Rounds via Statistical VSS

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 $\mathrm{\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 $$ plus expected $$ for broadcasting a message of size $$ bits. This paper presents a perfectly secure broadcast protocol with expected constant rounds and communication complexity of $$ plus expected $$ bits. In addition, we consider the problem of parallel broadcast, where $$ senders, each wish to broadcast a message of size $$. We show a parallel broadcast protocol with expected constant rounds and communication complexity of $$ plus expected $$ bits. Our protocol is optimal (up to expectation) for messages of length $$. 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 $$ bits to only $$ bits. All our protocols are adaptively secure.