The Taub Faculty of Computer Science Events and Talks

It is well known (c.f., Impagliazzo and Luby [FOCS '89]) that the existence of almost all ``interesting" cryptographic applications, i,e., ones that cannot hold information theoretically, implies one-way functions. An important exception where the above implication is not known, however, is the case of coin-flipping protocols. Such protocols allow honest parties to mutually flip an unbiased coin, while guaranteeing that even a cheating (efficient) party cannot bias the output of the protocol by much. While Impagliazzo and Luby proved that coin-flipping protocols that are safe against negligible bias do imply one-way functions, and, very recently, Maji, Prabhakaran, and Sahai [FOCS '10] proved the same for constant-round protocols (with any non-trivial bias). For the general case, however, no such implication was known.

We make progress towards answering the above fundamental question, showing that (strong) coin-flipping protocols safe against a constant bias (concretely, \frac{\sqrt2 -1}2 - o(1)) imply one-way functions. Joint work with Iftach Haitner.