UC San Diego

Suppose that you have n truly random bits x = (x1, . . ., xn) and you wish to use them to generate m n pseudorandom bits y = (y1, . . ., ym) using a local mapping, i.e., each yi should depend on at most d = O(1) bits of x. In the polynomial regime of m = ns, s > 1, the only known solution, originating from [Goldreich, Electronic Colloquium on Computational Complexity (ECCC), 2000], is based on random local functions: Compute yi by applying some fixed (public) d-ary predicate P to a random (public) tuple of distinct input indices (xi1 , . . ., xid). Our goal in this paper is to understand, for any value of s, how the pseudorandomness of the resulting sequence depends on the choice of the underlying predicate. We derive the following results: (1) We show that pseudorandomness against F2-linear adversaries (i.e., the distribution y has small bias) is achieved if the predicate is (a) k = Ω(s)-resilient, i.e., uncorrelated with any k-subset of its inputs, and (b) has algebraic degree of Ω(s) even after fixing Ω(s) of its inputs. We also show that these requirements are necessary, and so they form a tight characterization (up to constants) of security against linear attacks. Our positive result shows that a d-local small-biased generator can have output length of nΩ(d), answering an open question of Mossel, Shpilka, and Trevisan [Proceedings of FOCS, 2003]. Our negative result shows that a candidate for a pseudorandom generator proposed by Applebaum [Comput. Complexity, 25 (2016), pp. 667–722] and by O’Donnell and Witmer [Proceedings of CCC 2014] is insecure. We use similar techniques to refute a conjecture of Feldman, Perkins, and Vempala [Proceedings of STOC 2015] regarding the hardness of planted constraint satisfaction problems. (2) Motivated by the cryptanalysis literature, we consider security against algebraic attacks. We provide the first theoretical treatment of such attacks by formalizing a general notion of algebraic inversion and distinguishing attacks based on the polynomial calculus proof system. We show that algebraic attacks succeed if and only if the predicate P has rational degree e = Θ(s), where the rational degree of a predicate P is the smallest integer e for which there exist degree e polynomials Q, R, not both zero, such that PQ = R. As a corollary, we obtain the first example of a predicate P for which the generated sequence y passes all linear tests but fails to pass some polynomial-time computable test, answering an open question posed by Applebaum [Comput. Complexity, 25 (2016), pp. 667–722].