International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 22 April 2015

Pavel Raykov
ePrint Report ePrint Report
Byzantine broadcast is a distributed primitive that allows a specific party to consistently distribute a message among $n$ parties in the presence of potential misbehavior of up to $t$ of the parties. The celebrated result of \\cite{PSL80} shows that broadcast is achievable from point-to-point channels if and only if $t < n/3$.

The following two generalizations have been proposed to the original broadcast problem. In~\\cite{FM98} the authors considered a \\emph{general adversary} characterized by the sets of parties that can be corrupted. It was shown that broadcast is achievable from point-to-point channels if and only if no three possible corrupted sets can cover the whole party set. In~\\cite{CFFLMM05} the notion of point-to-point channels has been extended to the $b$-minicast channels allowing to locally broadcast among any subset of $b$ parties. It has been shown that broadcast secure against adversaries corrupting up to $t$ parties is achievable from $b$-minicast if and only if $t < \\frac{b-1}{b+1}n$.

In this paper we combine both generalizations by considering the problem of achieving broadcast from $b$-minicast channels secure against general adversaries. Our main result is a condition on the possible corrupted sets such that broadcast is achievable from $b$-minicast if and only if this condition holds.

Expand

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