## On the Black-Box Complexity of Optimally-Fair Coin Tossing

### Dana Dachman-Soled, Yehuda Lindell, Mohammad Mahmoody and Tal Malkin

### Abstract:

A fair two-party coin tossing protocol is one in which both parties output the same bit that is almost uniformly distributed (i.e., it equals 0 and 1 with probability that is at most negligibly far from one half). It is well known that it is *impossible* to achieve fair coin tossing even in the presence of fail-stop adversaries (Cleve, FOCS 1986). In fact, Cleve showed that for every coin tossing protocol running for *r* rounds, an efficient fail-stop adversary can bias the output by \Omega(1/*r*). Since this
is the best possible, a protocol that limits the bias of any adversary to
O(1/*r*) is called *optimally-fair*. The only optimally-fair protocol that is known to exist relies on the existence of oblivious transfer, because it
uses general secure computation (Moran, Naor and Segev, TCC 2009). However, it is possible to achieve a bias of O(1/sqrt(*r*)) in *r* rounds relying
only on the assumption that there exist one-way functions. In this paper
we show that it is impossible to achieve optimally-fair coin tossing via
a black-box construction from one-way functions for *r* that is less than
O(*n*/log *n*), where *n* is the input/output length of the one-way function used. An important corollary of this is that it is impossible to construct an optimally-fair coin tossing protocol via a black-box construction from one-way functions whose round complexity is independent of the security
parameter *n* determining the security of the one-way function being used.
Informally speaking, the main ingredient of our proof is to eliminate
the random-oracle from "secure" protocols with "low round-complexity"
and simulate the protocol securely against semi-honest adversaries in the
plain model. We believe our simulation lemma to be of broader interest.

PDF.

Back Home