CryptoDB
On One-way Functions and Sparse Languages
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2023 |
| 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, results from the elegant recent paper by Ilango, Ren and Santhanam (IRS, STOC'22), which presents similar connections for \emph{specific} sparse languages. |
BibTeX
@inproceedings{tcc-2023-33643,
title={On One-way Functions and Sparse Languages},
publisher={Springer-Verlag},
author={Yanyi Liu and Rafael Pass},
year=2023
}