Welcome to the resource topic for
**2021/890**

**Title:**

A Note on One-way Functions and Sparse Languages

**Authors:**
Yanyi Liu, 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.

**ePrint:**
https://eprint.iacr.org/2021/890

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .