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 .