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

by Boaz Barak, Zvika Brakerski, Ilan Komargodski, and Pravesh Kothari

Oded's comments

This work refutes a complexity conjecture that was recently proposed by Lin and Tessaro (in their work on Indistinguishability Obfuscation from Bilinear Maps and Block-Wise Local PRGs, which I should have recommended). The conjecture refers to the existence of pseudorandom generators (PRGs) in which each output bit depends on two blocks in the seed. Specifically, denoting the block-length by $b$, they required a stretch factor greater than $2^{3b}$.

The current paper shows that such PRGs do not exist. Specifically, the maximal possible stretch-factor of PRGs that are 2-local at the block level is $2^{2b}$, where $b$ is the block-length. This result is a special case of a more general statement that refers to constant locality at the block level; interestingly, the general result does not rule out 3-local (at the block level) PRGs with (small) polynomial stretch even for constant block-length.

Note: A closely related result by Alex Lombardi and Vinod Vaikuntanathan has appeared at about the same time as Report 2017/301 of the Crypto. ePrint Archive.

The original 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=3DG(x)$ from a vecto= r $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 =3D 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.

See ECCC TR17-060.

Back to list of Oded's choices.