{"id":"0bfd5229-3a42-489d-b2f1-52e132c60218","arxiv_id":"2605.24798","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Quantum rejection sampling applied to truncated Klein proposals yields quadratic speedup in dual-attack lattice Gaussian sampling, cutting Kyber attack costs by 9, 4, and 13 bits.","lead":"The paper shows how to use quantum rejection sampling together with an existing lower bound on Klein's algorithm to prepare truncated lattice Gaussians with quadratic fewer queries. If correct, this lowers the estimated quantum attack cost on Kyber by 4-13 bits and speeds up GPV trapdoor sampling.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.3","headline":"Wang-Ling lower bound may not supply the exact pointwise domination ratio required by Ozols QRS under coherent truncated-Klein oracle access","rationale":"The reader's weakest_assumption isolates exactly the step that converts the classical lower bound into a quantum query reduction. Because the full manuscript is now available, the concrete_test above directly audits that step rather than the abstract claim. If the domination holds, the remainder of the cost estimates can be accepted; if not, the headline savings are unsupported. This is therefore the single load-bearing assumption.","tokens_in":1757,"tokens_out":386,"duration_ms":17436,"concrete_test":"Extract the explicit lower-bound expression from Wang-Ling §4 (or wherever the Klein analysis appears), substitute the truncated Klein density with the paper's chosen radius R, and check whether the resulting ratio is everywhere ≥ the target dual Gaussian density on the support; if the inequality fails at any lattice point inside the truncation ball, recompute the QRS acceptance probability and the resulting attack-cost table.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central speedup rests on the claim that the lower bound derived in Wang-Ling (for classical Klein) supplies precisely the function f such that the truncated Klein proposal q satisfies q(x) ≤ f(x)·target(x) pointwise, which is the domination condition needed to invoke the Ozols et al. QRS theorem with a coherent oracle for the proposal. The paper states this equivalence directly but does not exhibit the explicit domination function or verify that the truncation radius chosen for TV-negligibility preserves the inequality inside the support. If the bound is only an average-case or asymptotic statement, or if coherent access introduces phase or normalization mismatches not present in the classical analysis, the quadratic query reduction does not follow and the reported 9/4/13-bit savings disappear.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims that the lower bound underlying Wang and Ling's analysis of Klein's algorithm supplies exactly the pointwise domination function needed to apply Ozols et al.'s quantum rejection sampling to a coherent oracle for the truncated Klein proposal distribution. This is asserted to yield a quadratic reduction in the query complexity of preparing truncated dual q-ary lattice Gaussians (with truncation radius chosen for negligible total-variation distance to the target). Substituting the resulting sampler into the dual-attack framework produces concrete attack-cost reductions of 9, 4, and 13 bits versus Pouly-Shen for Kyber-512/768/1024 (with and without modulus switching); an analogous quadratic speedup is claimed for GPV signing by replacing the MCMC sampler.","tokens_in":1949,"tokens_out":519,"duration_ms":22660,"significance":"If the claimed exact pointwise domination holds under coherent access and truncation, the work would supply a concrete quantum improvement to a core primitive in lattice-based cryptanalysis and signature generation, directly lowering bit-security estimates for standardized Kyber parameters and thereby affecting concrete security assessments in post-quantum cryptography.","major_comments":[{"comment":"Abstract and the section describing the QRS application: the central claim that the Wang-Ling lower bound 'gives precisely the pointwise domination condition' for the truncated Klein proposal is stated without exhibiting the explicit domination function f or deriving that q(x) ≤ f(x)·target(x) holds pointwise inside the truncation support when the oracle is coherent. This equivalence is load-bearing for the quadratic query reduction and the reported 9/4/13-bit savings; an average-case or asymptotic bound would not suffice.","section":"Abstract"},{"comment":"The paragraph on truncation radius and total-variation closeness: no explicit error analysis or verification is supplied showing that the chosen radius preserves the domination inequality inside the support while keeping TV distance negligible; coherent-access normalization or phase issues are not addressed.","section":"Section on truncation and TV distance"}],"minor_comments":[{"comment":"Notation for the truncated proposal distribution and the coherent oracle could be introduced earlier and used consistently when invoking the Ozols QRS theorem.","section":null}],"recommendation":"major_revision","confidential_remarks":"The manuscript's novelty rests almost entirely on the asserted interface between two external results; the absence of an explicit domination derivation makes the contribution appear thinner than the abstract suggests. This is a scope-fit concern for a theory journal."},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their careful reading and constructive comments, which highlight areas where the presentation of our central claims can be strengthened. We address each major comment below and will revise the manuscript accordingly.","responses":[{"response":"We agree that the manuscript states the equivalence without an explicit pointwise derivation of the domination function or verification of q(x) ≤ f(x)·target(x) for the coherent truncated proposal. In the revised version we will add a dedicated subsection that extracts the explicit domination function f from the Wang-Ling lower bound and proves the required pointwise inequality holds inside the truncation support under coherent oracle access. This will make the application of Ozols et al.'s framework fully rigorous and self-contained.","revision_made":"yes","referee_comment":"[Abstract] Abstract and the section describing the QRS application: the central claim that the Wang-Ling lower bound 'gives precisely the pointwise domination condition' for the truncated Klein proposal is stated without exhibiting the explicit domination function f or deriving that q(x) ≤ f(x)·target(x) holds pointwise inside the truncation support when the oracle is coherent. This equivalence is load-bearing for the quadratic query reduction and the reported 9/4/13-bit savings; an average-case or asymptotic bound would not suffice."},{"response":"The current manuscript selects the truncation radius to achieve negligible total-variation distance but does not supply a detailed error analysis confirming that the domination inequality survives truncation, nor does it discuss coherent-access normalization or phase considerations. We will insert an explicit analysis in the revision that (i) bounds the truncation error while preserving the pointwise domination, (ii) quantifies the resulting TV distance, and (iii) explains how the coherent oracle is normalized and how phase factors are handled within the QRS procedure.","revision_made":"yes","referee_comment":"[Section on truncation and TV distance] The paragraph on truncation radius and total-variation closeness: no explicit error analysis or verification is supplied showing that the chosen radius preserves the domination inequality inside the support while keeping TV distance negligible; coherent-access normalization or phase issues are not addressed."}],"tokens_in":1447,"tokens_out":462,"duration_ms":27673,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The core claim is that Wang and Ling's lower bound on Klein sampling supplies the exact domination function needed to run Ozols quantum rejection sampling on a truncated Klein proposal, cutting the dominant sampling cost by a quadratic factor. Plugging the resulting sampler into the dual attack then lowers the estimated costs by 9, 4, and 13 bits for Kyber-512/768/1024 versus Pouly-Shen. They also swap the same sampler into GPV signing and claim a similar speedup.\n\nThe new material is the concrete bit counts for the three Kyber sets under this hybrid sampler; those numbers are not in the cited prior papers. The move itself is a direct application of two existing results once the domination condition is noticed, so the technical lift is modest but the security-estimate consequence is not.\n\nThe soft spot is the domination step. The abstract states that the lower bound \"gives precisely the pointwise domination condition\" for the truncated distribution under coherent oracle access, yet supplies no explicit function, no verification that the chosen truncation radius keeps the inequality inside the support, and no check for phase or normalization issues that coherent access might introduce. If the bound is only average-case or asymptotic, the quadratic saving and the reported bit reductions do not follow. That gap is load-bearing.\n\nThe work is aimed at people who track concrete security of lattice schemes and need updated attack costs for parameter selection. A reader who already knows the Wang-Ling and Ozols papers can extract the new numbers quickly, but will still have to re-derive the domination claim to trust them.\n\nSend it to peer review. The potential effect on Kyber estimates is large enough to justify referee time even if the central justification needs tightening.","headline":"The paper gets 9/4/13-bit reductions on Kyber dual attacks by matching Wang-Ling's Klein lower bound to Ozols QRS domination, but the exact pointwise match under truncation and coherent access is asserted rather than derived.","tokens_in":2404,"tokens_out":444,"would_cite":false,"duration_ms":24367,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Quantum rejection sampling quadratically accelerates lattice Gaussian sampling for dual attacks, cutting estimated costs on Kyber parameters by 9, 4, and 13 bits.","keywords":["quantum rejection sampling","dual attack","lattice Gaussian sampling","Kyber","GPV trapdoor sampling","Klein's algorithm","post-quantum cryptography","quantum algorithms"],"falsifier":"An explicit computation or numerical check showing that, for the chosen truncation radius, the total variation distance between the truncated and full lattice Gaussian exceeds a negligible bound, or that the domination inequality fails to hold pointwise for the Klein proposal.","tokens_in":2664,"feed_emoji":"⚛️","tokens_out":741,"duration_ms":22108,"temperature":0.7,"pith_summary":"The paper focuses on the lattice Gaussian sampling step that often dominates the cost of dual attacks against schemes like Kyber. It combines the lower bound from Wang and Ling's analysis of Klein's algorithm with the quantum rejection sampling framework to obtain a quantum procedure that prepares the required truncated dual q-ary lattice Gaussian distribution. Because the lower bound supplies the exact pointwise domination condition needed for rejection sampling under coherent oracle access, the procedure achieves a quadratic reduction in sampling complexity while keeping total variation distance to the full Gaussian negligible. Substituting the new sampler into the dual attack framework produces lower overall attack-cost estimates than those obtained from Pouly and Shen's modern classical attack under identical parameters. The same replacement also yields a quadratic speedup when applied to the GPV trapdoor sampling used in signature generation.","feed_headline":"Quantum sampler reduces Kyber dual attack cost by up to 13 bits","feed_subtitle":"Combining quantum rejection sampling with Klein's algorithm analysis produces a quadratic speedup in the lattice sampling step that dominate","key_machinery":"Quantum rejection sampling applied to a truncated Klein proposal distribution under coherent oracle access, using the pointwise domination condition from Wang and Ling's analysis of Klein's algorithm.","core_discovery":"The authors show that the domination condition supplied by the lower bound on Klein's algorithm is precisely what quantum rejection sampling requires when given coherent access to a truncated Klein proposal; this yields a quantum algorithm for the truncated dual q-ary lattice Gaussian whose query complexity is quadratically smaller than the classical sampler, with the truncation radius chosen so the output remains negligibly close in total variation distance to the ideal lattice Gaussian.","pith_inferences":["The same domination-plus-rejection technique could be tested on other classical samplers whose analysis already supplies a suitable lower bound.","If the quadratic saving persists across a wider range of lattice dimensions, security estimates for other module-lattice and ideal-lattice schemes would require similar downward adjustment.","Implementation of the coherent oracle access model on near-term quantum hardware would provide a direct test of whether the predicted sampling speedup materializes in practice."],"forward_implications":["Attack cost estimates drop by 9 bits for Kyber-512, 4 bits for Kyber-768, and 13 bits for Kyber-1024 relative to Pouly and Shen's attack under the same parameters.","Corresponding cost reductions hold when modulus switching is also applied.","Replacing the MCMC sampler with the QRS algorithm produces a quadratic speedup in the GPV signing procedure."],"fun_headline_variants":["Quantum rejection sampling quadratically accelerates Kyber dual attacks","Lower bound on Klein enables quantum quadratic speedup for Kyber","QRS quadratic speedup cuts Kyber attack costs by 4-13 bits","Quantum Gaussian sampling reduces dual attack complexity for Kyber"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The lower bound from Wang and Ling's analysis of Klein's algorithm supplies exactly the pointwise domination condition that quantum rejection sampling needs for the truncated proposal distribution.","fun_headline_variants_meta":{"raw":{"variants":["Quantum rejection sampling quadratically accelerates Kyber dual attacks","Lower bound on Klein enables quantum quadratic speedup for Kyber","QRS quadratic speedup cuts Kyber attack costs by 4-13 bits","Quantum Gaussian sampling reduces dual attack complexity for Kyber"]},"model":"grok-4.3","cost_usd":0.00706,"raw_usage":{"total_tokens":3280,"prompt_tokens":697,"num_sources_used":0,"completion_tokens":67,"cost_in_usd_ticks":70599500,"prompt_tokens_details":{"text_tokens":697,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2516,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":697,"tokens_out":67,"duration_ms":23800,"temperature":1.0,"reasoning_tokens":2516,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-30T01:24:58.407976+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit computation or numerical check showing that, for the chosen truncation radius, the total variation distance between the truncated and full lattice Gaussian exceeds a negligible bound, or that the domination inequality fails to hold pointwise for the Klein proposal.","supporting_citations":[],"review_version":1}