On the Composition of Authenticated Byzantine Agreement

Yehuda Lindell, Anna Lysyanskaya and Tal Rabin


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 secure protocols for any number of corrupted parties. This augmented problem 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:

In contrast, we present randomized protocols for authenticated Byzantine Agreement that remain secure under sequential composition, for 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/loglog 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.

Postscript, gzipped Postscript.

Back Home