## 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.