Paper 2012/643

Protocols for Multiparty Coin Toss With Dishonest Majority

Amos Beimel, 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).

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. The short version published in Crypto10, this full and updated version submited for publication to J. of Cryptology
Keywords
Fair Coin TossingMultiparty ComputationDishonest MajoritySecure with AbortCheat Detection.
Contact author(s)
ilanorlov @ gmail com
History
2012-11-20: received
Short URL
https://ia.cr/2012/643
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/643,
      author = {Amos Beimel and Eran Omri and Ilan Orlov},
      title = {Protocols for Multiparty Coin Toss With Dishonest Majority},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/643},
      year = {2012},
      url = {https://eprint.iacr.org/2012/643}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.