Limits on low-degree pseudorandom generators (Or: Sum-of-squares meets program obfuscation)

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations


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~ (2bn/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}n→ Rm (R = reals) is a polynomial (over R) of degree at most d with at most s monomials and m≥ Ω~ (snd/2), then there is a polynomial time algorithm for distinguishing the output G(x) from z where each coordinate zi is sampled independently from the marginal distribution on Gi. 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= n1.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 xi∗ xj∗ xk.

Original languageEnglish (US)
Title of host publicationAdvances in Cryptology - EUROCRYPT 2018 - 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018 Proceedings
EditorsJesper Buus Nielsen, Vincent Rijmen
PublisherSpringer Verlag
Number of pages31
ISBN (Print)9783319783741
StatePublished - 2018
Event37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018 - Tel Aviv, Israel
Duration: Apr 29 2018May 3 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10821 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2018
CityTel Aviv

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Limits on low-degree pseudorandom generators (Or: Sum-of-squares meets program obfuscation)'. Together they form a unique fingerprint.

Cite this