Paper 2020/253

Black-box use of One-way Functions is Useless for Optimal Fair Coin-Tossing

Hemanta K. Maji and Mingyuan Wang

Abstract

A two-party fair coin-tossing protocol is a coin-tossing protocol that guarantees output to the honest party even when the other party aborts during the protocol execution. Cleve (STOC--1986) demonstrated that, even when the parties are computationally bounded, a fail-stop adversary can alter the output distribution of the honest party by (roughly) $1/r$ (in the statistical distance) in an $r$-message coin-tossing protocol. An optimal fair coin-tossing protocol ensures that no adversary can alter the output distribution beyond $1/r$. In a seminal result, Moran, Naor, and Segev (TCC--2009) constructed the first optimal fair coin-tossing protocol using oblivious transfer protocols. Whether the existence of oblivious transfer protocols is a necessary computational hardness assumption for optimal fair coin-tossing remains one of the most fundamental open problems in theoretical cryptography. Results of Impagliazzo and Luby (FOCS--1989) and Cleve and Impagliazzo (1993) together imply that the existence of one-way functions is necessary for optimal fair coin-tossing. However, the sufficiency of the existence of one-way functions is not known. Towards this research endeavor, our work proves a black-box separation of optimal fair coin-tossing from the existence of one-way functions. That is, the black-box use of one-way functions is unlikely to enable optimal fair coin-tossing. Following the standard Impagliazzo and Rudich (STOC--1989) approach, our work considers any $r$-message fair coin-tossing protocol in the random oracle model where the parties have unbounded computational power. We demonstrate a fail-stop attack strategy for one of the parties to alter the output distribution of the honest party by $1/\sqrt{r}$. Our result, therefore, proves that the $r$-message coin-tossing protocol of Blum (COMPCON--1982) and Cleve (STOC--1986), which uses one-way functions in a black-box manner, is qualitatively the best possible protocol. Several previous works, for example, Dachman--Soled, Lindell, Mahmoody, and Malkin (TCC--2011), Haitner, Omri, and Zarosim (TCC--2013), and Dachman--Soled, Mahmoody, and Malkin (TCC--2014), made partial progress on this research problem by proving this black-box separation assuming some restrictions on the coin-tossing protocol. Our work diverges significantly from these previous approaches to prove this black-box separation in its full generality. The starting point is the recently introduced potential-based inductive proof techniques for demonstrating large gaps in martingales in the information-theoretic plain model. Our technical contribution lies in identifying a global invariant that enables the extension of this technique to the random oracle model.