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 $$ 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 $$, where $$ denotes the total number of parties and $$ denotes the upper bound on the number of cheaters. This paper is concerned with broadcast protocols for any number of cheaters ($$), which can be possible only if, in addition to point-to-point channels, another primitive is available. Broadcast amplification is the problem of achieving $$-broadcast when $$-broadcast can be used once, for $$. Let $$ denote the minimal such $$ for domain size~$$. We show that for $$ parties, broadcast for any domain size is possible if only a single $$-broadcast is available, and broadcast of a single bit ($$) is not sufficient, i.e., $$ for any $$. In contrast, for $$ no broadcast amplification is possible, i.e., $$ for any $$. However, if other parties than the sender can also broadcast some short messages, then broadcast amplification is possible for \emph{any}~$$. Let $$ denote the minimal $$ such that $$-broadcast can be constructed from primitives $$-broadcast, \ldots, $$-broadcast, where $$ (i.e., $$). Note that $$. We show that broadcasting $$ bits in total suffices, independently of $$, and that at least $$ parties, including the sender, must broadcast at least one bit. Hence $$.