Welcome to the resource topic for 2023/1172
Communication and Round Efficient Parallel Broadcast Protocols
Authors: Ittai Abraham, Kartik Nayak, Nibesh ShresthaAbstract:
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.
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 .