Algebraic Attacks against Random Local Functions and Their Countermeasures

摘要

Suppose that you have n truly random bits x = ( x 1 x n ) and you wish to use them to generate m n pseudorandom bits y = ( y 1 y m ) using a local mapping, i.e., each y i should depend on at most d = O (1) bits of x . In the polynomial regime of m = n s , 1"> s 1 , the only known solution, originates from (Goldreich, ECCC 2000), is based on emph{Random Local Functions}: Compute y i by applying some fixed (public) d -ary predicate P to a random (public) tuple of distinct inputs ( x i 1 x i d ) . 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 F 2 -linear adversaries (i.e., the distribution y has low-bias) is achieved if the predicate is (a) k = ( s ) -resilience, 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 low-bias generator can have output length of n ( d ) , answering an open question of Mossel, Shpilka and Trevisan (FOCS, 2003). Our negative result shows that a candidate for pseudorandom generator proposed by the first author (ECCC 2015) and by O'Donnell and Witmer (CCC 2014) is insecure. We use similar techniques to refute a conjecture of Feldman, Perkins and Vempala (STOC 2015) regarding the hardness of planted constraint satisfaction problems.(2) Motivated by the cryptanalysis literature, we consider security against emph{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 there exist a degree e = ( s ) non-zero polynomial Q whose roots cover the roots of P or cover the roots of P 's complement. 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 the first author (Question~4.9, ECCC 2015).