An Optimally Fair Coin Toss

by Tal Moran, Moni Naor, and Gil Segev.

Oded's comments

The great success of theoretical research in cryptography, in the 1980s, led to a feeling that everything is possible. This view has been changing during the 1990s when the emergence of various impossibility results got more attention. Most of these impossibility results are not absolute but rather refer to natural well-defined abstractions of the known (and even "perceivable") proof techniques.
For example, while 2-message zero-knowledge proofs were proven to exist only for BPP sets, restricting the simulation (which underlies the definition of ZK) to black-box use of the adversary rules out also 3-message protocols as well as any constant-round public-coin protocols. Indeed, Barak's ZK protocol (simulated via non-blackbox use of the adversary's program) is the most dramatic example of a construction that bypasses the known limitation of a natural and general formulation of the known (and "perceivable") proof techniques.
The current paper provides yet another striking example. It refers to the tradeoff between the round complexity of a coin tossing protocol and the influence an adversary may have on its outcome (in a model that mandates that the honest party outputs a coin value also in the case that the other party aborts the protocol).
Cleve showed in 1986 that in any $r$-round protocol one party can influence the outcome by at least $Omega(1/r)$, whereas a simple $r$-round protocol guarantees influence of at most $O(1/sqrt(r))$. Furthermore, Cleve and Impagliazzo (1993) proved that, within a natural well-defined construction paradigm, no protocol can outperform the aforementioned simple protocol. Yet, the current paper presents an $r$-round protocol (which deviates from the latter construction paradigm) that guarantees influence of at most $O(1/r)$.
For comments on seven other talks given at TCC'09, see my notes.

The original abstract

We address one of the foundational problems in 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 [STOC '86] showed that for any two-party $r$-round coin-flipping protocol 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 is tight has remained open for more than twenty years.
In this paper we establish the optimal trade-off between the round complexity and the bias of two-party coin-flipping protocols. Under standard assumptions (the existence of oblivious transfer), we show that Cleve's lower bound is tight: we construct an $r$-round protocol with bias $O(1/r)$.

Back to list of Oded's choices.