Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Protocols for Multiparty Coin Toss With Dishonest Majority
event speaker icon
Ilan Orlov (Bar-Ilan University)
event date icon
Wednesday, 27.04.2011, 12:30
event location icon
Room 337-8 Taub Bld.
Generating random bits is a fundamental problem in cryptography. Coin-tossing protocols, which generate a random bit with uniform distribution, are used as a building box in many cryptographic protocols. Cleve [STOC 1986] has shown that if at least half of the parties can be malicious, then, in any $r$-round coin-tossing protocol, the malicious parties can cause a bias of $\Omega(1/r)$ in the bit that the honest parties output. However, for more than two decades the best known protocols had bias $t/\sqrt{r}$, where $t$ is the number of corrupted parties. Recently, in a surprising result, Moran, Naor, and Segev [TCC 2009] have shown that there is an $r$-round two-party coin-tossing protocol with the optimal bias of $O(1/r)$. We extend Moran et al.~results to the multiparty model when less than 2/3 of the parties are malicious. The bias of our protocol is proportional to $1/r$ and depends on the gap between the number of malicious parties and the number of honest parties in the protocol. Specifically, for a constant number of parties or when the number of malicious parties is somewhat larger than half, we present an $r$-round $m$-party coin-tossing protocol with optimal bias of $O(1/r)$.