Broadcast Amplification

Martin Hirt, Ueli Maurer, and Pavel Raykov

Theory of Cryptography Conference — TCC 2014, Lecture Notes in Computer Science, Springer, vol. 8349, pp. 419–439, Feb 2014.

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 $ϕ_{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., $ϕ_{3} (d) = 3$ for any $d \geq 3$ . In contrast, for $n > 3$ no broadcast amplification is possible, i.e., $ϕ_{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 any $n$ . Let $ϕ_{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 $ϕ_{n}^{*} (d) \leq ϕ_{n} (d)$ . We show that broadcasting $8 n \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 ϕ_{n}^{*} (d) \leq 8 n \log n$ .

BibTeX Citation

@inproceedings{HiMaRa14,
    author       = {Martin Hirt and Ueli Maurer and Pavel Raykov},
    title        = {Broadcast Amplification},
    editor       = {Yehuda Lindell},
    booktitle    = {Theory of Cryptography Conference --- TCC 2014},
    pages        = {419--439},
    series       = {Lecture Notes in Computer Science},
    volume       = {8349},
    year         = {2014},
    month        = {2},
    publisher    = {Springer},
}