Welcome to the resource topic for
**2023/1172**

**Title:**

Communication and Round Efficient Parallel Broadcast Protocols

**Authors:**
Ittai Abraham, Kartik Nayak, Nibesh Shrestha

**Abstract:**

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.

**ePrint:**
https://eprint.iacr.org/2023/1172

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 .