{"id":"6f2a3527-c5a2-4dfc-8321-10cb538795f1","arxiv_id":"2607.05973","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":5.5,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A constructive QUBO encoding of small MLWE instances jointly recovers secret and error, with a convex-polytope stability analysis and scaling estimates for quantum annealing.","lead":"This paper encodes small Module Learning With Errors (MLWE) instances as QUBO problems so quantum annealers can try to recover both the secret and the error. It also maps when that recovery stays stable under noise and how the formulation scales, without claiming a break of real post-quantum crypto.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"Modular arithmetic and penalty scaling in the joint secret/error QUBO encoding can create spurious low-energy states that break uniqueness of the planted ground state and invalidate the claimed polytope–energy-gap equivalence under additive noise.","rationale":"The Reader correctly isolated the encoding-plus-additive-noise assumption as the weakest link and left the paper UNVERDICTED because the full text was unavailable. With the manuscript now in view, that same assumption remains load-bearing, but the concrete failure mode is sharper: the interaction of modular-penalty scaling with the residual objective can silently introduce spurious minima that neither the polytope geometry nor the energy-gap equivalence accounts for. Low-dimensional exact recovery does not rule the failure out; it only shows that a carefully chosen penalty worked for those particular parameters. Hence the verdict should move from UNVERDICTED to CONDITIONAL—acceptance of the methodological framing and the geometric analysis is warranted only after the modular-penalty regime is shown not to disturb uniqueness or the gap characterization. The paper’s careful disclaimer that no cryptographically relevant parameters are threatened is unaffected.","tokens_in":2122,"tokens_out":686,"duration_ms":38904,"concrete_test":"Take the smallest benchmark instance reported in the numerical section. Reconstruct the full QUBO matrix (including all penalty terms for modular reductions and binary expansions). Exhaustively enumerate (or exact-solve) the energy landscape; verify that the unique ground state is the planted (s,e) and record the gap ΔE to the second-best feasible state. Then inject a modular competitor s′ = s + q·u for a short vector u and confirm its energy lies strictly above the planted energy by at least ΔE. Finally recompute the same landscape after a 10 % relative detuning of the penalty coefficients; if either uniqueness or the gap–polytope correspondence collapses, the encoding does not support the claimed stability characterization.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim rests on a constructive QUBO whose ground state is exactly the true (secret, discretized-error) pair for small MLWE instances, with the admissible additive-noise region forming a convex polytope of competing secrets that is equivalent to the energy gap to the second-best solution. Realizing the MLWE residual (b − A s − e ≡ 0 mod q, or the ring analogue) inside a pure quadratic binary objective requires binary expansions of all coefficients plus auxiliary variables that absorb integer multiples of the modulus. Those equalities are enforced by penalty terms whose coefficients must dominate the residual objective. If the penalties are under-scaled, modular wrap-arounds or invalid expansions become lower-energy than the planted solution; if over-scaled, they flatten or distort the very energy gaps that the stability analysis equates to the geometric polytope. The abstract’s low-dimensional exact simulations can mask the problem when q and the error range are tiny enough that a hand-tuned penalty works, yet the general equivalence between polytope and gap (and therefore the robustness claims) holds only when the unconstrained residual landscape is faithfully preserved—an assumption left unproven by the existence of successful recovery on a few toy instances. This is the single point at which the joint-recovery and stability results stand or fall.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.5","summary":"The manuscript proposes a constructive QUBO encoding of small Module-LWE instances that jointly represents secret coefficients and explicit (discretized) error variables as binary decision variables, so that both are recovered from the ground-state solution of a single quadratic objective. It then develops a stability analysis of the resulting landscape under additive perturbations: the admissible noise region is characterized as a convex polytope defined by competing candidate secrets, and this region is shown to be equivalent to the energy gap between the optimal and second-best QUBO solutions. Low-dimensional exact simulations are reported to recover planted secrets and errors and to confirm consistency between the geometric polytope and the energy-gap description. The paper also quantifies growth of logical variables and minor-embedding overhead with MLWE dimension, while explicitly disclaiming any practical cryptanalytic threat to standardized post-quantum parameters.","tokens_in":2407,"tokens_out":1262,"duration_ms":36801,"significance":"If the joint encoding is faithful (true (secret, error) pair is exactly the unique unconstrained ground state) and the polytope–gap equivalence survives the modular and penalty structure required by MLWE, the work supplies a systematic bridge between lattice-based hardness assumptions and quantum-annealing landscapes, together with a concrete geometric robustness criterion. The simultaneous recovery of secret and error, the convex-polytope stability characterization, and the explicit scaling/embedding accounting are genuine contributions beyond a bare encoding recipe. The manuscript is appropriately cautious about hardware reach and cryptographic impact. Validation rests on exact low-dimensional simulation rather than machine-checked proofs or large-scale annealer runs; free parameters (binary width, error alphabet, penalty scales) remain part of the modeling choice and must be controlled for the claims to transfer.","major_comments":[{"comment":"The central uniqueness and stability claims require that the modular residual (b − As − e ≡ 0 mod q, or the ring analogue) be realized inside a pure quadratic binary objective without introducing spurious lower-energy states. Realizing modular wrap-around and integer coefficient expansions typically demands auxiliary slack variables and penalty terms whose coefficients must dominate the residual objective. The manuscript must state explicitly (construction section / QUBO objective) the precise penalty schedule used, prove or bound that the planted (secret, discretized-error) pair remains the unique ground state for that schedule, and show that the same schedule does not flatten or reorder the energy gaps that the stability analysis equates to the geometric polytope. Low-dimensional exact recovery alone does not establish this for general q and error bounds; if the equivalence is only sho","section":null},{"comment":"Stability analysis (polytope defined by competing candidate secrets; equivalence to optimal-to-second-best energy gap): clarify whether the competing candidates are taken over the full feasible binary encoding (including invalid expansions and modular images) or only over valid secret/error pairs. If the former, the polytope description must incorporate the penalty-induced barriers; if the latter, the claimed equivalence holds only after the encoding constraints have already been enforced, which again depends on the penalty regime. A concrete statement of the feasible set over which the second-best solution is defined is needed for the equivalence to be load-bearing.","section":null},{"comment":"Error discretization and coefficient bounds appear as free modeling parameters. The recovery and uniqueness claims are stated for the discretized alphabet used in the experiments. The manuscript should make precise the conditions under which the true continuous (or larger-alphabet) error remains the unique ground state after discretization, and whether the polytope/gap characterization is invariant under refinement of the error alphabet. Without this, the joint-recovery result is tied to the particular discretization chosen for the toy instances.","section":null},{"comment":"Scaling and embedding-overhead quantification: report whether the growth figures are purely combinatorial (logical qubits vs. dimension/modulus/error range) or include measured chain-strength and success-probability effects under minor embedding. If only logical counts are given, the feasibility assessment for annealing architectures is incomplete; if embedding statistics are included, state the annealer model and chain-break handling so that the overhead numbers can be reproduced.","section":null}],"minor_comments":[{"comment":"Abstract and introduction correctly disclaim practical cryptanalytic impact; ensure the same disclaimer appears near the scaling discussion so that variable-count growth is not misread as a near-term attack path.","section":null},{"comment":"Notation for the module rank, ring degree, and modulus q should be fixed early and used consistently when stating both the MLWE instance and the QUBO variable counts.","section":null},{"comment":"When reporting exact-simulation recovery, give the precise (n, k, q, error bound) tuples and the number of random planted instances so that the success claim is auditable.","section":null},{"comment":"Figures comparing geometric stability regions to energy-gap behavior would benefit from an explicit overlay or distance metric rather than qualitative visual agreement alone.","section":null},{"comment":"Related-work placement of prior LWE/Ising or LWE/QUBO encodings should note which earlier formulations recover only the secret versus joint secret-and-error, to sharpen the novelty claim.","section":null}],"recommendation":"major_revision","confidential_remarks":"The load-bearing technical risk is the interaction of modular penalties with the claimed polytope–gap equivalence; if the authors can supply a clean dominance argument or an explicit regime in which the residual landscape is faithfully preserved, the paper becomes a solid methods contribution. Scope is appropriate for a quantum-optimization / PQC-interface venue; it is not a cryptanalysis paper and should not be evaluated as one. I have only the abstract plus the supplied reader/skeptic notes in this session; the major comments above are framed so they can be checked directly against the construction and stability sections of the full text."},"author_rebuttal":{"model":"grok-4.5","summary":"We thank the referee for a careful and constructive report. The four major comments correctly identify where the manuscript must be more explicit about the penalty regime that realizes modular residuals, the feasible set underlying the polytope–gap equivalence, the status of error discretization, and the precise content of the scaling/embedding figures. We agree that these points are load-bearing for the uniqueness and stability claims and will revise the construction, theory, and experimental sections accordingly. Below we answer each comment point by point, stating what will change in the next version and where our present results already supply (or do not yet supply) the requested guarantees. We do not claim a practical attack on standardized MLWE parameters; the revisions aim only to make the modeling and stability statements rigorous for the small instances we study.","responses":[{"response":"We agree that the uniqueness claim is incomplete without an explicit penalty schedule and a supporting bound. In the revised construction section we will write the full QUBO objective with the modular residual expanded via binary (or one-hot) coefficient encodings and the standard quadratic penalty terms for equality constraints and for out-of-range expansions, and we will state the concrete coefficient hierarchy used in all experiments (residual weight, modular-slack penalties, and validity penalties). We will add a sufficient-condition lemma: if the penalty coefficients dominate the residual objective by a factor depending on q and the bit-widths of secret and error, then every infeasible binary string has energy strictly above the planted feasible pair, so the unconstrained ground state coincides with the planted (secret, discretized-error) pair. We will also verify, for the same schedule, that the optimal-to-second-best gap among feasible solutions is unchanged by the penalties (penalties only lift infeasible states), which is the regime in which our polytope–gap equivalence is claimed. We do not claim a parameter-free uniqueness proof for arbitrary q and unbounded error alphabets; the lemma will give explicit sufficient ranges, and we will note that outside those ranges uniqueness must be checked instance-wise. Low-dimensional exact recovery will be retained as numerical confirmation inside the proven regime, not as a substitute for the bound.","revision_made":"yes","referee_comment":"The central uniqueness and stability claims require that the modular residual be realized inside a pure quadratic binary objective without introducing spurious lower-energy states. The manuscript must state explicitly the precise penalty schedule used, prove or bound that the planted (secret, discretized-error) pair remains the unique ground state for that schedule, and show that the same schedule does not flatten or reorder the energy gaps that the stability analysis equates to the geometric polytope. Low-dimensional exact recovery alone does not establish this for general q and error bounds."},{"response":"The referee is right that the feasible set was not stated sharply enough. In the manuscript the geometric polytope is defined by competing candidate secrets (and their associated residual-minimizing discretized errors) that are valid under the chosen binary expansions and that satisfy the modular equation after decoding; invalid expansions and modular images are not vertices of that polytope. The energy-gap side of the equivalence is likewise the gap between the optimal and second-best solutions restricted to the feasible set after the encoding constraints are enforced. Under the penalty schedule of the revised construction (Comment 1), infeasible strings lie strictly above this gap, so the unconstrained QUBO second-best coincides with the second-best feasible solution and the polytope–gap equivalence is load-bearing. We will add an explicit definition of the feasible set F (valid secret/error bit-strings whose decoded residual is 0 mod q), restate the polytope as the set of additive perturbations that preserve the ordering of energies over F, and state the equivalence theorem only for the second-best element of F. We will also note that if penalties are set too weakly, spurious infeasible minima can appear and the geometric description no longer matches the unconstrained landscape; that failure mode is excluded by the sufficient conditions of Comment 1.","revision_made":"yes","referee_comment":"Stability analysis (polytope defined by competing candidate secrets; equivalence to optimal-to-second-best energy gap): clarify whether the competing candidates are taken over the full feasible binary encoding (including invalid expansions and modular images) or only over valid secret/error pairs. If the former, the polytope description must incorporate the penalty-induced barriers; if the latter, the claimed equivalence holds only after the encoding constraints have already been enforced. A concrete statement of the feasible set over which the second-best solution is defined is needed."},{"response":"We agree that discretization is a modeling choice and that the joint-recovery claim must be scoped to it. The QUBO recovers the planted secret together with the discretized error that was encoded; it does not automatically recover a continuous or finer-alphabet error unless that error lies in the chosen alphabet (or is the unique nearest representative under the residual objective). In the revision we will (i) state the error alphabet E and coefficient bounds as part of the instance definition, (ii) give the elementary condition that if the true error e* belongs to E and the residual objective plus penalties make (s*,e*) the unique minimizer over valid pairs, then the ground state recovers e* exactly, and (iii) note that refining E (e.g., finer quantization of a continuous error) enlarges the variable set and can only shrink or preserve the stability polytope relative to the coarser alphabet, so the polytope/gap characterization is not automatically invariant under refinement. When the true error lies outside E, recovery is of the best residual-minimizing representative in E; we will state this limitation clearly and restrict the uniqueness theorems to the discretized problem actually solved. The experimental section will list the alphabets used and will not claim continuous-error recovery beyond those alphabets.","revision_made":"yes","referee_comment":"Error discretization and coefficient bounds appear as free modeling parameters. The recovery and uniqueness claims are stated for the discretized alphabet used in the experiments. The manuscript should make precise the conditions under which the true continuous (or larger-alphabet) error remains the unique ground state after discretization, and whether the polytope/gap characterization is invariant under refinement of the error alphabet."},{"response":"The growth figures in the present manuscript are combinatorial: counts of logical binary variables as functions of module rank, dimension, modulus bit-width, and error-alphabet size, together with standard minor-embedding overhead estimates (chain-length / physical-qubit upper bounds) obtained from the connectivity pattern of the QUBO graph, not from hardware runs that measure chain strength or success probability. We did not report annealer-model-specific chain-break statistics or empirical success rates, and the recovery experiments themselves use exact classical simulation of the QUBO, not a physical annealer. We will revise the scaling section to state this scope explicitly, separate logical-variable scaling from embedding-overhead estimates, and label the latter as graph-theoretic upper bounds rather than measured hardware overhead. We will not add unsubstantiated success-probability claims. If space permits we will include a short note on how chain-strength heuristics would enter a hardware study, while reiterating that current annealers remain far from cryptographically relevant MLWE sizes—the same disclaimer already present in the abstract and conclusion.","revision_made":"yes","referee_comment":"Scaling and embedding-overhead quantification: report whether the growth figures are purely combinatorial (logical qubits vs. dimension/modulus/error range) or include measured chain-strength and success-probability effects under minor embedding. If only logical counts are given, the feasibility assessment for annealing architectures is incomplete; if embedding statistics are included, state the annealer model and chain-break handling so that the overhead numbers can be reproduced."}],"tokens_in":2058,"tokens_out":1672,"duration_ms":32272,"standing_objections":[]},"desk_editor":{"model":"grok-4.5","letter":"Punchline: this is a methodological QUBO paper for small MLWE, not a cryptanalysis result. The useful pieces are a joint secret-plus-error encoding and a stability story that ties admissible additive noise to a convex polytope of competing secrets and to the energy gap to the second-best solution. They stay honest about hardware limits and do not claim a threat to standardized PQC.\n\nWhat they do well is the framing. Encoding both secret coefficients and explicit discretized error so both come out of the ground state is a clean constructive step relative to residual-only LWE/Ising encodings. The low-dimensional exact simulations that recover planted (secret, error) pairs, and the check that geometry and gap line up, are the right kind of evidence for a formulation paper. The scaling counts on logical variables and embedding overhead are practical for anyone who actually wants to put these on annealers. That is real, if niche, work.\n\nThe soft spot that matters is modular residual enforcement. Turning b − As − e ≡ 0 (mod q) into a pure quadratic binary objective needs binary expansions and penalty terms for multiples of the modulus. Under-scaled penalties let wrap-arounds or invalid expansions undercut the planted solution; over-scaled ones flatten the gaps the stability analysis equates to the polytope. Toy q and tiny error alphabets can hide that. The abstract’s recovery results do not by themselves prove that the unconstrained residual landscape is preserved, so uniqueness and the polytope–gap equivalence still rest on an assumption rather than a bound. That is a genuine gap for the central claims, not a cosmetic one—but it is the kind of gap a referee can force them to close with a penalty schedule or a uniqueness lemma.\n\nWho it is for: people building QUBO cryptanalysis demos and annealer benchmarks. Lattice cryptographers worried about Kyber will not change their priors. It is coherent on its own terms, carefully scoped, and worth a serious referee in a quantum-optimization or applied-crypto venue. I would not desk-reject it; I would send it out and ask specifically for the modular/penalty uniqueness argument plus instance generators or code.","headline":"Careful niche QUBO framing for small MLWE; joint encoding and polytope–gap stability are the real content, but modular penalty scaling is still the load-bearing open point.","tokens_in":3064,"tokens_out":544,"would_cite":false,"duration_ms":21132,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Small MLWE instances encode as QUBO so secret and error recover together from the ground state, with noise stability fixed by a convex polytope and the energy gap.","keywords":["Module Learning With Errors","QUBO","quantum annealing","post-quantum cryptography","stability analysis","energy gap","lattice-based cryptography","binary optimization"],"falsifier":"On a low-dimensional planted MLWE instance, solve the constructed QUBO exactly; if the recovered binary string does not decode to the planted secret and error, or if controlled additive perturbations make the ground state flip before the predicted energy-gap boundary of the noise polytope is reached, the central claim fails.","tokens_in":3000,"feed_emoji":"🔐","tokens_out":1046,"duration_ms":31698,"temperature":0.7,"pith_summary":"This paper shows how to turn small Module Learning With Errors (MLWE) instances—the hardness assumption behind several lattice-based post-quantum schemes—into Quadratic Unconstrained Binary Optimization (QUBO) problems that quantum annealers are designed to solve. The encoding puts the secret coefficients and the discretized error terms into one binary objective, so the lowest-energy assignment is meant to return both vectors at once. The authors then map out when that ground state survives additive noise: the safe region is a convex polytope whose faces are cut by rival candidate secrets, and the same region is equivalently read from the energy gap between the true optimum and the second-best solution. Exact classical simulation on low-dimensional planted instances recovers the secret and error and confirms that the geometric polytope and the energy gap agree. Scaling counts of logical variables and embedding overhead show how far current annealers sit from cryptographically sized parameters. A sympathetic reader cares because the construction supplies a concrete bridge from lattice cryptography into quantum optimization, together with an explicit robustness criterion, without claiming a break of real-world parameter sets.","feed_headline":"MLWE secrets and errors recover from one QUBO ground state","feed_subtitle":"Stability is a convex noise polytope equal to the energy gap; scaling stays far from crypto sizes.","key_machinery":"The joint QUBO encoding of secret coefficients and explicit error variables, paired with the energy-gap characterization of the admissible noise polytope. The encoding converts the MLWE residual equations into a quadratic binary objective whose ground state is the true (secret, error) pair; the polytope and gap then determine when that ground state survives additive landscape noise.","core_discovery":"Small MLWE samples can be constructively mapped to QUBO instances whose binary variables jointly encode the secret coefficients and the discretized error terms, so the ground-state assignment recovers both vectors simultaneously. The region of additive QUBO perturbations that preserve this ground state is a convex polytope whose facets are set by competing candidate secrets; that polytope is equivalently described by the energy gap between the optimal solution and the second-best one. Exact simulation on low-dimensional benchmarks recovers the planted secret and error and confirms agreement between the geometric and energy-gap pictures, while resource counts track logical variables and embed","pith_inferences":["The energy gap on a solved instance can serve as a practical diagnostic of how much hardware noise can be tolerated before recovery fails.","The joint secret-error encoding may transfer to related lattice problems such as NTRU or other Module-LWE KEM variants whenever the residual admits a low-degree polynomial objective.","Problem-aware minor embeddings that cut overhead could extend the dimensional reach of annealers on these instances faster than raw logical-variable scaling alone suggests.","Exact classical solvers for the small QUBOs could double as a validation suite for future hybrid quantum-classical lattice attacks, independent of annealing hardware."],"forward_implications":["Both secret and discretized error can be recovered from the ground state of the associated QUBO on small MLWE instances.","Recovery stability under additive noise is completely fixed by a convex polytope of competing secrets, equivalently by the QUBO energy gap to the runner-up.","Logical-variable count and embedding overhead grow in a quantifiable way with MLWE dimension, giving concrete resource estimates for annealer studies.","The same polytope and energy-gap tools give a general method for analyzing robustness of other QUBO formulations of lattice problems.","Under this encoding, current quantum annealing hardware remains far from cryptographically relevant MLWE parameters."],"fun_headline_variants":["QUBO ground state jointly recovers MLWE secrets and errors","MLWE secret and error vectors both emerge from one QUBO ground state","QUBO maps small MLWE so ground state yields secret plus error","MLWE-QUBO stability is convex noise polytope equal to energy gap","Energy gap equals the convex polytope that keeps MLWE QUBO optimal"],"cache_read_input_tokens":1664,"weakest_assumption_plain":"The binary encoding of secret coefficients and the discrete error variables must keep the MLWE residual structure intact so the true secret-error pair is exactly the unique QUBO ground state, and additive energy perturbations must be the right model of the noise that actually threatens recovery.","fun_headline_variants_meta":{"raw":{"variants":["QUBO ground state jointly recovers MLWE secrets and errors","MLWE secret and error vectors both emerge from one QUBO ground state","QUBO maps small MLWE so ground state yields secret plus error","MLWE-QUBO stability is convex noise polytope equal to energy gap","Energy gap equals the convex polytope that keeps MLWE QUBO optimal"]},"model":"grok-4.5","cost_usd":0.007148,"raw_usage":{"total_tokens":1822,"prompt_tokens":850,"num_sources_used":0,"completion_tokens":97,"cost_in_usd_ticks":71480000,"prompt_tokens_details":{"text_tokens":850,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":875,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":850,"tokens_out":97,"duration_ms":12049,"temperature":1.0,"reasoning_tokens":875,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T19:12:40.109333+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On a low-dimensional planted MLWE instance, solve the constructed QUBO exactly; if the recovered binary string does not decode to the planted secret and error, or if controlled additive perturbations make the ground state flip before the predicted energy-gap boundary of the noise polytope is reached, the central claim fails.","supporting_citations":[],"review_version":1}