Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-028 | 21st February 2006 00:00

On Expected Constant-Round Protocols for Byzantine Agreement


Authors: Jonathan Katz, Chiu-Yuen Koo
Publication: 4th March 2006 03:36
Downloads: 1251


In a seminal paper, Feldman and Micali (STOC '88) show an n-party Byzantine agreement protocol tolerating t < n/3 malicious parties that runs in expected constant rounds. Here, we show an expected constant-round protocol for authenticated Byzantine agreement assuming honest majority (i.e., $t < n/2$), and relying only on the existence of a secure signature scheme and a public-key infrastructure (PKI). Combined with existing results, this gives the first expected constant-round protocol for secure computation with honest majority in a point-to-point network assuming only one-way functions and a PKI. Our key technical tool --- a new primitive we introduce called moderated VSS --- also yields a simpler proof of the Feldman-Micali result.

We also improve the techniques of Lindell, et al. (PODC '02) for sequential composition of protocols without simultaneous termination (something that is inherent for Byzantine agreement protocols using o(n) rounds). Our approach is simpler and yields more round- and communication-efficient protocols.

ISSN 1433-8092 | Imprint