**Protocols for Multiparty Coin Toss With Dishonest Majority**

*Amos Beimel and Eran Omri and Ilan Orlov*

**Abstract: **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 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).

**Category / Keywords: **Fair Coin Tossing, Multiparty Computation, Dishonest Majority, Secure with Abort; Cheat Detection.

**Publication Info: **The short version published in Crypto10, this full and updated version submited for publication to J. of Cryptology

**Date: **received 13 Nov 2012

**Contact author: **ilanorlov at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20121120:104721 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]