Byzantine Broadcast is crucial for many cryptographic pro- tocols such as secret sharing, multiparty computation and blockchain consensus. In this paper we apply gossiping (propagating a message by sending to a few random parties who in turn do the same, until the mes- sage is delivered) and propose new communication-efficient protocols, under dishonest majority, for Single-Sender Broadcast (BC) and Parallel Broadcast (PBC), improving the state-of-the-art in several ways. As our first warm-up result, we give a randomized protocol for BC which achieves O(n^2κ^2) communication complexity from plain public key setup assumptions. This is the first protocol with subcubic communication in this setting, but does so only against static adversaries. Using some ideas from our BC protocol, we then move to our central con- tribution and present two protocols for PBC that are secure against adap- tive adversaries. To the best of our knowledge we are the first to study PBC specifically: All previous approaches for parallel BC (PBC) naively run n instances of single-sender Broadcast, increasing the communication complexity by an undesirable factor of n. Our insight of avoiding black- box invocations of BC is particularly crucial for achieving our asymptotic improvements. In particular: 1. Our first PBC protocol achieves O(n^3κ^2) communication complexity and relies only on plain public key setup assumptions. 2. Our second PBC protocol uses trusted setup and achieves nearly optimal communication complexity O(n^2κ^4). Both PBC protocols yield an almost linear improvement over the best known solutions involving n parallel invocations of the respective BC protocols such as those of Dolev and Strong (SIAM Journal on Comput- ing, 1983) and Chan et al. (Public Key Cryptography, 2020). Central to our PBC protocols is a new problem that we define and solve, that we call “Converge”. In Converge, parties must run an adaptively-secure and efficient protocol such that by the end of the protocol, the honest parties that remain possess a superset of the union of the inputs of the initial honest parties.
2022-08
2024-11-15