-
Upload Video
videos in mp4/mov/flv
close
Upload video
Note: publisher must agree to add uploaded document -
Upload Slides
slides or other attachment
close
Upload Slides
Note: publisher must agree to add uploaded document -
Feedback
help us improve
close
Feedback
Please help us improve your experience by sending us a comment, question or concern
Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.
Description
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.