# Theory Seminar: Coin Flipping with Constant Bias Implies One-Way Functions

- Speaker:
- Eran Omri (Bar-Ilan University)
- Date:
- Wednesday, 25.1.2012, 12:30
- Place:
- Taub 201

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.