Dana Dachman-Soled

On the Black-Box Complexity of Optimally-Fair coin tossing

D. Dachman-Soled, Y. Lindell, M. Mahmoody, T. Malkin

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 security
parameter (i.e. 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.  Thus we put forward another barrier (alternative
to that of Cleve's) for the number of rounds in an optimally-fair coin
tossing protocol, depending on the primitive used in the construction.
 Our result extends to any primitive (used to construct optimally-fair
coin tossing) which can be realized in a black-box manner from a
random oracle; examples of such primitives are exponentially hard
one-way functions and collision resistant hash functions.

To Appear at TCC 2011