Paper 2021/890

On One-way Functions and Sparse Languages

Yanyi Liu, Cornell Tech
Rafael Pass, Cornell Tech, Tel-Aviv University
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 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 \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 inspired 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.
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

BibTeX

@misc{cryptoeprint:2021/890,
      author = {Yanyi Liu and Rafael Pass},
      title = {On One-way Functions and Sparse Languages},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/890},
      year = {2021},
      url = {https://eprint.iacr.org/2021/890}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.