Paper 2024/974

Towards Optimal Parallel Broadcast under a Dishonest Majority

Abstract

The parallel broadcast (PBC) problem generalizes 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. The state-of-the-art PBC protocol, TrustedPBC, is due to Tsimos, Loss, and Papamanthou (CRYPTO 2022), which is secure under an adaptive adversary assuming $$, where $$ is the number of Byzantine failures and $$. TrustedPBC focuses on single-bit inputs and achieves $$ communication and $$ rounds. In this work, we propose three PBC protocols for $$-bit messages, for any size $$, that significantly improve TrustedPBC. First, we 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. 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.