Welcome to the resource topic for 2013/769
Title:
Broadcast Amplification
Authors: Martin Hirt, Ueli Maurer, 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.
ePrint: https://eprint.iacr.org/2013/769
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 .