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.