Impossibility of Black-Box Reduction from Non-Adaptively to Adaptively Secure Coin-Flipping
Yevgeniy Dodis · 2000
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 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 adaptive adversary who can corrupt just a 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 specically, that the optimal resilience threshold for adaptive adversaries is only O( p 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