REVIEW 6 major objections 5 minor 12 references
Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond
T0 review · 6 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read This paper argues for a dichotomy: either one-way functions exist, or every sufficiently lossy reduction for a hard problem runs nearly as slowly as solving the problem.
desk verdict A potentially important extension of lossy-reduction cryptography that currently rests on an unproven key lemma; worth refereeing but needs Section 3 fixed first. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is the extended disguising lemma (Lemma 9), a quantitative Fano-type statement. It starts from an $f$-distinguisher reduction $R$ for a promise problem $\Pi$: a map such that an unbounded distinguisher can detect whether a non-constant permutation-invariant Boolean function $f$ applied to the characteristic vector of $m$ inputs has value 0 or 1; this covers Or-, And-, Majority-, Parity-, Mod-, and Threshold-reductions, as well as Karp, non-adaptive Turing, and compression reductions. Mild lossiness says $R$ is $\ell$-lossy when the inputs are drawn from sparse uniform distributions supported on the YES and NO instances. The lemma concludes that there exist sparse distributions $D_0, D_1$, supported respectively on NO and YES instances, such that replacing one input by an arbitrary instance of the same type changes the expected output distribution by at most $\delta + 2(m+1)/(d+1) + 2\varepsilon$, where $\delta = \min\{\sqrt{\ell\ln 2/(2m)}, 1-2^{-\ell/m-2}\}$. This distributional stability is what makes the two circuits $C_0$ and $C_1$ in the construction statistically close on NO inputs and far on YES inputs; the one-way candidate $F(b,r) = C_b(r)$ inherits its security from that gap. The proof obtains sparseness from a sparse-strategy bound for zero-sum games applied twice around the minimax theorem, once for each player.
What would settle it
One concrete way to test the chain: for small parameters (say $n=4$, $m=3$, $d=2$, $\ell=1$), search for a deterministic map $R:\{0,1\}^{mn}\to\{0,1\}^{k}$ and disjoint sets $S_0,S_1$ such that $R$ is splitting $\ell$-lossy on all $ds$-uniform distributions but the expected trace distance in the disguising lemma exceeds $\delta + 2(m+1)/(d+1)+2\varepsilon$. An explicit counterexample of that form, checked by directly computing mutual information and trace distances, would falsify the missing lemma and with it the central claim; systematic absence of such counterexamples at small scales would support it.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is a quantitative dichotomy. For a promise problem $\Pi$, let $\tau_\Pi(n)$ be the infimum runtime of a worst-case solver on $n$-bit instances. The paper constructs a family of non-uniform functions $F_\Pi$ such that either $F_\Pi$ is a one-way function, or every $f$-distinguisher reduction for $\Pi$ with mild lossiness at most $m(\tau_\Pi/\log\log n - \log n)$ bits and error at most $2^{-\tau_\Pi(n)-8}$ must run in time $2^{\Omega(\tau_\Pi/\log\log n)}$; here $f$ may be any non-constant permutation-invariant Boolean function. In words, a reduction that hides information about its input cannot substantially beat the best solver for that problem unless one-way functions exist. Special cases are sharpened: worst-case-to-average-case Karp reductions and randomized encodings inherit the stronger bound $2^{\Omega(\tau_\Pi)}$, weak fine-grained one-way functions give the bound $\Omega(\tau_\Pi)$, and instantiated with $k$SAT under ETH these become near-exponential lower bounds on compressing and randomizing $k$SAT instances. The quantum version of the argument derives one-way state generators from pure quantum mildly-lossy reductions.
Load-bearing premise
The entire chain rests on the unproved transfer stated in Lemma 10 of Section 3: that a reduction which is $\ell$-lossy on sparse uniform distributions is automatically $\delta$-distributionally stable, with $\delta = \min\{\sqrt{\ell\ln 2/(2m)}, 1-2^{-\ell/m-2}\}$. The paper says this follows directly from splitting lossiness but supplies no proof; if that transfer fails in the sparse-uniform regime, the zero-knowledge, one-way-function, and one-way-state-generator theorems do not follow.
Editorial extensions
If this is right
- Under ETH, if infinitely often one-way functions do not exist, then any $f$-compression reduction of $k$SAT that compresses $mn$ bits to $m(s^*_k n/(\log n\log\log n)-\log n)$ bits with error at most $2^{-s^*_k n/\log n-8}$ must run in time $2^{\Omega(n/(\log n\log\log n))}$; in particular, any polynomial-parameter compression to $n^{\epsilon}$ bits is nearly exponential.
- Under ETH, if infinitely often weak fine-grained one-way functions do not exist, then any worst-case-to-average-case reduction for $k$SAT with small constant error and distance $d\le m^{2.5}n/2^{1.5 s^*_k n/\log n}$ runs in time $\Omega(2^{s^*_k n/\log n})$, so randomizing worst-case $k$SAT instances is essentially as hard as solving them.
- Worst-case-to-average-case Karp reductions and randomized encodings are special cases of mildly-lossy reductions, so the improved bounds $2^{\Omega(\tau_\Pi)}$ and $\Omega(\tau_\Pi)$ apply to them, giving impossibility results for instance randomization of arbitrary promise problems, not just NP problems.
- In the quantum setting, a pure quantum mildly-lossy reduction running faster than $2^{o(\log\tau^Q_\Pi/\log\log n)}$ for a quantumly hard problem yields one-way state generators; conversely, absence of infinitely often one-way state generators forces such reductions to run in time $2^{\Omega(\tau^Q_\Pi/\log\log n)}$.
Reading between the lines
- Editorial extension: the dichotomy sets a concrete research target: a subexponential-time instance randomization of any NP-complete problem would, by the paper's Corollary 7, yield weak fine-grained one-way functions, making fast instance randomization a direct construction route to a cryptographic primitive.
- Editorial extension: the same dichotomy would transfer to lattice problems if constant-approximation GapSVP under Gap-ETH admitted mildly-lossy reductions with subexponential runtime; the authors list this as an open question, and the lattice structure they expect might be the most natural place to try to realize or refute the missing Lemma 10.
- Editorial extension: the bounds are derived with an unbounded distinguisher inside the definition of $f$-distinguisher reduction; replacing that distinguisher by an efficient one would be a natural stress test that separates the information-theoretic part of the dichotomy from the computational part, and would show how much of the lower bound survives when the reduction's target problem must itsel
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces the notion of mild-lossiness (lossiness with respect to sparse uniform distributions) and f-distinguisher reductions, generalizing the lossy-reduction framework of Drucker and Ball et al. The central technical lemma (Lemma 9, Extended Disguising Lemma) claims that a splitting ℓ-lossy mapping over ds-uniform distributions is δ-QDS with δ = min{√(ℓ ln 2/(2m)), 1−2^{−ℓ/m−2}}. From this lemma the authors derive: reductions of mildly-lossy problems to SZK/QSZK (Theorem 1); constructions of EFI pairs, OWFs, and OWSGs from mildly-lossy or worst-case-to-distribution reductions (Theorems 2-4 and corollaries); and hardness-versus-one-wayness dichotomies culminating in Theorem 8 (if infinitely-often OWFs do not exist, then any mildly-lossy f-distinguisher reduction for a problem with exact hardness τ_Π has runtime 2^{Ω(τ_Π/log log n)}) and the ETH-based corollaries for kSAT. A quantum extension gives OWSGs from quantum mildly-lossy reductions. The paper also proves that worst-case-to-average-case Karp reductions and randomized encodings are mildly-lossy.
Significance. If the proofs were complete, this would be a substantial contribution: it would show that the absence of OWFs forces strong quantitative lower bounds on lossy reductions of hard problems, linking cryptography to worst-case complexity in the spirit of BBD+20; it extends Drucker's SZK results to arbitrary non-constant permutation-invariant f; and it initiates a quantum analogue via OWSGs. The paper is also methodologically clean in that no parameters are fitted and the conditional results are derived from externally defined hardness measures; the formal definitions (f-distinguisher reductions, mild-lossiness) are useful abstractions. However, because the central disguising lemma rests on an unproved transfer (Lemma 10) and several quantitative claims are inconsistent, the results are currently conditional on a nontrivial missing proof.
major comments (6)
- [Section 3, Lemma 10] Lemma 10 is asserted without proof: the text states that it 'can be argued directly from splitting lossiness' and that restrictions on input distributions carry over. This is precisely the nontrivial step that distinguishes the present work from Drucker's compression-based proof and from [BBD+20]; under splitting lossiness restricted to ds-uniform distributions, the input-distribution class is not closed under the operations used in the game-value argument (e.g., the marginal distributions obtained by conditioning are not necessarily ds-uniform). Lemma 10 is used in the proofs of Lemmas 11 and 12 and therefore in Lemma 9, and Lemma 9 underpins Theorems 1, 3, 4, 7, 8, 13, and 14. A complete proof of Lemma 10, or a different argument supplying the δ-QDS property for the sparse-uniform regime, is required before the main results can be evaluated.
- [Section 3, proof of Lemma 9] The last step of the proof of Lemma 9 states that 'the number of possible choices for Player 1 is |S0 ∪ S1| ≤ 2^n' and applies Lemma 2 with s = ⌈n ln 2/(2ε²)⌉. However, Player 1's pure strategies are pairs of d-element multisets (K,T), so the number of strategies is at least |S0|^d · |S1|^d / d!² ≈ 2^{2dn}. Lemma 2 therefore requires the sparsifying support size for Player 2 to be at least d n ln 2/ε², not n ln 2/(2ε²). The stated s is too small by a factor of roughly 2d, and the bound on the size of the collections K_1,…,K_s and T_1,…,T_s in the lemma's conclusion does not follow. This also affects the claimed advice size of 4mn/γ in Theorem 1.
- [Abstract vs. Theorem 8 vs. its proof] The main quantitative claim is stated inconsistently. The abstract and Section 1.2 state the lower bound as 2^{Ω(log τ_Π / log log n)}; Theorem 8 states T = 2^{Ω(τ_Π / log log n)}; and the proof of Theorem 8 concludes with 'the runtime must be at least 2^{Ω(τ_Π / log n)}'. These are different functions (e.g., for τ_Π(n)=n, they are exp(O(log n / log log n)), exp(Ω(n/log log n)), and exp(Ω(n/log n)), respectively). The authors must identify the intended bound, state it uniformly, and ensure the proof derives exactly that bound; the current mismatch makes the main theorem ambiguous.
- [Section 9, Lemma 20 and Theorem 8 proof] Lemma 20 is only sketched and, as stated, applies to reductions with error μ 'within a constant distance from 1/2'. In Theorem 8 the error is μ ≤ 2^{-τ_Π(n)-8}, which is far from 1/2. The proof nevertheless uses Lemma 20 to conclude that m = 2^{ω(τ(n)+log n)} implies T = 2^{ω(τ(n)+log n)}. No argument is given for the small-error regime. Since this step is needed to obtain a runtime lower bound (as opposed to a lower bound on m), Theorem 8's conclusion is not currently justified.
- [Section 8.1, Theorem 5] The sparseness condition and the entropy bound in Theorem 5 are inconsistent. The statement quantifies over pairwise independent 2^{9mn/γ³}-uniform distributions, but the proof asserts α_X ≥ γ³/2^{9mn} and concludes -log α_X ≤ 9 + log(mn/γ³). If the support size is 2^{9mn/γ³}, then α_X ≥ 2^{-9mn/γ³} and -log α_X grows as 9mn/γ³, not logarithmically; if the intended support size is 2^9 · mn/γ³, the notation at Definition 19 and in the theorem must be corrected. As written, the claimed mild-lossiness bound λ = max{1, 13+log(mnd²/γ³)} does not follow, and this propagates to Corollaries 1-4 and the WC-DIST based theorems.
- [Section 9, Lemma 22] Lemma 22 is false as stated. The condition 'g(n) > 2^{cτ(n)} for every constant c < 1' is satisfied by g(n)=2^{τ(n)}/τ(n), yet g(n)=o(2^{τ(n)}). The proof of Theorem 10 relies on Lemma 22 to convert exclusion of runtimes O(2^{τ(n)/(1+η)}) for all η>0 into the conclusion T=Ω(2^{τ_Π(n)}); this conversion needs a correct argument (e.g., a lower bound of 2^{τ_Π(n)-o(τ_Π(n))} rather than Ω(2^{τ_Π(n)})), and the theorem's claim must be adjusted accordingly.
minor comments (5)
- [Section 1.2 and Definition 19] The support-size notation '29mn/γ³' and '29n/γ³' is missing superscripts; it should be written as 2^{9mn/γ³} or 2^9 · mn/γ³, and the two occurrences must be made consistent.
- [Section 5, Algorithm 2 and Theorem 1] The claimed advice size 4mn/γ does not match the parameters s = ⌈n ln2/(2ε²)⌉ and d = ⌈(m+1)/ε⌉ with ε=γ/4, which give a larger expression; please re-derive the advice size.
- [Section 2, Definition 4] The phrase 'for any non-uniform classical-advice algorithm A with runtime at most T(n) over n-bit inputs, and any sufficiently large n ∈ N, there exists an input x' should clarify that the probability Pr[A(x)=χ_Π(x)] is over A's internal randomness only.
- [Section 9, Corollary 9] In Item II, the expression 'any perfect f^m-compression that compresses mn bits to mn^ε bits' uses the term 'perfect' without a definition for f^m-compressions in the text.
- [Throughout] There are several typos and grammatical errors, including 'the the' in Section 3, 'consisted of' in Definition 6, 'whe' in Definition 3, and 'd-secrery' in Section 8.2; these should be corrected in a final pass.
Circularity Check
No circularity found; the only load-bearing concern is an unproven bridging lemma, which is a correctness gap rather than a circular reduction.
full rationale
I walked the derivation chain and found no step in which a claimed prediction is equivalent to its inputs by construction. The paper's main theorems are genuine contrapositive implications: Theorem 7 constructs one-way functions from a mildly-lossy reduction whenever the underlying problem is hard, and Theorem 8 derives a runtime lower bound for such reductions from the assumed non-existence of infinitely-often one-way functions. The hardness measure tau_Pi is defined externally as the infimum solver runtime, and the parameter choices (gamma, mu, lambda, d) are explicit inequalities, not fitted constants. The technical machinery extends external results (Drucker's disguising lemma, Lipton-Young sparsification, Sason's reverse Pinsker inequality) rather than importing a conclusion from the authors' own prior work, and the reference list contains no self-citations. The notable weakness is Lemma 10, which asserts that splitting lossiness for sparse ds-uniform distributions implies delta-QDS and says only that this 'can be argued directly from splitting lossiness' without a proof; Lemmas 11, 12, and 9 rely on it. That is an important unverified step and a real correctness risk, but it is not circularity: the mutual-information assumption and the distributional-stability conclusion are distinct statements, and the paper does not reduce one to the other by definition. Thus the honest circularity finding is 0.
Assumptions & free parameters
assumptions (7)
- standard math Minimax theorem for finite zero-sum games (Lemma 1, von Neumann).
- standard math Lipton-Young sparsification lemma (Lemma 2, [LY94]).
- domain assumption Drucker's disguising lemma, adapted as Lemma 10 ([Dru15, Lemma 8.10]).
- standard math Sason's reverse Pinsker inequality (used in Theorem 5).
- domain assumption Worst-case hardness of Π, quantified by τ_Π (Definition 24).
- domain assumption Exponential Time Hypothesis (instantiations in Section 9).
- standard math Weak one-way functions imply one-way functions (Yao 1982).
Cite this review
Pith. "Pith review of Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond." pith.science (2026). https://pith.science/paper/K7PGOQLA
@misc{pith2026250521442,
author = {Pith},
title = {Pith review of: Cryptography from Lossy Reductions: Towards OWFs from ETH, and Beyond},
year = {2026},
howpublished = {\url{https://pith.science/paper/K7PGOQLA}},
note = {Machine review of arXiv:2505.21442}
}
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.
Reference graph
Works this paper leans on
- [12]
-
[1982]
John Bostanci, Luowen Qian, Nicholas Spooner, and Henry Yuen
BQSY24. John Bostanci, Luowen Qian, Nicholas Spooner, and Henry Yuen. An efficient quantum parallel repetition theorem and applications. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024,
work page 2024
-
[1994]
BM82. Manuel Blum and Silvio Micali. How to generate cryptographically strong sequences of pseudo random bits. In 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982),
work page 1982
-
[1998]
App17. Benny Applebaum. Garbled circuits as randomized encodings of functions: a primer. Cryptology ePrint Archive, Paper 2017/385,
work page 2017
-
[1999]
55 HN06. Danny Harnik and Moni Naor. On the compressibility of np instances and cryptographic applications. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06),
work page 2006
-
[2001]
Itay Berman, Akshay Degwekar, Ron D
BDR V19. Itay Berman, Akshay Degwekar, Ron D. Rothblum, and Prashant Nalini Vasudevan. Statistical difference beyond the polarizing regime. In Theory of Cryptography: 17th International Conference, TCC 2019, Nuremberg, Germany, December 1–5, 2019, Proceedings, Part II,
work page 2019
-
[2007]
Tomoyuki Morimae and Takashi Yamakawa
MY24. Tomoyuki Morimae and Takashi Yamakawa. One-wayness in quantum cryptography. In 19th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2024,
work page 2024
-
[2015]
BBD+20. Marshall Ball, Elette Boyle, Akshay Degwekar, Apoorvaa Deshpande, Alon Rosen, Vinod Vaikuntanathan, and Prashant Nalini Vasudevan. Cryptography from information loss. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020),
work page 2020
Show all 12 references
-
[2016]
Divesh Aggarwal and Noah Stephens-Davidowitz
AS18. Divesh Aggarwal and Noah Stephens-Davidowitz. (Gap/S)ETH hardness of SVP. STOC 2018,
2018
-
[2017]
Benny Applebaum and Pavel Raykov
AR16. Benny Applebaum and Pavel Raykov. On the relationship between statistical zero-knowledge and statis- tical randomized encodings. In Advances in Cryptology – CRYPTO 2016,
2016
-
[2020]
Zvika Brakerski, Ran Canetti, and Luowen Qian
BCQ23. Zvika Brakerski, Ran Canetti, and Luowen Qian. On the Computational Hardness Needed for Quantum Cryptography. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Leibniz International Proceedings in Informatics (LIPIcs),
2023
-
[2024]
Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan
BRSV17. Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017,
2017
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.