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.