Name
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 u002786] 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 *** (1/ r ). However, the best previously known protocol only guarantees $O(1/sqrt{r})$ bias, and the question of whether Cleveu0027s 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 Cleveu0027s lower bound is tight: we construct an r -round protocol with bias O (1/ r ). |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/s00145-015-9199-z | Journal of Cryptology |
Keywords | DocType | Volume |
Coin flipping,Round complexity,Optimal bias | Conference | 29 |
Issue | ISSN | Citations |
3 | 0933-2790 | 16 |
PageRank | References | Authors |
0.83 | 28 | 3 |