Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR00-039 | 25th April 2000 00:00

TR00-039
Authors: Yevgeniy Dodis
Publication: 19th June 2000 15:25
Keywords:

Abstract:

Collective Coin-Flipping is a classical problem where n
computationally unbounded processors are trying to generate a random
bit in a setting where only a single broadcast channel is available
for communication. The protocol is said to be b(n)-resilient if any
adversary that can corrupt up to b(n) players, still cannot bias the
coin to some desired outcome almost certainly. The problem is
have to decide which players to corrupt before the protocol starts. In
particular, it is well-known that the optimum resilience threshold is
n/2 in this case. However, none of these protocols is resilient
single} player in the course of the execution. In fact, Ben-Or and
(which is achieved by a simple "majority" protocol).

We give strong evidence towards this conjecture by showing that no
{\em black-box} transformation from any statically secure
coin-flipping protocol can yield an adaptively secure protocol
tolerating \omega(sqrt(n)) players, so it is impossible to beat the
simple majority protocol in this way. The result is proven by reducing
the question in hand to the analysis of a novel {\em imperfect random
source} of independent interest. This imperfect random source
generalizes and unifies two well-known imperfect random sources: the
SV-source of Santha-Vazirani [SV86] and the bit-fixing source of
Lichtenstein-Linial-Saks [LLS89]. While from each of these sources
it is easy to extract a "somewhat random" bit, we show this this is no
longer possible for the generalized source.

ISSN 1433-8092 | Imprint