{"id":"c010b42d-bf16-4d9b-aa2c-dfd0dde9d7b2","arxiv_id":"2504.18188","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Quantum lifting theorems for random permutations and ideal ciphers convert quantum attacks into few-query classical attacks, giving tight double-sided search bounds and new post-quantum security for sponge and Davies-Meyer.","lead":"The paper proves a general lifting theorem: any quantum attack with q queries on a random permutation or ideal cipher can be converted into a classical attack with only k queries, losing a polynomial factor. This yields new post-quantum security results for the sponge hash and the Davies-Meyer construction.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Ideal-cipher lifting is unproven: the global goodness set couples distinct keys, so the reprogrammed oracle is not uniform; Theorem 5.7 and the Davies-Meyer application need a per-key goodness proof.","rationale":"The permutation lifting theorem (Theorem 4.1) appears solid: the measure-and-reprogram state decomposition is written out, the goodness condition is the right one for a single permutation, and Lemma 2.11 is proven. The concern is entirely in Section 5. The abstract and introduction advertise Theorem 1.2 as a central result, and the Davies-Meyer collision-resistance depends on it. Section 5 explicitly says 'instead of providing a formal proof, we will give a brief sketch,' and then asserts that Lemma 5.6 and Theorem 5.7 are 'essentially a duplicate.' That is precisely where the argument is least secure. My check shows the claimed duplication is not literal: the global goodness set in Definition 5.3 couples different keys through conditions E_{K_i}(x_i*) != E*_{K_j}(x_j*). The uniformity lemma used for the average over permutations (Lemma 2.11) requires invariance of the conditioned set under the relevant symmetry group; for ciphers with multiple distinct keys, the full fiber-wise group action does not preserve G. The small example with two keys shows the reprogrammed cipher's outputs are correlated, so it is not the uniform ideal cipher. This does not prove the theorem false; a per-key goodness definition would restore the product structure and likely fix the proof with the same loss. But as written, the theorem and all applications resting on it (Theorem 6.15, PGV lifting) are not established. The reader's weakest assumption pointed to the ideal-cipher proof sketch; I agree partially, but the concrete mechanism is cross-key coupling in the goodness set rather than repeated-key interference per se. Verdict: keep CONDITIONAL; acceptance should require a complete proof of the cipher uniformity step, ideally with the per-key goodness definition.","tokens_in":48732,"tokens_out":26521,"duration_ms":259373,"concrete_test":"1) Replace Definition 5.3's global goodness by per-key goodness: require E_{K_i*}(x_i*) != E*_{K_j*}(x_j*) only when K_i* = K_j*, and require x_i*/y_i* distinct only within each key. Re-prove Lemma 5.6 and Theorem 5.7 with this definition; if the (8q+1)^{2k} loss and the k^2/|X| bound survive, the theorem is salvageable. 2) Direct numeric check: for K1 != K2, X={0,1,2}, x1=x2=1, enumerate all (E,E*) satisfying Definition 5.2/5.3, compute E' = E[x1->_{K1}E*_{K1}(x1)][x2->_{K2}E*_{K2}(x2)], and test Pr[E'_{K1}(1)=E'_{K2}(1)] = 2/3 rather than 1/3. This confirms the analogue of Lemma 2.11 fails under the stated goodness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The ideal-cipher theorem (Theorem 5.7, hence Theorem 1.2) is used for the Davies-Meyer/PGV collision-resistance claim, and its proof is only a sketch. The load-bearing step is the cipher analogue of Lemma 2.11: after averaging over good pairs, the reprogrammed oracle E[x*->K* y*] must be distributed as a uniform ideal cipher. For permutations this follows because the good set G[x*] is invariant under left multiplication by any permutation. For ciphers, Definition 5.2/5.3 imposes the cross-key condition E_{K_i*}(x_i*) != y_j* for all i,j, including different keys. The fiber-wise action (sigma_K E, sigma_K E*) does not preserve this condition unless all sigma_K are equal; G is not a product set over keys. Consequently the distribution of the reprogrammed cipher under (E,E*) sampled from G is not uniform. Concretely, for K1 != K2, X={0,1,2}, x1=x2=1, enumerating Definition 5.3 gives Pr[E'_K1(1)=E'_K2(1)] = 2/3, whereas a uniform ideal cipher gives 1/3. So the asserted 'duplicate' proof cannot go through as written; Theorem 5.7 is unproven. A likely repair is to define goodness per key (restrict conditions only to pairs sharing the same key), which factors G into a product and preserves uniformity, with the same k^2/|X| bad-probability bound. The paper does not state or prove that variant.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces lifting theorems for the quantum random permutation model (QRPM) and the quantum ideal cipher model (QICM). For the permutation case, Theorem 4.1 states that any q-quantum-query adversary against a search game with k classical challenger queries can be simulated by a k-classical-query adversary losing only a factor (8q+1)^{2k}, up to a small bad-event term. The proof is carried out through a detailed state-decomposition and measure-and-reprogram argument. The paper then presents applications to the double-sided zero-search problem, fixed-point finding, the sponge construction, and Davies-Meyer/PGV hash functions. For the ideal cipher case, Theorem 5.7 is given as a proof sketch, with the claim that it follows by duplicating the permutation proof. The central permutation lifting theorem appears technically sound, but the ideal-cipher version has a genuine gap, and the sponge application contains a citation/query-count inconsistency that needs correction.","tokens_in":49072,"tokens_out":10261,"duration_ms":105884,"significance":"The paper's Section 4 is a substantial technical contribution: it gives a self-contained, parameter-free derivation of a QRPM lifting theorem, avoiding fitted constants and providing explicit polynomial losses in q. If valid, the theorem is a powerful general tool that unifies several prior problem-specific analyses and yields tight bounds for double-sided zero search and fixed-point finding. The applications to multi-round sponge are also valuable, and the paper is honest about their non-tightness. However, the ideal-cipher lifting theorem is load-bearing for the Davies-Meyer/PGV results, and as written that theorem is not proven; the asserted 'duplicate proof' fails because the cipher goodness condition does not preserve uniformity of the reprogrammed oracle. The sponge proof also needs a small but real correction in its use of the lifting theorem. These issues are fixable, but they must be addressed before the paper can be accepted.","major_comments":[{"comment":"The claim that Lemma 5.6 is 'essentially a duplicate' of Lemma 4.4 is not correct, because the cipher analogue of Lemma 2.11 fails. The goodness set G[K*, x*] is not invariant under the relevant group action. Concretely, let K1 ≠ K2, X = {0,1,2}, and x1* = x2* = 1. Write a = E_{K1}(1), b = E_{K2}(1), c = E*_{K1}(1), d = E*_{K2}(1). Definition 5.2 requires a ∉ {c,d} and b ∉ {c,d}. Conditioning on (E,E*) ∈ G, one obtains Pr[c = d] = ((1/3)(2/3)^2) / ((1/3)(2/3)^2 + (2/3)(1/3)^2) = 2/3, whereas for a uniform ideal cipher the reprogrammed values E'_{K1}(1) and E'_{K2}(1) are equal with probability 1/3. Equivalently, the per-key left-multiplication action (σ_K E_K, σ_K E*_K) does not preserve G unless all σ_K are equal. Hence the distribution of the reprogrammed cipher under (E,E*) ← G is not uniform, and the step 'by Lemma 2.11' in the proof of Theorem 5.7 is unavailable. Theorem 5.7, and therefore Theorem 1.2 and the Davies-Meyer/PGV application in Section 6.3, are unproven as written. A likely repair is to define goodness per key, imposing cross conditions only among pairs sharing the same key; that variant would factor G into a product and preserve uniformity, but it is neither stated nor proved in the manuscript.","section":"Section 5, Definitions 5.2–5.3 and Lemma 5.6"},{"comment":"The first reduction in the proof of Theorem 6.4 is attributed to Theorem 3.1, but Theorem 3.1 is the classical lifting theorem. To reduce a q-quantum-query adversary A to a classical algorithm B, the proof must invoke the quantum lifting theorem, Theorem 4.1. Moreover, the reduced algorithm B should make kℓ classical queries, not k, because each evaluation of Sponge^π costs ℓ permutation queries; the exponent (8q+1)^{2kℓ} and the quantity N = kℓ + k in the later use of Lemma 6.11 confirm that the intended parameter is kℓ. As written, the sentence 'There exists a k-classical-query algorithm B' in the proof is inconsistent with the reduction, and the proof does not follow from the cited theorem. This is a local correction, but it is necessary for the sponge applications to be valid.","section":"Section 6.2, proof of Theorem 6.4"}],"minor_comments":[{"comment":"The statement says 'the probability that (π,π*) ∈ G[x*] is at most k^2/|X|', but the proof upper-bounds the probability that (π,π*) is not in G[x*]. The intended inequality is Pr[(π,π*) ∉ G[x*]] ≤ k^2/|X|.","section":"Lemma 2.10"},{"comment":"The lemma says 'Let E be a (fixed) permutation', but in the cipher setting E should be a fixed cipher over K × X, not a permutation.","section":"Lemma 5.4"},{"comment":"Several references to the hit/miss definitions say 'Definition 6'; the correct references are Definition 2.12 for permutations and Definition 5.5 for ciphers.","section":"Appendix C, proof of Lemma 4.3"},{"comment":"The statement of Theorem 6.4 defines P_R^max using k-classical-query algorithms to a random function, while the reduction in the proof produces a classical algorithm making kℓ permutation queries. The query count should be stated consistently, e.g., by renaming the lifted query count or by clarifying that the k-query bound in the theorem refers to the final sponge-evaluation algorithm after merging the kℓ direct queries.","section":"Theorem 6.4 and its proof"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle to publication is the ideal-cipher lifting theorem. Section 5 is only a sketch, and the specific uniformity failure described in my report shows that the 'duplicate proof' claim is not merely lacking detail; it is false under the current goodness definition. I would encourage the editor to request a full proof of a corrected per-key goodness variant before acceptance. The sponge proof error is minor by comparison and easily fixed. The paper should also be checked against the concurrent work ACMT25, which the authors already cite, to ensure the remaining novelty claims are precise."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The permutation lifting theorem (Theorem 4.1) is a genuine and well-executed result, and it deserves to survive. The ideal-cipher version (Theorem 1.2 / 5.7) does not: the proof sketch rests on a uniformity claim that is false. The sponge section also has a query-count problem that needs fixing.\n\nWhat's new: extending the measure-and-reprogram technique from YZ21 to the QRPM, with the hit/miss handling and the state decomposition, is a real step forward. For a permutation with inverse oracle, the proof in Section 4 is complete as far as I can tell: the decomposition into 4q+1 terms, the goodness condition, the bad-probability bound, and the reduction to a k-query classical adversary all line up. The derived bounds for double-sided search and fixed-point finding are clean and tight up to constants.\n\nSoft spots. Section 5 is not a proof sketch; it is a place where the argument breaks. For permutations, the goodness set G[x*] is invariant under left multiplication by any sigma, which gives uniformity of the reprogrammed permutation. For ciphers, the cross-key condition E_{K_i*}(x_i*) != y_j* for all i,j couples the keys. The natural global left-action does preserve G, but the reprogrammed cipher is not uniform on G: a concrete enumeration with X of size 3 and two distinct keys gives Pr[E'_K1(1)=E'_K2(1)] = 2/3 under G, versus 1/3 for a uniform ideal cipher. So the 'duplicate of Lemma 2.11' cannot be true. Theorem 5.7 and the Davies-Meyer/PGV applications are unsupported as written. A per-key goodness condition might repair this, but that is not what the paper states or proves.\n\nSponge: the proof of Theorem 6.4 cites Theorem 3.1 (classical lifting) where it must use Theorem 4.1 (quantum), and the query count is off: for k sponge inputs, the challenger makes k*ell permutation queries, not k. The proof then counts B as a k-query algorithm when it should be k*ell-query. These look fixable, but the stated bounds do not follow from the argument given.\n\nBottom line: the permutation lifting theorem is a solid, citable contribution. The cipher half is currently a claim with a false supporting lemma, so the Davies-Meyer result should be considered open until repaired. This deserves a serious referee: a good referee can separate the two halves, accept the permutation result, and force the authors to either prove the cipher lemma properly or remove those applications.","headline":"Permutation lifting is solid; the ideal-cipher lifting is broken by a false uniformity lemma, and the sponge application has query-count errors.","tokens_in":49588,"tokens_out":6450,"would_cite":true,"duration_ms":61441,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For any $q$-query quantum adversary against an invertible random permutation or ideal cipher, there is a $k$-query classical adversary whose success probability is at least $((1-k^2/|X|)/(8q+1)^{2k})$ of the quantum adversary's.","keywords":["quantum lifting theorem","random permutation model","ideal cipher model","post-quantum security","measure-and-reprogram","quantum query complexity","sponge construction","Davies-Meyer hash functions"],"falsifier":"Run the cipher simulator from Section 5 on a small domain, say two keys with $|X|=8$ and $k=2$ target pairs that share a key, and compute the exact ratio between the success probability of the reprogrammed-cipher experiment and the simulator's output. If for $q=1$ that ratio is ever smaller than $1/(8q+1)^4$, the ideal-cipher lifting theorem is refuted.","tokens_in":48569,"feed_emoji":"🔐","tokens_out":12430,"duration_ms":116671,"temperature":0.7,"pith_summary":"This paper proves the first lifting theorems for the quantum random permutation and ideal cipher models. It shows that any quantum adversary making $q$ queries against an invertible random permutation or ideal cipher can be converted into a classical adversary making only $k$ queries, with success probability at least $((1-k^2/|X|)/(8q+1)^{2k})$ of the quantum adversary's. The point is that quantum security proofs in these models reduce to classical $k$-query bounds, at the price of a polynomial factor in $q$. The payoff is a tight bound for the double-sided zero-search game, the first non-trivial post-quantum bounds for multi-round sponge hashing, and collision resistance for the Davies-Meyer and PGV compression functions under quantum ideal ciphers.","feed_headline":"Quantum adversaries on permutations reduce to few classical queries","feed_subtitle":"A q-query quantum adversary's success can be matched by a k-query classical adversary, up to a (8q+1)^(2k) loss.","key_machinery":"The load-bearing mechanism is a measure-and-reprogram lemma for permutations. To simulate an adversary that queries a reprogrammed permutation $\\pi[x^*\\to y^*]$, the simulator guesses the first query that touches the target pair: a hit query on $x^*$ (or $y^*$ for an inverse query) or a miss query on $\\pi^{-1}(y^*)$ (or $\\pi(x^*)$), and reprograms the permutation by swapping the two affected outputs so injectivity is preserved. In the quantum case, the algorithm's state is decomposed by inserting projections at each query into at most $(8q+1)^{2k}$ subnormalized terms, each corresponding to one choice of simulator randomness: query index, hit-versus-miss, and whether reprogramming happens before or after the query. The triangle inequality and norm bounds turn this decomposition into the stated probability ratio, and a goodness condition, violated with probability at most $k^2/|X|$, ensures that successive reprogrammings do not interfere.","core_discovery":"The paper's central claim is Theorem 4.1: for any search game whose challenger makes at most $k$ classical queries to an invertible random permutation $\\pi$, and any adversary $\\mathcal{A}$ making $q$ quantum queries to $\\pi$ and $\\pi^{-1}$, there exists an adversary $\\mathcal{B}$ making at most $k$ classical queries whose success probability is at least $((1-k^2/|X|)/(8q+1)^{2k})$ times that of $\\mathcal{A}$. Theorem 5.7 extends the same statement to ideal ciphers, with the same loss. The paper establishes that quantum query access to a permutation or cipher does not change the asymptotic difficulty of search games beyond a fixed polynomial factor in $q$: any quantum attack with success probability $p$ is matched by a $k$-query classical attack with probability at least $p/(8q+1)^{2k}$, whenever the challenger is efficient. The theorems are then applied to prove tight bounds for generalized double-sided search, the first non-trivial post-quantum security bounds for constant-round sponge (preimage, one-wayness, and multi-collision resistance), and collision resistance for Davies-Meyer and group-1 PGV compression functions.","pith_inferences":["The constant $8$ in $(8q+1)^{2k}$ is a byproduct of the normal-form reduction from $q$ queries to $2q$ alternating forward and inverse queries; a tighter decomposition might lower it, which would sharpen every application's constant factor.","The paper's sponge bounds are meaningful only when the capacity is large relative to the squared query terms; extending the lifting to unbounded input lengths without this restriction would make the results usable for general-purpose hash functions.","If the missing proof of the cipher lifting theorem can be completed, then every classical ideal-cipher security proof for a search game automatically becomes a quantum ideal-cipher proof; Davies-Meyer collision resistance is the first beneficiary, but other block-cipher-based constructions would inherit the same reduction."],"forward_implications":["Any quantum query lower bound in the random permutation model now follows from the corresponding $k$-query classical bound with a $(8q+1)^{2k}$ overhead; the paper uses this to prove an $O(r_{\\max} q^2 / 2^{2n})$ bound for generalized double-sided search, tight against the quadratic-speedup search algorithm.","The ideal-cipher version lifts classical collision-resistance proofs from the ICM to the quantum ideal cipher model; the paper obtains $O(q^4/2^n)$ collision resistance for Davies-Meyer and all group-1 PGV compression functions.","Constant-round sponge gains the first non-trivial post-quantum preimage, one-wayness, and multi-collision resistance bounds whenever the capacity is large enough; for the single-round case the preimage bound matches the quantum search bound up to constants.","For any classically verifiable interactive search game whose challenger uses at most $k$ classical queries, the same reduction holds, so future random-permutation or ideal-cipher proofs can be adapted to quantum adversaries without problem-specific tools.","The double-sided zero-search conjecture is confirmed with a tight $O(q^2/2^n)$ bound, improving the previous $O(r_{\\max} q^3 / 2^{2n})$-type bound."],"supporting_citations":[{"why":"Supplies the random-oracle measure-and-reprogram lifting framework that the paper adapts to invertible permutations and ciphers.","marker":"[YZ21]"},{"why":"Posed the double-sided zero-search problem and compressed-permutation oracle approach that the paper's lifting theorem makes tight.","marker":"[Unr23]"},{"why":"Gives the previous permutation-superposition lower bounds the paper improves, including the generalized double-sided search bound.","marker":"[MMW24]"},{"why":"Provides the classical indifferentiability bound for the sponge construction used to transfer classical security to the quantum setting.","marker":"[BDPV08]"},{"why":"Establishes the classical collision-resistance bound for group-1 PGV compression functions, including Davies-Meyer, which is lifted to the quantum ideal cipher model.","marker":"[BRS02]"},{"why":"Proved quantum one-wayness for single-round sponge and gave a prior double-sided zero-search constant; the paper compares and extends these results to multi-round sponge.","marker":"[CP24]"},{"why":"Introduced the measure-and-reprogram technique in the quantum random-oracle model that underlies the new simulator.","marker":"[DFMS19]"},{"why":"Showed Davies-Meyer one-wayness and gave a fixed-point finding bound that Corollary 6.3 improves.","marker":"[HY18]"}],"fun_headline_variants":["Quantum query advantage over classical is only polynomial in query count","Quantum lifting: classical queries match quantum attacks up to polynomial loss","Quantum query complexity reduced to classical with polynomial loss","Classical adversary can match any quantum query attack with polynomial loss","Quantum lifting: q-query attacks on ciphers are k-query classically simulable"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The ideal-cipher theorem rests on the unproven claim that the permutation measure-and-reprogram argument carries over to ciphers whose keys are repeated among the $k$ target pairs; if reprogrammings under the same key interfere with one another, the theorem and its Davies-Meyer applications fall apart.","fun_headline_variants_meta":{"raw":{"variants":["Quantum query advantage over classical is only polynomial in query count","Quantum lifting: classical queries match quantum attacks up to polynomial loss","Quantum query complexity reduced to classical with polynomial loss","Classical adversary can match any quantum query attack with polynomial loss","Quantum lifting: q-query attacks on ciphers are k-query classically simulable"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001637,"raw_usage":{"total_tokens":6491,"prompt_tokens":913,"completion_tokens":5578,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":529,"completion_tokens_details":{"reasoning_tokens":5489}},"tokens_in":529,"tokens_out":5578,"duration_ms":43097,"temperature":1.0,"reasoning_tokens":5489,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T10:23:59.676817+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the cipher simulator from Section 5 on a small domain, say two keys with $|X|=8$ and $k=2$ target pairs that share a key, and compute the exact ratio between the success probability of the reprogrammed-cipher experiment and the simulator's output. If for $q=1$ that ratio is ever smaller than $1/(8q+1)^4$, the ideal-cipher lifting theorem is refuted.","supporting_citations":[],"review_version":1}