Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond

One-way functions (OWFs) form the foundation of modern cryptography, yet their unconditional existence remains a major open question. In this work, we study this question by exploring its relation to lossy reductions, i.e., reductions $R$ for which it holds that $I(X;R(X)) \ll n$ for all distributions $X$ over inputs of size $n$. Our main result is that either OWFs exist or any lossy reduction for any promise problem $Π$ runs in time $2^{Ω(\logτ_Π/ \log\log n)}$, where $τ_Π(n)$ is the infimum of the runtime of all (worst-case) solvers of $Π$ on instances of size $n$. In fact, our result requires a milder condition, that $R$ is lossy for sparse uniform distributions (which we call mild-lossiness). It also extends to $f$-reductions as long as $f$ is a non-constant permutation-invariant Boolean function, which includes And-, Or-, Maj-, Parity-, Modulo$_k$, and Threshold$_k$-reductions. Additionally, we show that worst-case to average-case Karp reductions and randomized encodings are special cases of mildly-lossy reductions and improve the runtime above as $2^{Ω(\log τ_Π)}$ when these mappings are considered. Restricting to weak fine-grained OWFs, this runtime can be further improved as $Ω(τ_Π)$. Taking $Π$ as $kSAT$, our results provide sufficient conditions under which (fine-grained) OWFs exist assuming the Exponential Time Hypothesis (ETH). Conversely, if (fine-grained) OWFs do not exist, we obtain impossibilities on instance compressions (Harnik and Naor, FOCS 2006) and instance randomizations of $kSAT$ under the ETH. Finally, we partially extend these findings to the quantum setting; the existence of a pure quantum mildly-lossy reduction for $Π$ within the runtime $2^{o(\logτ_Π/ \log\log n)}$ implies the existence of one-way state generators.