Abstract
This paper considers unconditionally secure protocols for reliable broadcast among a set of n players, where up to t of the players can be corrupted by a (Byzantine) adversary but the remaining h = n - t players remain honest. In the standard model with a complete, synchronous network of bilateral authenticated communication channels among the players, broadcast is achievable if and only if 2n/h < 3. We show that, by extending this model by the existence of partial broadcast channels among subsets of b players, global broadcast can be achieved if and only if the number h of honest players satisfies 2n/h < b + 1. Achievability is demonstrated by protocols with communication and computation complexities polynomial in the size of the network, i.e., in the number of partial broadcast channels. A respective characterization for the related consensus problem is also given.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Considine, J., Fitzi, M., Franklin, M. et al. Byzantine Agreement Given Partial Broadcast. J Cryptology 18, 191–217 (2005). https://doi.org/10.1007/s00145-005-0308-x
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00145-005-0308-x