Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




Revision #1
Authors: Benny Applebaum, Yuval Ishai, Eyal Kushilevitz
Accepted on: 29th August 2016 17:24
Downloads: 162
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
Downloads: 670
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.



ISSN 1433-8092 | Imprint