Welcome to the resource topic for 2021/890
Title:
A Note on One-way Functions and Sparse Languages
Authors: Yanyi Liu, 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.
ePrint: https://eprint.iacr.org/2021/890
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .