##
Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings

by Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz

#### Oded's comments

This choice is more of a gamble;
a gamble that the notion of semi-private randomized encoding
may find useful applications.

#### The original abstract

A one-way function is $d$-local if each of its outputs depends on at most
$d$ input bits. In (Applebaum, Ishai, and Kushilevitz, FOCS 2004) it was
shown that, under relatively mild assumptions, there exist $4$-local
one-way functions (OWFs). This result is not far from optimal as it is not
hard to show that there are no $2$-local OWFs. The gap was partially closed
in (Applebaum, Ishai, and Kushilevitz, FOCS 2004) by showing that the
existence of a $3$-local OWF is implied by the intractability of decoding a
random linear code (or equivalently the hardness of learning parity with
noise).

In this note we provide further evidence for the existence of $3$-local
OWFs. We construct a $3$ local OWF based on the assumption that a random
function of (arbitrarily large) constant locality is one-way. (A similar
assumption was previously made by Goldreich, ECCC 2000.) Our proof consists
of two steps: (1) We show that, under the above assumption, random local
functions remain hard to invert even when some information on the preimage
$x$ is leaked; and (2) Such ``robust'' local one-way functions can
be converted to $3$-local one-way functions via a new construction of
semi-private randomized encoding. We believe that these results may
be of independent interest.

See ECCC TR15-045 .

Back to
list of Oded's choices.