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 ℓ -block local if every output is a function of at most ℓ blocks. We show that such ℓ -block local pseudorandom generators can have output length at most O~ (2^ℓbn^⌈ℓ/2⌉), 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 ℓ= 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, non-binary valued pseudorandom generators: if every output of G: {± 1}ⁿ→ R^m (R = reals) is a polynomial (over R) of degree at most d with at most s monomials and m≥ Ω~ (sn^⌈d/2⌉), 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 semidefinite 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-ε. 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.