ECCC-Report TR18-084https://eccc.weizmann.ac.il/report/2018/084Comments and Revisions published for TR18-084en-usWed, 25 Apr 2018 21:25:09 +0300
Paper TR18-084
| On the Complexity of Fair Coin Flipping |
Iftach Haitner,
Nikolaos Makriyannis,
Eran Omri
https://eccc.weizmann.ac.il/report/2018/084A 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 $\Theta(1/\sqrt{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 $\Theta(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)$-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 \emph{restricted} types of fully black-box reductions cannot establish $o(1/\sqrt r)$-fair coin-flipping protocols from one-way functions.
We make progress towards answering the above question, by showing that, for any (constant) $r\in \mathbb{N}$, the existence of an $1/(c\cdot \sqrt{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. to facilitate a two-party variant of the recent attack of Beimel et al. on multi-party coin-flipping protocols.
Wed, 25 Apr 2018 21:25:09 +0300https://eccc.weizmann.ac.il/report/2018/084