Cryptology ePrint Archive: Report 2009/214

An Optimally Fair Coin Toss

Tal Moran and 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)$.

Category / Keywords: foundations / Fair computation, coin-flipping protocols

Original Publication (with major differences): IACR-TCC-2009

Date: received 17 May 2009, last revised 4 Jan 2015

Contact author: segev at cs huji ac il

Available format(s): PDF | BibTeX Citation

Version: 20150104:080819 (All versions of this report)

Short URL: ia.cr/2009/214

Discussion forum: Show discussion | Start new discussion