COIN FLIPPING WITH CONSTANT BIAS IMPLIES ONE-WAY FUNCTIONS.

It is well known (cf. Impagliazzo and Luby [in Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989, pp. 230-235]) 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. 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 [in Proceedings of the 2001 51st Annual IEEE Symposium on Foundations of Computer Science, 2010, pp. 613-622] proved the same for constant-round protocols (with any nontrivial 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, √2-1/2 - o(1)) imply one-way functions. [ABSTRACT FROM AUTHOR]