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

• URL: http://arxiv.org/abs/2505.21442v2
• Date: Mon, 30 Jun 2025 09:24:50 GMT
• Title: Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond
• Authors: Pouria Fallahpour, Alex B. Grilo, Garazi Muguruza, Mahshid Riahinia,
• Abstract summary: One-way functions (OWFs) form the foundation of modern cryptography, yet their unconditional existence remains a major open question.<n>We show that either OWFs exist or any lossy reduction for any promise problem $Pi$ runs in time $2Omega(logtau_Pi / loglog n)$.
• Score: 1.0687104237121408
• License: http://creativecommons.org/licenses/by/4.0/
• 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$. 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^{\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)$. Taking $\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 $\Pi$ within the runtime $2^{o(\log\tau_\Pi / \log\log n)}$ implies the existence of one-way state generators.

Related papers

• Batched Stochastic Bandit for Nondegenerate Functions [8.015503209312786]
  This paper studies batched bandit learning problems for nondegenerate functions.<n>We introduce an algorithm that solves the batched bandit problem for nondegenerate functions near-optimally.
  arXiv  Detail & Related papers  (2024-05-09T12:50:16Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
  We study pure exploration with infinitely many bandit arms generated i.i.d. from an unknown distribution. Our goal is to efficiently select a single high quality arm whose average reward is, with probability $1-delta$, within $varepsilon$ of being among the top $eta$-fraction of arms.
  arXiv  Detail & Related papers  (2023-06-03T04:00:47Z)
• Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs [66.47284608209692]
  We propose an algorithm for general acyclic WFSAs which runs in $Oleft(|E| + s |Sigma| |Q| T_textmax log|Sigma|right)$. When the failure transition topology satisfies a condition exemplified by CRFs, the $T_textmax$ factor can be dropped. In the latter case (ring-weighted acyclic WFSAs), we also give an alternative algorithm complexity with $style Oleft(|E| + |Sigma| |
  arXiv  Detail & Related papers  (2023-01-17T13:15:44Z)
• On Submodular Contextual Bandits [92.45432756301231]
  We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function. We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
  arXiv  Detail & Related papers  (2021-12-03T21:42:33Z)
• Cascading Bandit under Differential Privacy [21.936577816668944]
  We study emphdifferential privacy (DP) and emphlocal differential privacy (LDP) in cascading bandits. Under DP, we propose an algorithm which guarantees $epsilon$-indistinguishability and a regret of $mathcalO(fraclog3 Tepsilon)$ for an arbitrarily small $xi$. Under ($epsilon$,$delta$)-LDP, we relax the $K2$ dependence through the tradeoff between privacy budgetepsilon$ and error probability $
  arXiv  Detail & Related papers  (2021-05-24T07:19:01Z)
• Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$ Geometry [69.24618367447101]
  Up to logarithmic factors the optimal excess population loss of any $(varepsilon,delta)$-differently private is $sqrtlog(d)/n + sqrtd/varepsilon n.$ We show that when the loss functions satisfy additional smoothness assumptions, the excess loss is upper bounded (up to logarithmic factors) by $sqrtlog(d)/n + (log(d)/varepsilon n)2/3.
  arXiv  Detail & Related papers  (2021-03-02T06:53:44Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• List-Decodable Subspace Recovery: Dimension Independent Error in Polynomial Time [5.812499828391904]
  In list-decodable subspace recovery, the input is a collection of $n$ points $alpha n$ (for some $alpha ll 1/2$) of which are drawn i.i.d. from a distribution $mathcalD$. In this work, we improve on results on all three fronts: emphcertifiable anti-concentration error via a faster fixed-polynomial running time.
  arXiv  Detail & Related papers  (2020-02-12T18:30:09Z)
• On the Complexity of Minimizing Convex Finite Sums Without Using the Indices of the Individual Functions [62.01594253618911]
  We exploit the finite noise structure of finite sums to derive a matching $O(n2)$-upper bound under the global oracle model. Following a similar approach, we propose a novel adaptation of SVRG which is both emphcompatible with oracles, and achieves complexity bounds of $tildeO(n2+nsqrtL/mu)log (1/epsilon)$ and $O(nsqrtL/epsilon)$, for $mu>0$ and $mu=0$
  arXiv  Detail & Related papers  (2020-02-09T03:39:46Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.