Paper 2009/214

An Optimally Fair Coin Toss

Tal Moran, Moni Naor, and Gil Segev

Abstract

We address one of the foundational problems in cryptography: the bias of coin-flipping protocols. Coin-flipping protocols allow mutually distrustful parties to generate a common unbiased random bit, guaranteeing that even if one of the parties is malicious, it cannot significantly bias the output of the honest party. A classical result by Cleve [STOC '86] showed that for any two-party $r$-round coin-flipping protocol there exists an efficient adversary that can bias the output of the honest party by $\Omega(1/r)$. However, the best previously known protocol only guarantees $O(1/\sqrt{r})$ bias, and the question of whether Cleve's bound is tight has remained open for more than twenty years. In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: we construct an $r$-round protocol with bias $O(1/r)$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2009
Keywords
Fair computationcoin-flipping protocols
Contact author(s)
segev @ cs huji ac il
History
2015-01-04: last of 2 revisions
2009-05-26: received
See all versions
Short URL
https://ia.cr/2009/214
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/214,
      author = {Tal Moran and Moni Naor and Gil Segev},
      title = {An Optimally Fair Coin Toss},
      howpublished = {Cryptology ePrint Archive, Paper 2009/214},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/214}},
      url = {https://eprint.iacr.org/2009/214}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.