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 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:
- 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 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