Paper 2022/1266

Asymptotically Free Broadcast in Constant Expected Time via Packed VSS

Ittai Abraham, VMWare Research
Gilad Asharov, Bar-Ilan University
Shravani Patil, Indian Institute of Science Bangalore
Arpita Patra, Indian Institute of Science Bangalore

Broadcast is an essential primitive for secure computation. We focus in this paper on optimal resilience (i.e., when the number of corrupted parties $t$ is less than a third of the computing parties $n$), and with no setup or cryptographic assumptions. While broadcast with worst case $t$ rounds is impossible, it has been shown [Feldman and Micali STOC'88, Katz and Koo CRYPTO'06] how to construct protocols with expected constant number of rounds in the private channel model. However, those constructions have large communication complexity, specifically $\mathcal{O}(n^2L+n^6\log n)$ expected number of bits transmitted for broadcasting a message of length $L$. This leads to a significant communication blowup in secure computation protocols in this setting. In this paper, we substantially improve the communication complexity of broadcast in constant expected time. Specifically, the expected communication complexity of our protocol is $\mathcal{O}(nL+n^4\log n)$. For messages of length $L=\Omega(n^3 \log n)$, our broadcast has no asymptotic overhead (up to expectation), as each party has to send or receive $\mathcal{O}(n^3 \log n)$ bits. We also consider parallel broadcast, where $n$ parties wish to broadcast $L$ bit messages in parallel. Our protocol has no asymptotic overhead for $L=\Omega(n^2\log n)$, which is a common communication pattern in perfectly secure MPC protocols. For instance, it is common that all parties share their inputs simultaneously at the same round, and verifiable secret sharing protocols require the dealer to broadcast a total of $\mathcal{O}(n^2\log n)$ bits. As an independent interest, our broadcast is achieved by a packed verifiable secret sharing, a new notion that we introduce. We show a protocol that verifies $\mathcal{O}(n)$ secrets simultaneously with the same cost of verifying just a single secret. This improves by a factor of $n$ the state-of-the-art.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in TCC 2022
Perfect Security Byzantine Agreement Broadcast Secure Computation Communication Complexity
Contact author(s)
iabraham @ vmware com
Gilad Asharov @ biu ac il
shravanip @ iisc ac in
arpita @ iisc ac in
2022-09-26: approved
2022-09-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ittai Abraham and Gilad Asharov and Shravani Patil and Arpita Patra},
      title = {Asymptotically Free Broadcast in Constant Expected Time via Packed VSS},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1266},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.