{"id":"b6495969-2676-4077-b67c-449e558c25e6","arxiv_id":"2509.09900","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"New hybrid quantum-classical measure-and-reprogram theorems reduce NISQ security games to few-query adversaries, yielding the first direct product theorems and hardness bounds in the hybrid QROM.","lead":"This paper proves new 'lifting' theorems: a hybrid quantum-classical attacker's chance of solving a search game is bounded by a much simpler attacker that makes only a handful of queries, losing a quantified factor. This gives a general tool for proving NISQ-era security of cryptographic tasks by computing one combinatorial number.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (6) orthogonality fails when reprogrammed value equals original oracle value; history register only distinguishes schedules if G(x)≠H(x).","rationale":"The reader's weakest_assumption correctly identified Eq. (6) as the linchpin of the proof. Our stress test sharpens this: the asserted orthogonality is not a mathematical identity because the history register alone cannot distinguish a reprogrammed classical query from an unreprogrammed one when G(x)=H(x). This is a concrete, checkable failure mode, not just a missing detail. The proof of Lemma 3.6 relies on Eq. (6) to move from a norm of a sum to a sum of norms; without exact orthogonality, cross terms appear and the advertised polynomial loss may no longer follow. The theorem statement is for arbitrary H,G, so a deterministic counterexample (e.g., H=G) invalidates the proof as written. This concern does not necessarily refute the theorem—a modified argument might condition on G(x)≠H(x) or absorb the cross terms—but it means the current proof is incomplete. The reader's CONDITIONAL verdict remains appropriate: the central claim is plausible but not rigorously established. We therefore leave the verdict unchanged and propose a concrete test to settle the impact.","tokens_in":34579,"tokens_out":12598,"duration_ms":145376,"concrete_test":"Take the minimal instance k=1, q=0, c=1, X=Y={0,1} with H(0)=0, G(0)=0. Construct the two subnormalized states in Eq. (6): one where the single classical query is reprogrammed, one where it is not. The history register contains |(0,0)> in both cases, so the inner product is 1, not 0. Generalize: for any H,G, the inner product equals |{x: G(x)=H(x)}|/|X| (or 1/|Y| for random G); if nonzero, Eq. (6) fails. Then re-derive Eq. (7) using the actual inner product and check whether the final loss remains O(q^2/k^2 + c/k)^k or acquires an extra factor.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is Eq. (6) in Section 3.2. It asserts that states corresponding to different classical reprogramming schedules are orthogonal because the history register differs. But the history register records input–output pairs, not whether reprogramming occurred. For a classical query on input x, the recorded pair is (x, G(x)) if the schedule reprograms that query and (x, H(x)) if it does not. These are distinct only when G(x)≠H(x). For fixed H,G they can coincide; over random H,G this occurs with probability 1/|Y| per input. Thus Eq. (6) is not an identity. Eq. (7) uses Eq. (6) to replace the norm of a sum by the sum of norms. If orthogonality fails, Cauchy-Schwarz introduces cross terms adding a combinatorial factor (equal to the number of classical reprogramming choices), which could degrade the claimed O(q^2/k^2 + c/k)^k loss. The paper gives no argument that this extra factor is negligible. Additionally, Lemma 3.7's counting uses (c choose k-t) while Definition 3.3 allows v to be drawn from q+c+k positions, including the k final typing queries; this inconsistency also affects the loss factor.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a 'hybrid coherent measure-and-reprogram' framework for security games in the quantum random oracle model, targeting NISQ settings. The central claim (Theorem 3.1) is a lifting theorem: for any hybrid algorithm with q quantum and c classical queries, there is a simulator making only k queries that wins with probability at least 1/O((q^2/k^2 + c/k))^k times the original algorithm's success probability. The authors also state lifting theorems for noisy oracles and bounded-depth algorithms, and derive applications including direct-product theorems, salting against non-uniform adversaries, and hardness bounds for multi-image inversion, multi-collision finding, multi-search, and 3SUM. The framework is intended to reduce NISQ security to the computation of a single classical quantity p(R).","tokens_in":34868,"tokens_out":5546,"duration_ms":70069,"significance":"If the main theorem and its proof were correct, this would be a substantial contribution: it would provide the first general hybrid lifting theorem, a unified technique for deriving NISQ hardness across many search games, and a direct-product theorem for hybrid adversaries. The claimed reduction of security to a simple combinatorial quantity p(R) is attractive and would extend the recent coherent measure-and-reprogram approach of [CGLS25] to a practically motivated model. The paper also gives optimality claims for multi-image search, which would demonstrate tightness of the framework. However, the proof of the central theorem contains a load-bearing orthogonality assertion that is not justified and is in fact false under the paper's own definitions, and there is a clear counting inconsistency between the simulator definition and the probability computations. These issues prevent the current manuscript from establishing its main results.","major_comments":[{"comment":"The orthogonality assertion in Eq. (6) is not correct. The history register records (x, H(x)) for non-reprogrammed classical queries and (x, G(x)) for reprogrammed ones. For x in the reprogrammed set \\vec{x}_o, however, H^{\\vec{x}_o,\\vec{y}_o}(x) = G(x) by construction, so the recorded pairs coincide. Since the final projection fixes the output to \\vec{x}_o, the relevant classical query inputs are in \\vec{x}_o, making the two histories indistinguishable in general. Consequently Eq. (7) does not follow; cross terms may introduce an additional combinatorial factor proportional to the number of classical reprogramming choices, potentially invalidating the claimed O(q^2/k^2 + c/k)^k loss.","section":"Section 3.2, Eq. (6)"},{"comment":"There is a counting mismatch. Definition 3.3 samples the reprogramming positions v from [c+q+k], including the k final 'typing' queries, so the number of choices with exactly t quantum positions is (q choose t)(c+k choose k-t). Lemma 3.7 instead uses (q choose t)(c choose k-t). This discrepancy affects the normalization in the definition of a_t (Definition 3.8) and the final loss factor. It is not a cosmetic issue: the theorem statement's A_{k,q,c} may correspond to a different sampling procedure than the one actually analyzed.","section":"Lemma 3.7 vs. Definition 3.3"},{"comment":"The proof is a sketch and delegates the central state decomposition to the proof of Theorem 6 in [CGLS25], which is not reproduced. The hybrid adaptation—especially the treatment of the final k classical queries and the claim that one can 'measure-and-(immediately)-reprogram exactly k-l locations of the last k queries'—is asserted without derivation. Given that the entire theorem rests on this decomposition, the referee cannot verify that the stated constants (e.g., the factor k and the binomial coefficients) are correct.","section":"Proof of Lemma 3.6"},{"comment":"The paper states the main theorem only for static hybrid algorithms (where the order of classical and quantum queries is fixed) and says the general adaptive case follows from [DFH22] with a factor-2 loss. Since several applications are phrased for arbitrary hybrid algorithms, this extension is load-bearing, but no proof is given and the exact way [DFH22] applies to the present simulator is not specified.","section":"Remark 3.2"}],"minor_comments":[{"comment":"The informal Theorem 1.1 says 'k (quantum + classical) hybrid query adversary' but it is not immediately clear whether the simulator's k queries include both types; the formal Theorem 3.1 clarifies that Sim makes exactly k queries to G, but the informal phrasing could be tightened.","section":"Abstract / Introduction"},{"comment":"The condition '1 < v_1 < ... < v_k <= c+q+k' appears to have a typo: the lower bound should likely be 1, not 1 < v_1, and the ordering should be non-decreasing or strictly increasing depending on whether duplicate positions are allowed.","section":"Definition 3.3, step 2"},{"comment":"The proof of optimality shows an upper bound on A_{k,q,c} but the matching lower bound is only argued for constant k. The claim for general k would benefit from a more explicit comparison of constants.","section":"Section 3.5, Lemma 3.11"},{"comment":"The factor 1/2^k in Lemma 3.7 seems to be lost in the displayed equation after substitution of a_t; the final expression in the proof of Theorem 3.1 should be checked for consistency of the powers of 2.","section":"Equation (9)"}],"recommendation":"reject","confidential_remarks":"The manuscript has a promising high-level idea and the applications are relevant, but the main theorem's proof appears to contain a false orthogonality claim and a counting inconsistency. These are not minor presentation issues; they affect the core lifting bound. Unless the authors can supply a corrected proof—which may require a substantially different argument—the paper cannot be accepted in its current form. The heavy reliance on [CGLS25] for the key decomposition also makes the proof difficult to verify."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this is a useful lifting framework for NISQ security, and if the central theorem is right it will save a lot of ad-hoc analysis. But the core proof has a real gap that the authors need to close before the result is proven as stated.\n\nWhat's genuinely new: a hybrid coherent measure-and-reprogram theorem that handles algorithms issuing both quantum and classical queries, with a loss factor O(q^2/k^2 + c/k)^k. It gives the first hybrid direct product theorem in the average case and a clean way to get hardness for multi-image inversion, multi-collision, 3SUM, salting, and non-uniform adversaries. The applications are essentially direct consequences of computing a single combinatorial quantity p(R). That is a significant modularity improvement over prior work like [HLS24] and [CGS23], which were tailored to specific problems.\n\nWhere I have concerns. The stress-test is right: Eq. (6) is not an identity for arbitrary H,G. The history register only distinguishes two classic reprogramming schedules when the oracle value at the reprogrammed point differs from the original value. If G(x)=H(x), the branches have identical histories, so the claimed orthogonality fails. Since the theorem is stated for all H,G, the proof as written does not go through. The fix is probably to work with random H,G, show the bad event has small probability, and absorb that into the constant—but that needs to be done explicitly. As it stands, the claimed bound is not justified.\n\nOther soft spots: Section 3.2 is a sketch leaning heavily on [CGLS25], which makes it hard to verify the state decomposition independently; the noisy-oracle result is explicitly non-tight away from the endpoints p=0,1 (they acknowledge this, but it limits the result's usefulness); and there is a minor counting inconsistency in Lemma 3.7 about whether the final k classical queries are included in the reprogramming locations, which affects the loss factor.\n\nWho should read this: anyone working on QROM lifting theorems, hybrid quantum-classical security, or NISQ hardness. It's a good paper to bring to a reading group because the high-level idea is clean and there is a substantive technical gap to discuss.\n\nRecommendation: this deserves a serious referee. I would not accept it in its current form—the Eq. (6) gap is load-bearing—but with that fixed and the proof expanded, it should be a strong paper.","headline":"A genuinely useful lifting framework for hybrid NISQ security, but the central orthogonality claim (Eq. 6) has a real gap that needs fixing before the result is proven as stated.","tokens_in":35348,"tokens_out":7813,"would_cite":true,"duration_ms":81643,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P94","94A60"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims a single hybrid lifting theorem: any hybrid (q quantum, c classical) adversary against a k-query classical challenger implies a k-query adversary whose success is at least Pr[A] / O(q^2/k^2 + c/k)^k.","keywords":["hybrid algorithms","lifting theorem","quantum random oracle model","measure-and-reprogram","NISQ","direct product theorem","query complexity","cryptographic hardness"],"falsifier":"Take a small explicit hybrid algorithm (say k=2, q=1, c=2) for a 2-image search, implement the two decomposed states corresponding to two different classical reprogramming schedules, and compute their inner product: a nonzero value would violate the orthogonality asserted in the proof's inequality (6) and invalidate the bound.","tokens_in":34443,"feed_emoji":"🔐","tokens_out":4122,"duration_ms":43578,"temperature":0.7,"pith_summary":"The paper's central claim is a lifting theorem for security games in which an attacker may mix quantum and classical random-oracle queries. It proves that any hybrid attacker with q quantum and c classical queries that wins a game against a k-query classical challenger with probability epsilon can be converted into a k-query attacker winning with probability at least epsilon / O(q^2/k^2 + c/k)^k. The technical engine is a 'hybrid coherent measure-and-reprogram' simulator that reprograms up to k oracle answers while controlling when measurements and reprogrammings occur, losing only a combinatorial factor A_{k,q,c}. From this one theorem, the paper derives direct product theorems and hybrid hardness for multi-image inversion, multi-collision, multi-search, salted games, and 3SUM. A sympathetic reader would care because it turns NISQ security analysis into one classical combinatorial calculation.","feed_headline":"Hybrid quantum-classical attacks collapse to tiny-query attacks","feed_subtitle":"A single combinatorial count bounds NISQ hash hardness, from multi-collision to salted games.","key_machinery":"The central object is the hybrid coherent measure-and-reprogram experiment: a simulator runs the hybrid algorithm while choosing k query positions, deciding for each whether to measure-and-reprogram before or after the query, and using a control/history register to track (x, G(x)) pairs. The key identity is the combinatorial sum A_{k,q,c} = sum_t (q choose t)^2 (k choose t)(c choose k-t), bounded by O(q^2/k^2 + c/k)^k; it quantifies the probability that the simulator picks exactly t quantum queries to reprogram. The simulator's success probability is inversely proportional to A_{k,q,c}, and this single quantity becomes the universal loss for all applications.","core_discovery":"The core discovery is a hybrid coherent measure-and-reprogram theorem. For any static hybrid algorithm making q quantum and c classical queries to an oracle, and any k-point reprogramming of that oracle, there is a simulator that makes only k queries to a second random oracle and reproduces the algorithm's success with probability at least 1/(2^{2k} k A_{k,q,c}) of the original, where A_{k,q,c} = sum_t (q choose t)^2 (k choose t)(c choose k-t) simplifies to O(q^2/k^2 + c/k)^k. From this, the lifting theorem follows: any hybrid adversary against a k-query classical challenger can be replaced by a k-query adversary with the stated loss. The authors then show the bound is optimal for multi-imag","pith_inferences":["The same simulator template could be adapted to prove lifting for interactive protocols where the challenger itself makes quantum queries, extending the framework beyond classical-challenger games.","The bound suggests the natural hybrid resource is q^2 + c; protocols could be parameterized on this combined quantity, and practical NISQ experiments might test whether attack success follows this trade-off.","For noisy oracles the authors note non-tightness at constant p; a concrete open test is whether explicit function inversion matches O(T^2/N) or the classical O(T/N), indicating where the lifting bound loses.","One could apply the framework to new games by computing p(R) alone and reading off hybrid hardness without further analysis, for relations defined by linear statistics or other permutation-invariant image predicates."],"forward_implications":["If a search game is hard for any k-query hybrid adversary, then it is hard for arbitrary hybrid adversaries up to the loss factor O(q^2/k^2 + c/k)^k.","The hybrid direct product theorem implies that solving g independent instances with g q quantum and g c classical queries has success at most [O(q^2/k^2 + c/k)^k p(R)]^g, enabling multi-instance hardness.","Non-uniform hybrid adversaries with S bits of classical advice are bounded by O((S^2 q^2/k^2 + S c/k))^{k/S} p(R^{⊗S})^{1/S}.","Salting defeats preprocessing: salted games become 4S/K + O(q^2/k^2 + c/k)^k p(R) secure against hybrid adversaries with S bits of advice.","The framework yields upper bounds for multi-image inversion (tight), multi-collision, multi-search, and 3SUM in the hybrid query model."],"fun_headline_variants":["Hybrid attacks reduced to k-query simulators","Lifting theorems for hybrid quantum-classical oracles","One combinatorial count for NISQ hardness","Measure-and-reprogram tames hybrid adversaries","Direct-product theorems in the hybrid setting"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof relies on the states generated by different choices of which classical queries to reprogram being exactly orthogonal as recorded in the history register; if that orthogonality fails for any algorithm, the Cauchy-Schwarz step that produces the main bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Hybrid attacks reduced to k-query simulators","Lifting theorems for hybrid quantum-classical oracles","One combinatorial count for NISQ hardness","Measure-and-reprogram tames hybrid adversaries","Direct-product theorems in the hybrid setting"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000182,"raw_usage":{"total_tokens":1168,"prompt_tokens":785,"completion_tokens":383,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":529,"completion_tokens_details":{"reasoning_tokens":324}},"tokens_in":529,"tokens_out":383,"duration_ms":4519,"temperature":1.0,"reasoning_tokens":324,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T18:29:25.592011+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a small explicit hybrid algorithm (say k=2, q=1, c=2) for a 2-image search, implement the two decomposed states corresponding to two different classical reprogramming schedules, and compute their inner product: a nonzero value would violate the orthogonality asserted in the proof's inequality (6) and invalidate the bound.","supporting_citations":[],"review_version":1}