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.