Paper 2023/1172

Communication and Round Efficient Parallel Broadcast Protocols

Ittai Abraham, Intel Labs
Kartik Nayak, Duke University
Nibesh Shrestha, Supra Research

This work focuses on the parallel broadcast primitive, where each of the $n$ parties wish to broadcast their $\ell$-bit input in parallel. We consider the authenticated model with PKI and digital signatures that is secure against $t < n/2$ Byzantine faults under a synchronous network. We show a generic reduction from parallel broadcast to a new primitive called graded parallel broadcast and a single instance of validated Byzantine agreement. Using our reduction, we obtain parallel broadcast protocols with $O(n^2 \ell + \kappa n^3)$ communication ($\kappa$ denotes a security parameter) and expected constant rounds. Thus, for inputs of size $\ell = \Omega(n)$ bits, our protocols are asymptotically free. Our graded parallel broadcast uses a novel gradecast protocol with multiple grades with asymptotically optimal communication complexity of $O(n \ell + \kappa n^2)$ for inputs of size $\ell$ bits. We also present a multi-valued validated Byzantine agreement protocol with asymptotically optimal communication complexity of $O(n \ell + \kappa n^2)$ for inputs of size $\ell$ bits in expectation and expected constant rounds. Both of these primitives are of independent interest.

Available format(s)
Cryptographic protocols
Publication info
Parallel broadcastvalidated byzantine agreementgradecastsynchrony
Contact author(s)
ittai abraham @ intel com
kartik @ cs duke edu
nibeshrestha2 @ gmail com
2023-07-30: approved
2023-07-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ittai Abraham and Kartik Nayak and Nibesh Shrestha},
      title = {Communication and Round Efficient Parallel Broadcast Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1172},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.