ECCC-Report TR21-092https://eccc.weizmann.ac.il/report/2021/092Comments and Revisions published for TR21-092en-usFri, 02 Jul 2021 04:24:40 +0300
Paper TR21-092
| A Note on One-way Functions and Sparse Languages |
Yanyi Liu,
Rafael Pass
https://eccc.weizmann.ac.il/report/2021/092We show equivalence between the existence of one-way
functions and the existence of a \emph{sparse} language that is
hard-on-average w.r.t. some efficiently samplable ``high-entropy''
distribution.
In more detail, the following are equivalent:
- The existentence of a $S(\cdot)$-sparse language $L$ that is
hard-on-average with respect to some samplable distribution with
Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq 4\log n$;
- The existentence of a $S(\cdot)$-sparse language $L \in
\NP$, that is
hard-on-average with respect to some samplable distribution with
Shannon entropy $h(\cdot)$ such that $h(n)-\log(S(n)) \geq n/3$;
- The existence of one-way functions.
Our results are insipired by, and generalize, the recent elegant paper by Ilango,
Ren and Santhanam (ECCC'21), which presents similar characterizations for
concrete sparse languages.Fri, 02 Jul 2021 04:24:40 +0300https://eccc.weizmann.ac.il/report/2021/092