On the composition of authenticated Byzantine AgreementOn the composition of authenticated Byzantine Agreement

Access Restriction
Subscribed

 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

Source: ACM Digital Library