ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

{B}yzantine Agreement Given Partial Broadcast

Jeffrey Considine and Matthias Fitzi and Matthew Franklin and Leonid A. Levin and Ueli Maurer and David Metcalf

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.