You are looking at a specific version 20210629:114946 of this paper. See the latest version.

Paper 2021/890

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
one-way functionsaverage-case complexity
Contact author(s)
yl2866 @ cornell edu,rafael @ cs cornell edu
History
2023-02-10: revised
2021-06-29: received
See all versions
Short URL
https://ia.cr/2021/890
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.