Abstract:

We address one of the classical open problems in the foundations of 
cryptography: the bias of coin-flipping protocols. Coin-flipping protocols 
allow mutually distrustful parties to generate a common unbiased random bit,
guaranteeing that even if one of the parties is malicious, it cannot 
significantly bias the output of the honest party.

A classical result by Cleve from STOC 1986 showed that for any two-party 
coin-flipping protocol with r rounds, there exists an efficient adversary
that can bias the output of the honest party by Omega(1/r). However, the best 
previously known protocol only guarantees O(1/sqrt(r)) bias, and the
question of whether Cleve's bound was tight has remained open ever since.

In this work we establish the optimal tradeoff between the round complexity
and the maximal bias of two-party coin-flipping protocols. Under standard 
assumptions, we show that Cleve's lower bound is tight: we construct an
r-round protocol with bias O(1/r). We make use of recent progress by Gordon, 
Hazay, Katz and Lindell regarding fair protocols (STOC 2008).

The talk will be self contained.

Joint work with Tal Moran and Gil Segev