Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR15-045 | 29th August 2016 17:24

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

Revision #1
Authors: Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
Accepted on: 29th August 2016 17:24
Keywords:

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 \emph{semi-private randomized encoding}. We believe that these results may be of independent interest.

### Paper:

TR15-045 | 1st April 2015 07:45

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

TR15-045
Authors: Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
Publication: 2nd April 2015 17:24
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 \emph{semi-private randomized encoding}. We believe that these results may be of independent interest.