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 pointtopoint 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 pointtopoint 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 $n2$ parties, including the sender, must broadcast at least one bit. Hence $\min(\log d,n2) \leq \log \phi^*_n(d) \leq 8n\log n$.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published by the IACR in TCC 2014
 Keywords
 Broadcast AmplificationPerfect SecurityFeasibilityImpossibility Proofs
 Contact author(s)
 raykov pavel @ gmail com
 History
 20131125: received
 Short URL
 https://ia.cr/2013/769
 License

CC BY
BibTeX
@misc{cryptoeprint:2013/769, author = {Martin Hirt and Ueli Maurer and Pavel Raykov}, title = {Broadcast Amplification}, howpublished = {Cryptology ePrint Archive, Paper 2013/769}, year = {2013}, note = {\url{https://eprint.iacr.org/2013/769}}, url = {https://eprint.iacr.org/2013/769} }