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

Eran Omri (Bar-Ilan University)

Wednesday, 25.01.2012, 12:30

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.

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.