ECCC-Report TR15-045https://eccc.weizmann.ac.il/report/2015/045Comments and Revisions published for TR15-045en-usMon, 29 Aug 2016 17:24:17 +0300
Revision 1
| Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings |
Benny Applebaum,
Yuval Ishai,
Eyal Kushilevitz
https://eccc.weizmann.ac.il/report/2015/045#revision1A 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. Mon, 29 Aug 2016 17:24:17 +0300https://eccc.weizmann.ac.il/report/2015/045#revision1
Paper TR15-045
| Minimizing Locality of One-Way Functions via Semi-Private Randomized Encodings |
Benny Applebaum,
Yuval Ishai,
Eyal Kushilevitz
https://eccc.weizmann.ac.il/report/2015/045A 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. Thu, 02 Apr 2015 17:24:47 +0300https://eccc.weizmann.ac.il/report/2015/045