IACR News item: 25 November 2013
Martin Hirt, Ueli Maurer, Pavel Raykov
ePrint Reportsender 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 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$.
Additional news items may be found on the IACR news page.