International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Gilad Asharov , Bar-Ilan University
Anirudh Chandramouli , Bar-Ilan University
Download:
DOI: 10.1007/978-3-031-58740-5_11 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
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. Our protocol is optimal (up to expectation) for messages of length $L \in \Omega(n \log^2 n)$. Our main contribution is a framework for obtaining \emph{perfectly} secure broadcast with an expected constant number of rounds from a \emph{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(\poly \log n)$ bits. All our protocols are adaptively secure.
BibTeX
@inproceedings{eurocrypt-2024-34042,
  title={Perfect (Parallel) Broadcast in Constant Expected Rounds via Statistical VSS},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-58740-5_11},
  author={Gilad Asharov and Anirudh Chandramouli},
  year=2024
}