Welcome to the resource topic for 2025/778
Title:
Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond
Authors: Pouria Fallahpour, Alex B. Grilo, Garazi Muguruza, Mahshid Riahinia
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 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 \Pi runs in time 2^{\Omega(\log\tau_\Pi / \log\log n)}, where \tau_\Pi(n) is the infimum of the runtime of all (worst-case) solvers of \Pi on instances of size n. More precisely, by having a reduction with a better runtime, for an arbitrary promise problem \Pi, and by using a non-uniform advice, we construct (a family of) OWFs. 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 \text{And-, Or-, Maj-, Parity-}, \text{Mod}_k-, and \text{Threshold}_k-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 2^{\Omega(\log \tau_\Pi)} when these mappings are considered. Restricting to weak fine-grained OWFs, this runtime can be further improved as \Omega(\tau_\Pi).
Intuitively, the latter asserts that if weak fine-grained OWFs do not exist then any instance randomization of any \Pi has the same runtime (up to a constant factor) as the best worst-case solver of \Pi.
Taking \Pi as k\text{Sat}, 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 k\text{Sat} under the ETH.
Moreover, the analysis can be adapted to studying such properties of any \text{NP}-complete problem.
Finally, we partially extend these findings to the quantum setting; the existence of a pure quantum mildly-lossy reduction for \Pi within the runtime 2^{o(\log\tau_\Pi / \log\log n)} implies the existence of one-way state generators, where \tau_\Pi is defined with respect to quantum solvers.
ePrint: https://eprint.iacr.org/2025/778
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 .