On Expected Constant-Round Protocols for Byzantine Agreement

Jonathan Katz; Chiu-Yuen Koo

Paper 2006/065

On Expected Constant-Round Protocols for Byzantine Agreement

Jonathan Katz and Chiu-Yuen Koo

Abstract

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 show a simple technique for sequential composition of protocols without simultaneous termination (something that is inherent for Byzantine agreement protocols using rounds) for the case of .

Metadata

Available format(s): PDF PS
Category: Cryptographic protocols
Publication info: Published elsewhere. An extended abstract will appear at Crypto 2006
Keywords: distributed computing multiparty computation
Contact author(s): jkatz @ cs umd edu
History: 2006-05-23: revised; 2006-02-23: received; See all versions
Short URL: https://ia.cr/2006/065
License: CC BY

BibTeX

@misc{cryptoeprint:2006/065,
      author = {Jonathan Katz and Chiu-Yuen Koo},
      title = {On Expected Constant-Round Protocols for Byzantine Agreement},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/065},
      year = {2006},
      url = {https://eprint.iacr.org/2006/065}
}