**Broadcast Amplification**

*Martin Hirt and Ueli Maurer and Pavel Raykov*

**Abstract: **A $d$-broadcast primitive is a communication primitive that allows a
sender to send a value from a domain of size $d$ to a set of parties.
A broadcast protocol emulates the $d$-broadcast primitive using only
point-to-point channels, even if some of the parties cheat, in
the sense that all correct recipients agree on the same value $v$
(consistency), and if the sender is correct, then $v$ is the value
sent by the sender (validity). A celebrated result by Pease, Shostak
and Lamport states that such a broadcast protocol exists if and only if $t <
n/3$, where $n$ denotes the total number of parties and $t$ denotes
the upper bound on the number of cheaters.

This paper is concerned with broadcast protocols for any number of cheaters ($t<n$), which can be possible only if, in addition to point-to-point channels, another primitive is available. Broadcast amplification is the problem of achieving $d$-broadcast when $d'$-broadcast can be used once, for $d'<d$. Let $\phi_n(d)$ denote the minimal such $d'$ for domain size~$d$.

We show that for $n=3$ parties, broadcast for any domain size is possible if only a single $3$-broadcast is available, and broadcast of a single bit ($d'=2$) is not sufficient, i.e., $\phi_3(d)=3$ for any $d\geq 3$. In contrast, for $n > 3$ no broadcast amplification is possible, i.e., $\phi_n(d)=d$ for any $d$.

However, if other parties than the sender can also broadcast some short messages, then broadcast amplification is possible for \emph{any}~$n$. Let $\phi^*_n(d)$ denote the minimal $d'$ such that $d$-broadcast can be constructed from primitives $d'_1$-broadcast, \ldots, $d'_k$-broadcast, where $d'=\prod_i d'_i$ (i.e., $\log d'=\sum_i \log d'_i$). Note that $\phi^*_n(d)\leq\phi_n(d)$. We show that broadcasting $8n\log n$ bits in total suffices, independently of $d$, and that at least $n-2$ parties, including the sender, must broadcast at least one bit. Hence $\min(\log d,n-2) \leq \log \phi^*_n(d) \leq 8n\log n$.

**Category / Keywords: **cryptographic protocols / Broadcast Amplification, Perfect Security, Feasibility, Impossibility Proofs

**Original Publication**** (in the same form): **IACR-TCC-2014

**Date: **received 20 Nov 2013

**Contact author: **raykov pavel at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20131125:191332 (All versions of this report)

**Short URL: **ia.cr/2013/769

[ Cryptology ePrint archive ]