Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)

An m output pseudorandom generator G: ({+/- 1}(b))(n) -> {+/- 1}(m) that takes input n blocks of b bits each is said to be l-block local if every output is a function of at most l blocks. We show that such l-block local pseudorandom generators can have output length at most (O) over tilde (2(lb)n(inverted right) (perpendicularl/2inverted left perpendicular)), by presenting a polynomial time algorithm that distinguishes inputs of the form G(x) from inputs where each coordinate is sampled from the uniform distribution on m bits. As a corollary, we refute some conjectures recently made in the context of constructing provably secure indistinguishability obfuscation (iO). This includes refuting the assumptions underlying Lin and Tessaro's [47] recently proposed candidate iO from bilinear maps. Specifically, they assumed the existence of a secure pseudorandom generator G : {+/- 1}(nb) -> {+/- 1}(2cbn) as above for large enough c > 3 and l = 2. (Following this work, and an independent work of Lombardi and Vaikuntanthan [49], Lin and Tessaro retracted the bilinear maps based candidate from their manuscript.) Our results actually hold for the much wider class of low-degree, nonbinary valued pseudorandom generators: if every output of G : {+/- 1}(n) -> R-m (R = reals) is a polynomial (over R) of degree at most d with at most s monomials and m >= (O) over tilde (sn(inverted right perpendiculard/2inverted left perpendicular)), then there is a polynomial time algorithm for distinguishing the output G(x) from z where each coordinate z(i) is sampled independently from the marginal distribution on G(i). Furthermore, our results continue to hold under arbitrary pre-processing of the seed. This implies that any such map G, with arbitrary seed pre-processing, cannot be a pseudorandom generator in the mild sense of fooling a product distribution on the output space. This allows us to rule out various natural modifications to the notion of generators suggested in other works that still allow obtaining indistinguishability obfuscation from bilinear maps. Our algorithms are based on the Sum of Squares (SoS) paradigm, and in most cases can even be defined more simply using a canonical semi-definite program. We complement our algorithm by presenting a class of candidate generators with block-wise locality 3 and constant block size, that resists both Gaussian elimination and sum of squares (SOS) algorithms whenever m = n(1.5-e). This class is extremely easy to describe: Let G be any simple non-abelian group with the group operation "*", and interpret the blocks of x as elements in G. The description of the pseudorandom generator is a sequence of m triples of indices (i, j, k) chosen at random and each output of the generator is of the form x(i) (*) x(j) (*) x(k).