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.
Category / Keywords: cryptographic protocols / Byzantine broadcast Original Publication (with major differences): ICALP 2015 (Track C) Date: received 20 Apr 2015, last revised 20 Apr 2015 Contact author: pavelraykov at post tau ac il Available format(s): PDF | BibTeX Citation Version: 20150423:024822 (All versions of this report) Short URL: ia.cr/2015/352 Discussion forum: Show discussion | Start new discussion