%0 Journal Article %J Journal of Computer and System Sciences %D 2009 %T On expected constant-round protocols for Byzantine agreement %A Katz, Jonathan %A Koo,Chiu-Yuen %K broadcast %K cryptography %K Distributed computing %K secure computation %X In a seminal paper, Feldman and Micali show an n-party Byzantine agreement protocol in the plain model that tolerates t < n / 3 malicious parties and runs in expected constant rounds. Here, resolving a question that had been open since their work, 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 signature schemes and a public-key infrastructure. Combined with existing results, this gives the first expected constant-round protocol for secure computation with honest majority in a point-to-point network under the same assumptions. Our key technical tool — a new primitive we introduce called moderated VSS — also yields a simpler proof of the Feldman–Micali result.In addition, we show a simple technique for sequential composition of Byzantine agreement protocols that do not achieve simultaneous termination, something that is inherent for protocols using o ( t ) rounds. %B Journal of Computer and System Sciences %V 75 %P 91 - 112 %8 2009/02// %@ 0022-0000 %G eng %U http://www.sciencedirect.com/science/article/pii/S0022000008000718 %N 2 %R 10.1016/j.jcss.2008.08.001