On the Complexity of Fair Coin Flipping
This work addresses a foundational question in cryptography about the requirements for secure two-party coin-flipping, with implications for protocol design and lower bounds.
The paper tackles the problem of constructing fair coin-flipping protocols by showing that for any constant number of rounds, a protocol with fairness better than 1/(c√r) implies the existence of key-agreement, linking fairness improvements to cryptographic primitives. This result makes progress on understanding whether public-key primitives are necessary for such protocols.
A two-party coin-flipping protocol is $ε$-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 $ε$. Cleve [STOC '86] showed that $r$-round $o(1/r)$-fair coin-flipping protocols do not exist. Awerbuch, Blum, Chor, Goldwasser, and Micali[Manuscript '85] constructed a $Θ(1/\sqrt{r})$-fair coin-flipping protocol, assuming the existence of one-way functions. Moran, Naor, and Segev [Journal of Cryptology '16] constructed an $r$-round coin-flipping protocol that is $Θ(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 protocol. We make a different progress towards answering the question by showing that, for any constant $r\in \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 \emph{non} black-box and makes a novel use of the recent dichotomy for two-party protocols of Haitner, Nissim, Omri, Shaltiel, and Silbak [FOCS '18] to facilitate a two-party variant of the recent attack of Beimel, Haitner, Makriyannis, and Omri [FOCS '18] on multi-party coin-flipping protocols.