On beating the hybrid argument

Abstract

The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor k equal to the bit-length of the distributions: ε-distinguishability implies ε/k-predictability. This paper studies the consequences of avoiding this loss - what we call "beating the hybrid argument" -- and develops new proof techniques that circumvent the loss in certain natural settings. Specifically, we obtain the following results: 1. We give an instantiation of the Nisan-Wigderson generator (JCSS '94) that can be broken by quantum computers, and that is o(1)-unpredictable against AC^0. We conjecture that this generator indeed fools AC^0. Our conjecture implies the existence of an oracle relative to which BQP is not in the PH, a longstanding open problem. 2. We show that the "INW" generator by Impagliazzo, Nisan, and Wigderson (STOC '94) with seed length O(log n log log n) produces a distribution that is 1/log n-unpredictable against poly-logarithmic width (general) read-once oblivious branching programs. Obtaining such generators where the output is indistinguishable from uniform is a longstanding open problem. 3. We identify a property of functions f, "resamplability," that allows us to beat the hybrid argument when arguing indistinguishability of [EQUATION] from uniform. This gives new pseudorandom generators for classes such as AC^0[p] with a stretch that, despite being sub-linear, is the largest known. We view this as a first step towards beating the hybrid argument in the analysis of the Nisan-Wigderson generator (which applies G_f^⊗k on correlated x_1,...,x_k) and proving the conjecture in the first item.

Additional details