A Note on One-way Functions and Sparse Languages

Oded's comments

This note is a culmination of a line of work [LP20,...,IRS21] that related the existence of hard-on-the-average problems that are morally sparse to the existence of one-way functions. In the current work, the morally sparse aspects takes the most transparent form.

In retrospect, this reminds me of my own note on computational indistinguishability in which an equivalence is proved between the existence of pseudorandom generators (equiv., of one-way functions) and the existence of samplable distributions that are computationally indistinguishable and yet statistically far apart. The point is that a relatively sparse problem (i.e., sparse with respect to the distribution on which it is hard) as in the first item of the abstract (below) yields a pair of disjoint distributions (one on Yes-instances and one on No-instances) that are computational indistinguishable although typically elements in one distribution have significantly larger probability weight than in the other. Needless to say, this pair of distributions is not necessarily sampleable (i.e., it falls short from the condition of the foregoing note), but if one-way functions do not exist then we can distinguish these two distributions by approximating the probability weight of instances (by inverting the sampling procedure). Of course, the foregoing note is not really used; it merely plays a role in my way of thinking about this result.

The take home message is that the existence of a relatively sparse problem as in the first item below implies that it must be typically hard to estimate the probability weight of elements in the sampled distribution; that is, that the sampling process is typically hard to invert, and yields a one-way function. On the other hand, the existence of pseudorandom generators implies a problem as in the first item (e.g., consider the set of pseudorandom outputs and a distribution that is pseudorandom with probability half and totally random otherwise).

The original abstract

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.

Available from ECCC TR21-092