Gossiping for Communication-Efficient Broadcast

Byzantine Broadcast is crucial for many cryptographic protocols 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 message 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 warm-up result, we present 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 operates only against static adversaries.

Using ideas from our BC protocol, we move to our central contribution and present two protocols for PBC that are secure against adaptive adversaries. To the best of our knowledge we are the first to study PBC specifically: All previous approaches for Parallel Broadcast 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 Õ(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 Õ(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 Computing, 1983) and Chan et al. (Public Key Cryptography, 2020). Central to our PBC protocols is a new problem that we define and solve, which we name "Converge". In Converge, parties must run an adaptively-secure and efficient protocol such that by the end of the protocol, all honest parties that remain possess a superset of the union of the initial honest parties' inputs.