Paper 2013/769

Broadcast Amplification

Martin Hirt, 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$.