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.

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.