Paper 2024/974

Towards Optimal Parallel Broadcast under a Dishonest Majority

Abstract

The parallel broadcast (PBC) problem generalises the classic Byzantine broadcast problem to the setting where all $$ nodes broadcast a message and deliver $$ messages. PBC arises naturally in many settings including multi-party computation. Recently, Tsimos, Loss, and Papamanthou (CRYPTO 2022) showed PBC protocols with improved communication, against an adaptive adversary who can corrupt all but a constant fraction $$ of nodes (i.e., $$). However, their study is limited to single-bit messages, and their protocols have large polynomial overhead in the security parameter $$: their TrustedPBC protocol achieves $$ communication and $$ rounds. Since these factors of $$ are in practice often close (or at least polynomially related) to $$, they add a significant overhead. In this work, we propose three parallel broadcast protocols for $$-bit messages, for any size $$, that significantly improve the communication efficiency of the state-of-the-art. We first propose a new extension protocol that uses a $$-bit PBC as a black box and achieves i) communication complexity of $$, where $$ is the communication complexity of the $$-bit PBC, and ii) round complexity same as the $$-bit PBC. By comparison, the state-of-the-art extension protocol for regular broadcast (Nayak et al., DISC 2020) incurs $$ additional rounds of communication. Next, we propose a protocol that is secure against a static adversary, for $$-bit messages with $$ communication and $$ round complexity, where $$ is an arbitrarily small constant such that $$. Finally, we propose an adaptively-secure protocol for $$-bit messages with $$ communication overhead and $$ round complexity by modifying and improving the next-best protocol TrustedPBC in several key ways. Notably, our latter two protocols are $$ and $$ times more communication-efficient, respectively, than the state-of-the-art protocols while achieving the same round complexity.