Algebraic Attacks against Random Local Functions and Their Countermeasures

Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate $m\gg n$ pseudorandom bits $y=(y_1,\ldots, 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$, $s>1$, the only known solution, originating from [Goldreich, Electronic Colloquium on Computational Complexity (ECCC), 2000], is based on random local functions: Compute $y_i$ by applying some fixed (public) $d$-ary predicate $P$ to a random (public) tuple of distinct input indices $(x_{i_1},\ldots,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 $\mathbb{F}_2$-linear adversaries (i.e., the distribution $y$ has small bias) is achieved if the predicate is (a) $k=\Omega(s)$-resilient, i.e., uncorrelated with any $k$-subset of its inputs, a...