Nearly Optimal Parallel Broadcast in the Plain Public Key Model.

Summary

Parallel Byzantine broadcast (PBC) (also known as Interactive Consistency), is a fundamental problem in distributed computing and cryptography which asks that all parties reliably distribute a message to all other parties. We give the first communication-efficient protocol for PBC in the model with plain public keys (i.e., no trusted dealer) which achieves security against an adaptive adversary that can corrupt up to t < n/2 parties. Our protocol runs in total communication complexity O(n2ℓlog(n) +nκ2 log4 (n)) bits to succeed with probability 1 − 2−κ, where ℓ is the length of a message. All prior protocols either rely on a trusted setup or require at least O(n3) communication complexity. As a stepping stone, we present a binary consensus protocol with the same resilience and success probability that sends O(n2κ log(n) + nκ2log3(n)) bits. We achieve these results based on a highly efficient gossip procedure that implements echo operations at low cost, and might prove useful in deriving further efficient protocols relying on simple cryptographic tools.