Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


It is well known (\cf Impagliazzo and Luby [FOCS '89]) that the existence of almost all ``interesting" cryptographic applications, \ie 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, Sahai and Schreiber [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 a significant step towards answering the above fundamental question, showing that coin-flipping protocols safe against a constant bias (concretely, $\frac{\sqrt{2} -1}{2}$) imply one-way functions.

Questions and Answers

You need to be logged in to be able to post here.