Algebraic Attacks against Random Local Functions and Their Countermeasures

by Benny Applebaum and Shachar Lovett

Oded's comments

The result I find most interesting is a small-biased generator computable in NC0 that is not pseudorandom with respect to polynomial-time distinguishers. This refutes an appealing conjecture by Benny that asserted that NC0 constructs are "too weak to separate these two notions of pseudorandomness".

A second result of this paper is a characterization of the amount of stretch that small-biased generators consisting of a "local random functions" based on a fix predicate may have (*). Here the amount of stretch is the degree of the polynomial stretch function and this degree is related to a parameter of the predicate.

*) The term "local random function" is somewhat misleading. It refers to a local function (i.e., a function in NC0) that is selected by fixing a $d$-variate Boolean predicate $P$ and selecting a function from $n$ bits to $m=m(n)$ bits by applying $P$ to $m$ randomly selected $d$-long equences of elements in $[n]$.

Note (added Nov'16): I neglected to mention a nice attempt to model a type of algebraic attacks, which are commonly used in cryptoanalysis, and a characterization of stretch of generators that withstand such attacks in terms of another parameter of the predicate. I also neglected to mention that, in both cases, predicates yielding "maximal" stretch are presented; for example, in the case of small-bias generators, the exponent is improved from a square root of the locality parameter to linear in it (which is clearly maximal even wrt to an almost trivial test that just compares two bits in the sequence).

The original abstract

See the program webpage of STOC'16.

Back to list of Oded's choices.