Welcome to the resource topic for 2004/181
Title:
On the Composition of Authenticated Byzantine Agreement
Authors: Yehuda Lindell, Anna Lysyanskaya, 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.
ePrint: https://eprint.iacr.org/2004/181
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .