**A Note on One-way Functions and Sparse Languages**

*Yanyi Liu and Rafael Pass*

**Abstract: **We show equivalence between the existence of one-way
functions and the existence of a 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.

**Category / Keywords: **foundations / one-way functions, average-case complexity

**Date: **received 28 Jun 2021

**Contact author: **yl2866 at cornell edu, rafael at cs cornell edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20210629:114946 (All versions of this report)

**Short URL: **ia.cr/2021/890

[ Cryptology ePrint archive ]