ECCC-Report TR06-028https://eccc.weizmann.ac.il/report/2006/028Comments and Revisions published for TR06-028en-usSat, 04 Mar 2006 03:36:25 +0200
Paper TR06-028
| On Expected Constant-Round Protocols for Byzantine Agreement |
Jonathan Katz,
Chiu-Yuen Koo
https://eccc.weizmann.ac.il/report/2006/028In 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.
Sat, 04 Mar 2006 03:36:25 +0200https://eccc.weizmann.ac.il/report/2006/028