Communication and Round Efficient Parallel Broadcast Protocols

This work focuses on the parallel broadcast primitive, where each of the n parties wish to broadcast their ℓ-bit input in parallel. We consider the authenticated model with PKI and digital signatures that is secure against t2ℓ+κn³) communication (κ denotes a security parameter) and expected constant rounds. Thus, for inputs of size ℓ=Ω(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ℓ+κn²) for inputs of size ℓ bits. We also present a multi-valued validated Byzantine agreement protocol with asymptotically optimal communication complexity of O(nℓ+κn²) for inputs of size ℓ bits in expectation and expected constant rounds. Both of these primitives are of independent interest.

Duke Scholars

Author Kartik Nayak Computer Science