Welcome to the resource topic for 2018/901
Title:
On the Complexity of Fair Coin Flipping
Authors: Iftach Haitner, Nikolaos Makriyannis, Eran Omri
Abstract:A two-party coin-flipping protocol is \epsilon-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 \epsilon. 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 restricted types of fully black-box reductions cannot establish o(1/\sqrt r)-fair coin-flipping protocols from one-way functions. In particular, for constant-round coin-flipping protocols, Dachman-Soled et al. showed that black-box techniques from one-way functions can only guarantee fairness of order 1/\sqrt{r}. 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. [FOCS '18] to facilitate a two-party variant of the recent attack of Beimel et al. [FOCS '18] on multi-party coin-flipping protocols.
ePrint: https://eprint.iacr.org/2018/901
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .