On one-way functions and sparse languages

DOI10.1007/978-3-031-48615-9_8MaRDI QIDQ6581789zbMATH OpenFDO

Authors Yanyi Liu, Rafael Pass

Publication date 1 August 2024

Full work available at URL https://doi.org/10.1007/978-3-031-48615-9_8

zbMATH Keywords

one-way functionssparse languages

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Measures of information, entropy (94A17)

Review text

The authors show the 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 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\mathrm{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, where a language \(L\) is said to be \(S(\cdot)\)-sparse if \(|L\cap\{0, 1\}^n|\leq S(n)\) for all \(n\in N\).\N\NTheir results are inspired by, and generalize, results from the elegant recent paper by \textit{R. Ilango} et al. [STOC 2022, 1575--1583 (2022; Zbl 07774439)], which presents similar connections for specific sparse languages\N\NFor the entire collection see [Zbl 1542.94005].

Recommendations

• On building fine-grained one-way functions from strong average-case hardness
• One-way functions and circuit complexity
• On building fine-grained one-way functions from strong average-case hardness
• scientific article; zbMATH DE number 3990863
• scientific article; zbMATH DE number 4125016

Cites work

• A method for obtaining digital signatures and public-key cryptosystems
• A Pseudorandom Generator from any One-way Function
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Bit commitment using pseudorandomness
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• scientific article; zbMATH DE number 4779 (Why is no real title available?)
• New directions in cryptography
• On the Cryptographic Applications of Random Functions (Extended Abstract)
• On the notion of infinite pseudorandom sequences
• Probabilistic encryption
• Robustness of average-case meta-complexity via pseudorandomness
• The tale of one-way functions
• Three approaches to the quantitative definition of information^*

Cited in

(1)

• Lower bounds for Levin-Kolmogorov complexity

This page was built for publication: On one-way functions and sparse languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6581789)