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

摘要

PRG has block-locality , i.e. each output bit depends on at most out of the n blocks. The question of the maximum stretch m that such PRGs can have, as a function of n b 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 -block local PRGs can have output length at most O ( 2 b n 2 ) , 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 : 1 nb 1 2 cb n as above for large enough 3"> c 3 with = 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 low-degree polynomial over R (instead of the more restrictive local/block-local assumption). Specifically, we prove that for every function G : 1 n R m ( R = reals), if every output of G is a polynomial (over the real numbers R ) of degree at most d of at most s monomials and m ( s n d 2 ) , 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.