Paper 2017/312
Limits on LowDegree Pseudorandom Generators (Or: SumofSquares Meets Program Obfuscation)
Boaz Barak, Zvika Brakerski, Ilan Komargodski, and Pravesh K. Kothari
Abstract
Consider a pseudorandom generator $G$ with $m$ outputs, whose seed contains $n$ blocks of $b$ bits each. Further, assume that this PRG has blocklocality $\ell$, i.e. each output bit depends on at most $\ell$ out of the $n$ blocks. The question of the maximum stretch $m$ that such PRGs can have, as a function of $n,b,\ell$ recently emerged in the context of constructing provably secure program obfuscation. It also relates to the question of refuting constraint satisfaction problems on predicates with large alphabets in complexity theory. We show that such $\ell$block local PRGs can have output length at most $\tilde{O}(2^{\ell b} n^{\lceil \ell/2 \rceil})$, by presenting a polynomial time algorithm that distinguishes inputs of the form $G(x)$ (for any $x$) from inputs where each coordinate is sampled independently according to the marginal distributions of the coordinates of $G$. 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 \cite{LinT17} recently proposed candidate iO from bilinear maps. Specifically, they assumed the existence of a secure pseudorandom generator $G\colon \{ \pm 1 \}^{nb} \rightarrow \{ \pm 1 \}^{2^{cb}n}$ as above for large enough $c>3$ with $\ell=2$. (Following this work, and an independent work of Lombardi and Vaikuntanthan \cite{LombardiV17a}, Lin and Tessaro retracted the bilinear maps based candidate from their manuscript.) Our results follow from a general framework that handles more general class of pseudorandom generators. Namely they work even if the outputs are not binary valued and are computed using lowdegree polynomial over $R$ (instead of the more restrictive local/blocklocal assumption). Specifically, we prove that for every function $G\colon\{\pm 1\}^n \rightarrow \mathbb R^m$ ($\mathbb R$ = reals), if every output of $G$ is a polynomial (over the real numbers $\mathbb{R}$) of degree at most $d$ of at most $s$ monomials and $m \ge \tilde{\Omega}(sn^{\lceil d/2 \rceil})$, then there is a polynomial time algorithm for the distinguishing task above. This implies that any such map $G$ cannot be a pseudorandom generator. Our results yield, in particular, that natural modifications to notion of generators that are still sufficient for obtaining indistinguishability obfuscation from bilinear maps run into similar barriers. Our algorithms follow the Sum of Squares (SoS) paradigm, and in most cases can even be defined more simply using a semidefinite program. We complement our algorithm by presenting a class of candidate generators with blockwise locality $3$ and constant block size, that resists both Gaussian elimination and sum of squares (SOS) algorithms whenever $m = n^{1.5\epsilon}$. This class is extremely easy to describe: Let $\mathbb G$ be any simple nonabelian group with the group operation ``$\ast$'', and interpret the blocks of $x$ as elements in $\mathbb 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 \ast x_j \ast x_k$.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 pseudorandom generatorslocal computationobfuscationrefutationSDPSOS
 Contact author(s)
 komargodski @ cornell edu
 History
 20190523: last of 2 revisions
 20170411: received
 See all versions
 Short URL
 https://ia.cr/2017/312
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/312, author = {Boaz Barak and Zvika Brakerski and Ilan Komargodski and Pravesh K. Kothari}, title = {Limits on LowDegree Pseudorandom Generators (Or: SumofSquares Meets Program Obfuscation)}, howpublished = {Cryptology ePrint Archive, Paper 2017/312}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/312}}, url = {https://eprint.iacr.org/2017/312} }