On one-way functions and sparse languages (Q6581789)

The authors show the 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 existence 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 existence of a \(S(\cdot)\)-sparse language \(L\in\mathrm{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, where a language \(L\) is said to be \(S(\cdot)\)-sparse if \(|L\cap\{0, 1\}^n|\leq S(n)\) for all \(n\in N\).\N\NTheir results are inspired by, and generalize, results from the elegant recent paper by \textit{R. Ilango} et al. [STOC 2022, 1575--1583 (2022; Zbl 07774439)], which presents similar connections for specific sparse languages\N\NFor the entire collection see [Zbl 1542.94005].