Paper 2015/352

Broadcast from Minicast Secure Against General Adversaries

Pavel Raykov

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ICALP 2015 (Track C)
Keywords
Byzantine broadcast
Contact author(s)
pavelraykov @ post tau ac il
History
2015-04-23: received
Short URL
https://ia.cr/2015/352
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/352,
      author = {Pavel Raykov},
      title = {Broadcast from Minicast Secure Against General Adversaries},
      howpublished = {Cryptology ePrint Archive, Paper 2015/352},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/352}},
      url = {https://eprint.iacr.org/2015/352}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.