Theory Seminar
"Algebraic Attacks against Random Local Functions and Their Countermeasures"
Shachar Lovett
(UCSD)
Tuesday, November 10th, 2015, 1:00 pm
EBU3B, Room 4258
Abstract:
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, 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},\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 $\F_2$-linear adversaries (i.e., the distribution $y$ has low-bias) is achieved if the predicate is (a) $k=\Omega(s)$-resilience, i.e., uncorrelated with any $k$-subset of its inputs, and (b) has algebraic degree of $\Omega(s)$ even after fixing $\Omega(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^{\Omega(d)}$, answering an open question of Mossel, Shpilka and Trevisan (FOCS, 2003). Our negative result shows that a candidate for pseudorandom generator proposed by Applebaum (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=\Theta(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 Applebaum (Question 4.9, ECCC 2015).
Joint work with Benny Applebaum.
The paper is at http://eccc.hpi-web.de/report/2015/172/