Pith. sign in

REVIEW 2 major objections 2 minor 1 cited by

A strictly penalty-free mapping reduces LWE to a QUBO whose ground state on coherent Ising machines yields the secret.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.3

2026-06-26 08:24 UTC pith:NQAEJPXN

load-bearing objection Penalty-free LWE-to-QUBO reduction via algebraic elimination and CR-BNP encoder, shown on 40-dim CIM hardware, but thin on success metrics and unproven that the relaxation keeps exact BDD equivalence. the 2 major comments →

arxiv 2606.22843 v1 pith:NQAEJPXN submitted 2026-06-22 quant-ph cs.CR

When the Learning With Errors Problem Meets the Coherent Ising Machine: A Penalty-Free Algorithm-Hardware Co-Design

Shuxian Jiang This is my paper
classification quant-ph cs.CR
keywords Learning With ErrorsCoherent Ising MachinePenalty-free QUBOBounded-Distance DecodingClosest Vector ProblemPost-Quantum CryptanalysisNISQ hybrid solver
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes CIM-BDD, a hybrid solver that converts the Learning With Errors problem into a Quadratic Unconstrained Binary Optimization instance without any penalty terms. It achieves this by algebraically eliminating the secret to embed the modular LWE instance into a q-ary lattice, turning the task into a Closest Vector Problem whose squared error norm becomes the objective function to minimize. A Continuous Relaxed Babai's Nearest Plane projection combined with an adaptive mixed-radix encoder shrinks the qubit count and coefficient range so that a single hardware batch suffices on NISQ devices. The method supplies a statistically bounded early-stopping threshold that serves as both a solution certificate and a Decision-LWE distinguisher. End-to-end validation recovers solutions for 40-dimensional Search- and Decision-LWE instances on the Coherent Ising Machine CPQC-550.

Core claim

LWE is reduced to a QUBO through algebraic elimination of the secret that absorbs modular arithmetic into a q-ary lattice CVP, after which the squared error norm is used directly as the energy function; the Continuous Relaxed Babai's Nearest Plane projection and adaptive mixed-radix encoder then produce a compact instance whose ground state on the physical machine recovers the LWE solution.

What carries the argument

Penalty-free QUBO mapping via algebraic embedding of LWE into q-ary lattice CVP, with squared error norm as energy, realized by Continuous Relaxed Babai's Nearest Plane projection plus adaptive mixed-radix encoder.

Load-bearing premise

The Continuous Relaxed Babai's Nearest Plane projection together with the adaptive mixed-radix encoder produces a QUBO whose ground state on the hardware exactly matches the correct LWE solution without errors that break the bounded-distance decoding guarantee.

What would settle it

Running the constructed QUBO on the Coherent Ising Machine for a known 40-dimensional LWE instance and finding that the returned ground state does not recover the secret vector, or that the early-stopping threshold incorrectly certifies an invalid solution.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • A single batched hardware submission suffices for the encoded instance because the encoder keeps both qubit count and coefficient range within NISQ limits.
  • The early-stopping threshold T_early supplies a one-sided certificate for Search-LWE and simultaneously acts as a Decision-LWE distinguisher.
  • The same penalty-free formulation applies to both Search-LWE and Decision-LWE, demonstrated end-to-end on the TU Darmstadt Challenge.
  • The co-design reduces the problem size enough that current coherent Ising machines can handle 40-dimensional instances without classical post-processing beyond the threshold check.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same algebraic elimination step could be applied to other modular lattice problems whose noise term can be expressed as a squared norm.
  • If the encoder's relaxation error remains bounded for larger dimensions, the method would scale to instances currently out of reach for classical lattice reduction alone.
  • Hardware-specific coefficient compression via mixed-radix encoding may transfer to other Ising-machine or quantum-annealing platforms that suffer from limited dynamic range.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes CIM-BDD, a hybrid Bounded-Distance-Decoding solver that reduces LWE to a penalty-free QUBO by algebraically eliminating the secret into a q-ary lattice (recasting as CVP with squared error norm as the objective), employs a Continuous Relaxed Babai's Nearest Plane (CR-BNP) projection to drive an adaptive mixed-radix encoder that reduces qubit count and coefficient range, derives a statistically bounded early-stopping threshold T_early as a one-sided certificate and Decision-LWE distinguisher, and reports an end-to-end hardware demonstration of both Search- and Decision-LWE on a 40-dimensional TU Darmstadt challenge instance using the Coherent Ising Machine CPQC-550.

Significance. If the penalty-free mapping and CR-BNP encoding preserve exact equivalence to the original BDD instance without introducing spurious low-energy states outside the noise bound, the approach would establish a new algorithm-hardware co-design paradigm for lattice-based cryptanalysis on Ising machines. The direct use of the cryptographic noise norm as the QUBO objective (rather than a penalized constraint) and the single-submission batched encoding are technically distinctive strengths; the hardware run, even at small scale, provides a concrete existence proof for NISQ deployment.

major comments (2)
  1. [Experimental Results / Hardware Demonstration] Experimental validation section (hardware demonstration of 40-dimensional instance): the abstract and results report a successful run on the CPQC-550 but supply no success probabilities, bit-error rates, baseline comparisons (e.g., against classical BDD or other QUBO solvers), or statistical validation of the T_early threshold; without these metrics the claim of an 'end-to-end demonstration' for both Search- and Decision-LWE lacks the quantitative support required to substantiate the framework's correctness.
  2. [Encoding Method / CR-BNP Projection] Encoding construction (CR-BNP projection and adaptive mixed-radix encoder): the continuous relaxation of Babai's nearest-plane method is used to set variable bounds and radix choices, yet no derivation shows that every ground state of the resulting QUBO maps back to a lattice vector whose distance to the target lies strictly inside the BDD radius; if the relaxation admits configurations whose decoded vectors exceed the LWE noise bound, the one-sided certificate T_early no longer certifies a valid solution.
minor comments (2)
  1. [Abstract / Introduction] The abstract states that the squared error norm is used 'directly' as the QUBO energy; a brief explicit statement of the algebraic elimination step (how the modular reduction is absorbed without auxiliary variables) would clarify the penalty-free property for readers unfamiliar with q-ary lattice embeddings.
  2. [Early-Stopping Threshold] Notation for the early-stopping threshold T_early is introduced without an accompanying equation number or explicit statistical derivation in the provided abstract; adding the defining expression and the one-sided probability bound would improve traceability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive comments on our manuscript. We address each major comment below, indicating where revisions will strengthen the presentation.

read point-by-point responses

  1. Referee: [Experimental Results / Hardware Demonstration] Experimental validation section (hardware demonstration of 40-dimensional instance): the abstract and results report a successful run on the CPQC-550 but supply no success probabilities, bit-error rates, baseline comparisons (e.g., against classical BDD or other QUBO solvers), or statistical validation of the T_early threshold; without these metrics the claim of an 'end-to-end demonstration' for both Search- and Decision-LWE lacks the quantitative support required to substantiate the framework's correctness.

    Authors: We agree that the experimental section would benefit from additional quantitative metrics to fully substantiate the end-to-end demonstration. In the revised manuscript we will add success probabilities and bit-error rates computed over repeated hardware submissions on the 40-dimensional instance, include baseline comparisons against classical BDD implementations on the same TU Darmstadt challenge instance, and provide a statistical validation of the T_early threshold derived from the LWE noise distribution together with empirical histograms from the CPQC-550 runs. revision: yes

  2. Referee: [Encoding Method / CR-BNP Projection] Encoding construction (CR-BNP projection and adaptive mixed-radix encoder): the continuous relaxation of Babai's nearest-plane method is used to set variable bounds and radix choices, yet no derivation shows that every ground state of the resulting QUBO maps back to a lattice vector whose distance to the target lies strictly inside the BDD radius; if the relaxation admits configurations whose decoded vectors exceed the LWE noise bound, the one-sided certificate T_early no longer certifies a valid solution.

    Authors: The CR-BNP projection selects bounds and radices so that every admissible integer combination corresponds to a lattice vector whose squared distance to the target is at most the squared BDD radius; the continuous relaxation is used only to approximate the nearest-plane decision and does not enlarge the feasible set beyond the noise ball. Nevertheless, an explicit end-to-end derivation establishing that every QUBO ground state decodes to a vector strictly inside the BDD radius was omitted from the original text. In the revision we will insert a formal lemma and proof (in the main body or appendix) showing that the encoding is injective on the relevant ball and that the QUBO objective coincides exactly with the squared error norm, thereby confirming that T_early remains a valid one-sided certificate. revision: yes

Circularity Check

0 steps flagged

No circularity: algebraic LWE-to-QUBO reduction is direct and externally validated

full rationale

The derivation begins with an algebraic elimination that recasts LWE as a q-ary CVP whose squared error norm becomes the QUBO objective by direct substitution; this is a one-way mathematical embedding, not a self-definition or fitted parameter renamed as a prediction. The CR-BNP projection and mixed-radix encoder are presented as a hardware-specific encoding step whose correctness is asserted via the subsequent T_early certificate and 40-dimensional hardware run on the external TU Darmstadt challenge, not by internal closure. No self-citations, uniqueness theorems, or ansatzes are invoked to justify the core mapping, and the result is not forced to equal its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, axioms, or invented entities are stated in sufficient detail to enumerate.

axioms (1)
  • domain assumption LWE instances can be algebraically reduced to a q-ary lattice CVP whose squared error norm serves directly as QUBO energy
    Stated as the core mapping step in the abstract.

pith-pipeline@v0.9.1-grok · 5831 in / 1251 out tokens · 15728 ms · 2026-06-26T08:24:09.359977+00:00 · methodology

0 comments
read the original abstract

The Learning With Errors (LWE) problem constitutes the mathematical foundation of modern Post-Quantum Cryptography (PQC). Cryptanalysis of LWE ranges from classical lattice reduction to machine learning and quantum-classical hybrids. We propose CIM-BDD, a hybrid Bounded-Distance-Decoding solver that reduces LWE to a Quadratic Unconstrained Binary Optimization (QUBO) problem through a strictly \emph{penalty-free} mapping. An algebraic elimination of the secret embeds LWE into a $q$-ary lattice, absorbing the modular arithmetic and recasting the problem as a Closest Vector Problem (CVP). The squared error norm is then used \emph{directly} as the QUBO energy, so the cryptographic noise is the objective to be minimized rather than a penalized constraint. To realize this general model on current Noisy Intermediate-Scale Quantum (NISQ) devices, we design a special encoding method: a Continuous Relaxed Babai's Nearest Plane (CR-BNP) projection drives an adaptive mixed-radix encoder that greatly reduces both the qubit count and the QUBO coefficient range, so that a single batched hardware submission suffices. We further derive a statistically bounded early-stopping threshold ($T_{\text{early}}$) that acts as a one-sided certificate and doubles as a Decision-LWE distinguisher. We validate the framework on the TU Darmstadt LWE Challenge, giving an end-to-end demonstration for both Search- and Decision-LWE of a $40$-dimensional instance on the Coherent Ising Machine CPQC-550. This work establishes a new algorithm-hardware co-design paradigm for quantum-classical hybrid cryptanalysis.

Figures

Figures reproduced from arXiv: 2606.22843 by Shuxian Jiang.

Figure 1
Figure 1. Figure 1: Trend of the theoretical ∥b ∗ 1 ∥ and ∥b ∗ m′∥ as functions of sub-dimension m′ for the n = 40 instance (q = 1601, γH = 1.0128 (BKZ-20), σ = 8.005). The dash-dotted purple line at 6σ ≈ 48 is the Babai hard-decision failure region threshold, the grey vertical line at m′ = 88 marks the point used in the experiments, the analytic maximum of ∥b ∗ m′∥ occurs at m′ = 152. Hence the coordinate error is ϵy = yc,ex… view at source ↗
Figure 2
Figure 2. Figure 2: Decision-LWE on LWE_40_005: measured post-corrector residual energies (Tearly = 9040). Green = true-LWE seeds the pipeline solves (residual crosses below Tearly, secret recov￾ered), gray = true-LWE seeds the solver fails, red = uniform-random control, light-red histogram = n=220 uniform targets evaluated by classical minimization on the same reduced bases. Pro￾gressive BKZ-20 → 30 raises the solved fractio… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. QUBO Modeling of Module Learning With Errors: Stability and Scaling in Post-Quantum Cryptography

    quant-ph 2026-07 unverdicted novelty 5.5

    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.

Reference graph

Works this paper leans on

26 extracted references · 1 canonical work pages · cited by 1 Pith paper

  1. [1]

    FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard

    National Institute of Standards and Technology (NIST), “FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard”, 2024

    2024

  2. [2]

    FIPS 204: Module-Lattice-Based Digital Signature Standard

    National Institute of Standards and Technology (NIST), “FIPS 204: Module-Lattice-Based Digital Signature Standard”, 2024

    2024

  3. [3]

    On lattices, learning with errors, random linear codes, and cryptography

    Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography”, in Journal of the ACM, Volume 56, Issue 6, 2009

    2009

  4. [4]

    Factoring polynomials with rational coeffi- cients

    A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coeffi- cients”,Math. Ann., 1982

    1982

  5. [5]

    On Lovász’ lattice reduction and the nearest lattice point problem

    L. Babai, “On Lovász’ lattice reduction and the nearest lattice point problem”, inSTACS, 1985

    1985

  6. [6]

    Better Key Sizes (and Attacks) for LWE-Based Encryption

    R. Lindner and C. Peikert, “Better Key Sizes (and Attacks) for LWE-Based Encryption”, in CT-RSA, 2011

    2011

  7. [7]

    Lattice basis reduction: Improved practical algorithms and solving subset sum problems

    C.-P. Schnorr and M. Euchner, “Lattice basis reduction: Improved practical algorithms and solving subset sum problems”,Mathematical programming, vol. 66, pp. 181–199, 1994

    1994

  8. [8]

    BKZ 2.0: Better lattice security estimates

    Y. Chen and P. Q. Nguyen, “BKZ 2.0: Better lattice security estimates”,Advances in Cryptology–ASIACRYPT 2011, pp. 1–20, Springer, 2011

    2011

  9. [9]

    Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator

    Y. Aono, Y. Wang, T. Hayashi, and T. Takagi, “Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator”,Advances in Cryptology–EUROCRYPT 2016, pp. 789–819, Springer, 2016

    2016

  10. [10]

    On the concrete hardness of Learning with Errors

    M. R. Albrecht, R. Player, and S. Scott, “On the concrete hardness of Learning with Errors”, J. Math. Cryptol., 2015

    2015

  11. [11]

    New directions in nearest neighbor searching with applications to lattice sieving

    A. Becker, L. Ducas, N. Gama, and T. Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving”, inSODA, 2016

    2016

  12. [12]

    SALSA: Attacking lattice cryptography with transformers

    E. Wenger, M. Chen, F. Charton, and K. E. Lauter, “SALSA: Attacking lattice cryptography with transformers”,NeurIPS 2022: Proceedings of the 36th International Conference on Neural Information Processing Systems, 2022

    2022

  13. [13]

    Salsa Picante: A machine learning attack on LWE with binary secrets

    C. Y. Li, J. Sotáková, E. Wenger, M. Malhou, E. Garcelon, F. Charton, and K. Lauter, “Salsa Picante: A machine learning attack on LWE with binary secrets”,Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, pp. 2606–2620, 2023

    2023

  14. [14]

    Salsa Fresca: Angular embeddings and pre-training for ml attacks on learning with errors

    S. Stevens, E. Wenger, C. Li, N. Nolte, E. Saxena, F. Charton, and K. Lauter, “Salsa Fresca: Angular embeddings and pre-training for ml attacks on learning with errors”,Cryptology ePrint Archive, 2024

    2024

  15. [15]

    Benchmarking attacks on learning with errors

    E. Wenger, E. Saxena, M. Malhou, E. Thieu, and K. Lauter, “Benchmarking attacks on learning with errors”,2025 IEEE Symposium on Security and Privacy (SP), pp. 279–297, 2025. 17

    2025

  16. [16]

    A fully programmable 100-spin coherent Ising machine with all-to-all connections

    P. L. McMahon, A. Marandi, Y. Haribara, R. Hamerly, C. Langrock, S. Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K. Aihara, et al., “A fully programmable 100-spin coherent Ising machine with all-to-all connections”,Science, vol. 354, no. 6312, pp. 614–617, 2016

    2016

  17. [17]

    Experimental investigation of performance differences between coherent Ising machines and a quantum annealer

    R. Hamerly, T. Inagaki, P. L. McMahon, D. Venturelli, A. Marandi, T. Onodera, E. Ng, C. Langrock, K. Inaba, T. Honjo, et al., “Experimental investigation of performance differences between coherent Ising machines and a quantum annealer”,Science Advances, Vol 5, Issue 5, 2019

    2019

  18. [18]

    A versatile coherent Ising computing platform

    H. Wei, C. Ai, P. Guo, B. Jia, L. Yuan, H. Song, S. Chen, C. Cao, J. Wu, C. Ju, Y. Ma, J. Fan, M. Hu, C. Wang, K. Wen, “A versatile coherent Ising computing platform”,Light: Science & Applications, vol. 15, no. 74, 2026

    2026

  19. [19]

    Not-so-adiabatic quantum computation for the shortest vector problem

    D. Joseph, A. Ghionis, C. Ling, and F. Mintert, “Not-so-adiabatic quantum computation for the shortest vector problem”,Phys. Rev. Res., 2020

    2020

  20. [20]

    Cryptanalysis of LWE and SIS-based cryptosystems by using quantum annealing

    A. Qayyum and M. Haris, “Cryptanalysis of LWE and SIS-based cryptosystems by using quantum annealing”,Prikladnaya Diskretnaya Matematika, Supplement, pp. 117–123, 2023

    2023

  21. [21]

    AdvancingLWEcryptanalysis: anupdatedMIPmodelandQUBOformulation for quantum annealing

    A.Qayyum, “AdvancingLWEcryptanalysis: anupdatedMIPmodelandQUBOformulation for quantum annealing”,Prikladnaya Diskretnaya Matematika, pp. 194–200, 2025

    2025

  22. [22]

    Using Variational Quantum Algorithm to Solve the LWE Problem

    L. Lv, B. Yan, H. Wang, Z. Ma, Y. Fei, X. Meng, and Q. Duan, “Using Variational Quantum Algorithm to Solve the LWE Problem”,Entropy, vol. 24, no. 10, p. 1428, 2022

    2022

  23. [23]

    Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices

    M. Zheng, J. Zeng, W. Yang, P.-J. Chang, Q. Lu, B. Yan, H. Zhang, M. Wang, S. Wei, and G.-L. Long, “Quantum-classical hybrid algorithm for solving the learning-with-errors problem on NISQ devices”,Communications Physics, volume 8, Article number: 208, 2025

    2025

  24. [24]

    Quantum algorith- mic solutions to the shortest vector problem on simulated coherent Ising machines

    E. Dable-Heath, L. Casas, V. Hertz, C. Porter, F. Mintert, and C. Ling, “Quantum algorith- mic solutions to the shortest vector problem on simulated coherent Ising machines”,arXiv preprint arXiv:2304.04075v3, 2023

    work page arXiv 2023

  25. [25]

    Kaiwu SDK,https://kaiwu-sdk-docs.qboson.com/en/. (2022)

    2022

  26. [26]

    Lattice Challenge – LWE Challenge

    TU Darmstadt, “Lattice Challenge – LWE Challenge”,https://www.latticechallenge. org/lwe_challenge/challenge.php. 18 A Algebraic Isomorphism and Explicit Lattice Basis Extraction In standard reductions from the Learning With Errors (LWE) problem to Bounded-Distance Decoding (BDD), the primalq-ary latticeΛ q(A)is often defined using a generating matrix [A|q...