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 Discussion forum: Show discussion | Start new discussion