## CryptoDB

### Paper: On the Complexity of Fair Coin Flipping

Authors: Iftach Haitner Nikolaos Makriyannis Eran Omri DOI: 10.1007/978-3-030-03807-6_20 Search ePrint Search Google TCC 2018 A two-party coin-flipping protocol is $\varepsilon$ε-fair if no efficient adversary can bias the output of the honest party (who always outputs a bit, even if the other party aborts) by more than $\varepsilon$ε. Cleve [STOC ’86] showed that r-round o(1 / r)-fair coin-flipping protocols do not exist. Awerbuch et al. [Manuscript ’85] constructed a $\varTheta (1/\sqrt{r})$Θ(1/r)-fair coin-flipping protocol, assuming the existence of one-way functions. Moran et al. [Journal of Cryptology ’16] constructed an r-round coin-flipping protocol that is $\varTheta (1/r)$Θ(1/r)-fair (thus matching the aforementioned lower bound of Cleve [STOC ’86]), assuming the existence of oblivious transfer.The above gives rise to the intriguing question of whether oblivious transfer, or more generally “public-key primitives”, is required for an $o(1/\sqrt{r})$o(1/r)-fair coin flipping. This question was partially answered by Dachman-Soled et al. [TCC ’11] and Dachman-Soled et al. [TCC ’14], who showed that restricted types of fully black-box reductions cannot establish $o(1/\sqrt{r})$o(1/r)-fair coin-flipping protocols from one-way functions. In particular, for constant-round coin-flipping protocols, [10] yields that black-box techniques from one-way functions can only guarantee fairness of order $1/\sqrt{r}$1/r.We make progress towards answering the above question by showing that, for any constant , the existence of an $1/(c\cdot \sqrt{r})$1/(c·r)-fair, r-round coin-flipping protocol implies the existence of an infinitely-often key-agreement protocol, where c denotes some universal constant (independent of r). Our reduction is non black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner et al. [FOCS ’18] to facilitate a two-party variant of the attack of Beimel et al. [FOCS ’18] on multi-party coin-flipping protocols.
##### BibTeX
@inproceedings{tcc-2018-28998,
title={On the Complexity of Fair Coin Flipping},
booktitle={Theory of Cryptography},
series={Theory of Cryptography},
publisher={Springer},
volume={11239},
pages={539-562},
doi={10.1007/978-3-030-03807-6_20},
author={Iftach Haitner and Nikolaos Makriyannis and Eran Omri},
year=2018
}