TITLE: On the Composition of Authenticated Byzantine Agreement

Speaker: Yehuda Lindell (Weizmann)


A fundamental problem of distributed computing is that of simulating a (secure) broadcast channel within the setting of a point-to-point network. Beyond being an important task within itself, secure broadcast is used at the core of many secure multiparty protocols. This problem is known as "Byzantine Agreement" and has been the focus of much research.

Lamport et al. showed that in order to obtain secure broadcast, more than 2/3 of the participating parties must by honest. They further show that if one augments the network with a public-key infrastructure (specifically, of digital signature keys), then it is possible to achieve secure broadcast when any number of the parties are dishonest. This augmented problem is called ``authenticated Byzantine Agreement.'' Previously, the security of authenticated Byzantine Agreement protocols was considered when the protocol was run once and in isolation. However, clearly it should be proven for multiple invocations, in order for it to be of real use.

We present surprising impossibility results showing that: 1. Authenticated Byzantine Agreement cannot be composed in parallel (and thus concurrently) if less than 2/3 of the parties are honest. 2. Deterministic authenticated Byzantine Agreement protocols can be composed sequentially for a fixed, limited number of times only.

In contrast, we present some positive results by giving randomized protocols that do compose sequentially.

This is joint work with and Anna Lysyanskaya and Tal Rabin.