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

Yevgeniy Dodis.

In submission

### 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 *static 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 *adaptive adversary* who can corrupt just a
*single* player in the *middle* of the execution. In fact,
Ben-Or and Linial [BL90] conjectured that adaptive adversary is much
more powerful than non-adaptive adversary. In particular, 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
*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 *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 and the bit-fixing source of
Lichtenstein-Linial-Saks. While from each of these sources it is easy
to extract a "somewhat random" bit, we show this this is no longer
possible in the generalized source.

[ postscript ]
[ back to Yevgeniy Dodis' research interests
]