Coin-tossing protocols are protocols that generate a random bit with
uniform distribution. These protocols are used as a building block 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) to the bit that the
honest parties output. However, for more than two decades the best known
protocols had bias \1/sqrt(r). 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).
Joint work with Eran Omri and Ilan Orlov
Copyright. All Rights Reserved.