We 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.

We 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.