On the Complexity of Fair Coin Flipping
share
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/√(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/√(r))-fair coin flipping protocol. We make a different progress towards answering the question by showing that, for any constant r∈, the existence of an 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, 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.
READ FULL TEXT