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.