CryptoDB
On Expected Constant-Round Protocols for Byzantine Agreement
| Authors: | |
|---|---|
| Download: | |
| 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 $o(n)$ rounds) for the case of $t |
BibTeX
@misc{eprint-2006-21558,
title={On Expected Constant-Round Protocols for Byzantine Agreement},
booktitle={IACR Eprint archive},
keywords={cryptographic protocols / distributed computing, multiparty computation},
url={http://eprint.iacr.org/2006/065},
note={An extended abstract will appear at Crypto 2006 jkatz@cs.umd.edu 13291 received 20 Feb 2006, last revised 23 May 2006},
author={Jonathan Katz and Chiu-Yuen Koo},
year=2006
}