Paper 2023/1172

Communication and Round Efficient Parallel Broadcast Protocols

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 $$ communication ($$ denotes a security parameter) and expected constant rounds. Thus, for inputs of size $$ bits, our protocols are asymptotically free. Our graded parallel broadcast uses a novel gradecast protocol with multiple grades with asymptotically optimal communication complexity of $$ for inputs of size $$ bits. We also present a multi-valued validated Byzantine agreement protocol with asymptotically optimal communication complexity of $$ for inputs of size $$ bits in expectation and expected constant rounds. Both of these primitives are of independent interest.

Note: Full version of the paper published at FC'25.