SPEAKER: Dana Dachman-Soled TITLE: On the Black-Box Complexity of Optimally-Fair coin tossing AUTHORS: D. Dachman-Soled, Y. Lindell, M. Mahmoody, T. 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 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. LINKS: To Appear at TCC 2011