International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 25 November 2013

Martin Hirt, Ueli Maurer, Pavel Raykov
ePrint Report ePrint Report
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 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$.

Expand

Additional news items may be found on the IACR news page.