Paper 2004/181

On the Composition of Authenticated Byzantine Agreement

Yehuda Lindell, Anna Lysyanskaya, and Tal Rabin

Abstract

A fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement (or Generals) and has been the focus of much research. Lamport et al. showed that in order to achieve Byzantine Agreement in the standard model, more than 2/3 of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure for digital signatures, it is possible to obtain protocols that are secure for any number of corrupted parties. The problem in this augmented model is called "authenticated Byzantine Agreement". In this paper we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols. We present surprising impossibility results showing that: * If an authenticated Byzantine Agreement protocol remains secure under parallel or concurrent composition (even for just two executions), then more than 2/3 of the participating parties must be honest. * Deterministic authenticated Byzantine Agreement protocols that run for $r$ rounds and tolerate 1/3 or more corrupted parties, can remain secure for at most $2r-1$ sequential executions. In contrast, we present randomized protocols for authenticated Byzantine Agreement that remain secure under sequential composition, for {\em any}\/ polynomial number of executions. We exhibit two such protocols. In the first protocol, the number of corrupted parties may be any number less than 1/2 (i.e., an honest majority is required). In the second protocol, any number of parties may be corrupted; however, the overall number of parties must be limited to $O(\log k/\log\log k)$, where $k$ is the security parameter (and so all parties run in time that is polynomial in $k$). Finally, we show that when the model is further augmented so that unique and common session identifiers are assigned to each concurrent session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of corrupted parties.