Welcome to the resource topic for 2025/1012
Title:
Nearly Optimal Parallel Broadcast in the Plain Public Key Model
Authors: Ran Gelles, Christoph Lenzen, Julian Loss, Sravya Yandamuri
Abstract: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(n^2\ell\log(n)+n\kappa^2\log^4(n)) bits to succeed with probability 1-2^{-\kappa}, where \ell is the length of a message. All prior protocols either rely on a trusted setup or require at least O(n^3) communication complexity. As a stepping stone, we present a binary consensus protocol with the same resilience and success probability that sends O(n^2\kappa\log(n)+n\kappa^2\log^3(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.
ePrint: https://eprint.iacr.org/2025/1012
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .