Improved Search-to-Decision Reduction for Random Local Functions

A random local function defined by a d-ary predicate P is one where each output bit is computed by applying P to d randomly chosen bits of its input. These represent natural distributions of instances for constraint satisfaction problems. They were put forward by Goldreich [Gol11] as candidates for low-complexity one-way functions, and have subsequently been widely studied also as potential pseudo-random generators.

We present a new search-to-decision reduction for random local functions defined by any predicate of constant arity. Given any efficient algorithm that can distinguish, with advantage ε, the output of a random local function with m outputs and n inputs from random, our reduction produces an efficient algorithm that can invert such functions with Õ(m(n/ε) 2 ) outputs, succeeding with probability Ω(ε). This implies that if a family of local functions is one-way, then a related family with shorter output length is a family of pseudo-random generators.

Prior to our work, all such reductions that were known required the predicate to have additional sensitivity properties, whereas our reduction works for any predicate. Our results also generalise to some super-constant values of the arity d, and to noisy predicates.