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 $\mathrm{\Pi }$ runs in time $2^{\mathrm{\Omega }(\log {\tau }_{\mathrm{\Pi }}\mathrm{/}\log \log n)}$, where ${\tau }_{\mathrm{\Pi }}(n)$ is the infimum of the runtime of all (worst-case) solvers of $\mathrm{\Pi }$ 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^{\mathrm{\Omega }(\log {\tau }_{\mathrm{\Pi }})}$ when these mappings are considered. Restricting to weak fine-grained OWFs, this runtime can be further improved as $\mathrm{\Omega }({\tau }_{\mathrm{\Pi }})$. Taking $\mathrm{\Pi }$ 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 $\mathrm{\Pi }$ within the runtime $2^{o(\log {\tau }_{\mathrm{\Pi }}\mathrm{/}\log \log n)}$ implies the existence of one-way state generators.