Paper 2025/778

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

Abstract

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 $$ for which it holds that $$ for all distributions $$ over inputs of size $$. Our main result is that either OWFs exist or any lossy reduction for any promise problem $$ runs in time $$, where $$ is the infimum of the runtime of all (worst-case) solvers of $$ on instances of size $$. More precisely, by having a reduction with a better runtime, for an arbitrary promise problem $$, and by using a non-uniform advice, we construct (a family of) OWFs. In fact, our result requires a milder condition, that $$ is lossy for sparse uniform distributions (which we call mild-lossiness). It also extends to $$-reductions as long as $$ is a non-constant permutation-invariant Boolean function, which includes $$, $$-, and $$-reductions. Additionally, we show that worst-case to average-case Karp reductions and randomized encodings are special cases of mild-lossy reductions and improve the runtime above as $$ when these mappings are considered. Restricting to weak fine-grained OWFs, this runtime can be further improved as $$. Intuitively, the latter asserts that if weak fine-grained OWFs do not exist then any instance randomization of any $$ has the same runtime (up to a constant factor) as the best worst-case solver of $$. Taking $$ as $$, 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 $$ under the ETH. Moreover, the analysis can be adapted to studying such properties of any $$-complete problem. Finally, we partially extend these findings to the quantum setting; the existence of a pure quantum mildly-lossy reduction for $$ within the runtime $$ implies the existence of one-way state generators, where $$ is defined with respect to quantum solvers.