Communication and Round Efficient Parallel Broadcast Protocols

doi:10.1007/978-3-032-07024-1_19

Communication and Round Efficient Parallel Broadcast Protocols

2026-01-01

0

PRE

AI

DOI：10.1007/978-3-032-07024-1_19

Original

Original request for help

Save

Abstract

En 中文

This work focuses on the parallel broadcast primitive, where each of the n parties wish to broadcast their l-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)l + kappa n(3)) communication (kappa denotes a security parameter) and expected constant rounds. Thus, for inputs of size l = 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(nl + kappa n(2)) for inputs of size l bits. We also present a multi-valued validated Byzantine agreement protocol with asymptotically optimal communication complexity of O(nl + kappa n(2)) for inputs of size l bits in expectation and expected constant rounds. Both of these primitives are of independent interest.

Keywords:

Parallel broadcast

Graded parallel broadcast

Validated Byzantine agreement

Communication complexity

Round efficiency

Communication and Round Efficient Parallel Broadcast Protocols

Abstract

Journal

Organization