Access Restriction

Author Lindell, Yehuda ♦ Lysyanskaya, Anna ♦ Rabin, Tal
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2006
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Authenticated Byzantine Agreement ♦ Lower bounds ♦ Protocol composition ♦ Randomized protocols
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. [1982] showed that in order to achieve Byzantine Agreement in the plain model, more than two thirds 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 article, we consider the question of concurrent, parallel and sequential composition of authenticated Byzantine Agreement protocols with a single common setup. We present surprising impossibility results showing that:(1) Authenticated Byzantine Agreement protocols that remain secure under parallel or concurrent composition (even for just two executions) and tolerate a third or more corrupted parties, do $\textit{not}$ exist.(2) Deterministic authenticated Byzantine Agreement protocols that run for $\textit{r}$ rounds and tolerate a third or more corrupted parties, can remain secure for at most $2\textit{r}$ ™ 1 sequential executions.In contrast, we present randomized protocols for authenticated Byzantine Agreement that remain secure under sequential composition, for $\textit{any}$ polynomial number of executions. We exhibit two such protocols. In the first protocol, an honest majority is required. In the second protocol, any number of parties may be corrupted; however, the complexity of the protocol is in the order of $2^{n}$ · $\textit{n}!$ for $\textit{n}$ parties. In order to have this polynomial in the security parameter $\textit{k}$ (used for the signature scheme in the protocol), this requires the overall number of parties to be limited to $\textit{O}(log$ $\textit{k}/log$ log $\textit{k}).$ The above results are achieved due to a new protocol for authenticated Byzantine Generals for three parties that can tolerate any number of faulty parties and composes sequentially.Finally, we show that when the model is further augmented so that in each session, all the participating parties receive a common session identifier that is unique to that session, then any polynomial number of authenticated Byzantine agreement protocols can be concurrently executed, while tolerating any number of corrupted parties.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2006-11-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 53
Issue Number 6
Page Count 37
Starting Page 881
Ending Page 917

Open content in new tab

   Open content in new tab
Source: ACM Digital Library