Lower Bounds and Impossibility Results

We prove the first general and non-trivial lower bound for the number of times a 1-out-of-n Oblivious Transfer of strings of length l should be invoked so as to obtain, by an information-theoretically secure reduction, a 1-out-of-N Oblivious Transfer of strings of length L. The bound is tight in many significant cases and holds even in the honest-but-curious model. We also prove the first non-trivial lower bound for the number of random bits needed to implement such a reduction whenever the receiver sends no messages to the sender. This bound is also tight in many significant cases.

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, it has been onjectured 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.