__
TR00-039 | 25th April 2000 00:00
__

#### Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping

**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

extensively studied for the case of {\em non-adaptive} adversaries who

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

against an {\em adaptive} adversary who can corrupt just a {\em

single} player in the course of the execution. In fact, Ben-Or and

Linial [BL90] conjectured that the adaptive adversary is much more

powerful than the non-adaptive adversary. More specifically, that the

optimal resilience threshold for adaptive adversaries is only O(sqrt(n))

(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.