Paper 2017/312

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

Boaz Barak and Zvika Brakerski and Ilan Komargodski and Pravesh K. Kothari

Abstract

We prove that for every function $G\colon\{0,1\}^n \rightarrow \mathbb{R}^m$, if every output of $G$ is a polynomial (over $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m > \widetilde{O}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm that can distinguish a vector of the form $z=G(x)$ from a vector $z$ where each coordinate is sampled independently according to the marginal distributions of the coordinates of $G$ (assuming the latter satisfy some non-degeneracy condition). In particular, if $G\colon\{0,1\}^n \rightarrow \{0,1\}^m$ and $m$ is as above, then $G$ cannot be a pseudorandom generator. Our algorithm is based on semidefinite programming and in particular the sum of squares (SOS) hierarchy. As a corollary, we refute some conjectures recently made in the cryptographic literature. This includes refuting the assumptions underlying Lin and Tessaro's recently proposed candidate construction for indistinguishability obfuscation from bilinear maps, by showing that any block-wise 2-local PRG with block size $b$ cannot go beyond $m \approx 2^{2b}\cdot n$. We give an even stronger bound of $m \approx 2^b n$ on the output length of random block-wise 2-local PRGs. We also show that a generalized notion of generators runs into similar barriers. 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 SOS algorithms whenever $m = n^{1.5-\varepsilon}$. This class is extremely easy to describe: Let $\mathbb{G}$ be any simple non-abelian group, and interpret the blocks of $x$ as elements in $\mathbb{G}$, then each output of the generator is of the form $x_i \ast x_j \ast x_k$, where $i,j,k$ are random and "$\ast$" is the group operation.