When the Learning With Errors Problem Meets the Coherent Ising Machine: A Penalty-Free Algorithm-Hardware Co-Design
arXiv:2606.22843v1 [quant-ph] 22 Jun 2026
Shuxian Jiang∗
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 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 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 (Tearly ) that acts as a onesided certificate and doubles as a Decision-LWE distinguisher. We validate the framework on the TU Darmstadt LWE Challenge, giving an end-toend 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 codesign paradigm for quantum-classical hybrid cryptanalysis.
1
Introduction
Unlike integer factorization and the discrete logarithm problem, the Learning With Errors (LWE) problem, introduced by Oded Regev [3], is believed to resist quantum attack. It is extensively utilized in Post-Quantum Cryptography (PQC) and provides the theoretical foundation for NIST standard schemes such as ML-KEM (FIPS 203) and ML-DSA (FIPS 204) [1, 2], and it is the fundamental building block of Fully Homomorphic Encryption (FHE). LWE enjoys a worst-case to average-case guarantee: solving the average-case problem is at least as hard as worst-case lattice problems such as the Shortest Vector Problem (SVP). Concretely, LWE asks to recover a secret vector s ∈ Znq from a matrix A and a vector c with c = As + e
(mod q),
(1)
where e is a small error vector drawn from a discrete Gaussian distribution. This unknown error is what makes the system intractable for both classical and quantum algorithms. Evaluating the concrete security of LWE is an active area of research. In classical cryptanalysis, the lattice-based method that maps LWE to Bounded Distance Decoding (BDD) and solves it via lattice basis reduction, notably BKZ [7–9], remains dominant, complemented by advanced estimators based on enumeration with pruning or sieving [10, 11]. Locating closest or shortest ∗
Email: [email protected]
1
vectors is, however, (sub)exponential. In parallel, machine-learning attacks [12,13] have emerged, but they rely on large training datasets and scale poorly to cryptographic dimensions [14, 15]. With the advent of NISQ devices, attention has shifted to quantum–classical hybrids. For instance, Lv et al. [22] use QAOA to optimize the nearest plane algorithm in order to solve LWE and apply a Variational Quantum Eigensolver to the unique SVP (uSVP), while Zheng et al. [23] encode lattice vectors into an Ising model (HAWI). Reducing LWE to a lattice problem via nullspaces absorbs the modular arithmetic classically (as in HAWI [23]), but framing the resulting problem as an SVP inherently introduces the trivial-zero symmetry. To avoid collapsing to the origin without explicit penalties, SVP-based solvers are forced to restrict variable domains and sequentially evaluate O(m) or O(n) independent sub-Hamiltonians [23, 24], or attempt to target the first excited state [19]. Conversely, direct LWE QUBO formulations [20, 21] rely heavily on auxiliary slack variables and penalty coefficients to enforce modular constraints, which distort the energy landscape. Our method is similar to [22], but makes a different algorithm-hardware co-design. By modeling LWE as CVP (BDD) and using the squared error norm directly as the objective energy, we get a penalty-free QUBO formulation (as well as a justification), then partition the search space to model partial dimensions using a Continuous Relaxed Babai’s Nearest Plane driven adaptive mixed-radix encoder. We present both theoretical analysis and experimental verification on real hardware for LWE challenge instance of dimension 40.
1.1
Our Contributions
We propose the CIM-BDD framework, a hybrid BDD solver suitable for Coherent Ising Machines (CIMs) [16, 18], which support fully-connected topologies. Our framework advances the field through both mathematical modeling and physical hardware realization: • A Strictly Penalty-Free QUBO Formulation of LWE. In Section 3, an algebraic elimination of the secret absorbs the modulus into a primal q-ary lattice and recasts LWE as a Closest Vector Problem (CVP), then uses the Babai-recentered least-squares residual as the QUBO energy. So the cryptographic noise becomes the objective rather than a penalized constraint. This yields a strictly penalty-free modeling. • A Compact Encoding for NISQ-Scale Qubit Budgets and Precision Limits. To map this general model onto precision-limited hardware (Section 4), a Continuous Relaxed Babai’s Nearest Plane (CR-BNP) projection acts as a prior driving an adaptive mixedradix encoder (allocating 0/1/2 bits). This compresses the target combinatorial space, restricting the n = 40 instance to fewer than 20 logical qubits. • A One-Sided Statistical Certificate and DLWE Distinguisher via Tearly . From the χ2 properties of the√discrete-Gaussian error variance we derive an early-stopping threshold Tearly = m′ σ 2 +4σ 2 2m′ . Placing a four-sigma confidence boundary on the residual energy makes this a one-sided statistical certificate: a candidate that crosses below Tearly certifies the LWE secret directly from the ground-state energy, with no algebraic re-verification. The same binary crossing doubles as a Decision-LWE distinguisher.
2
Preliminaries
2.1
Lattices and the LWE Problem
A lattice is defined as the set of all integer linear combinations of linearly independent basis vectors. Let b1 , b2 , . . . , bn ∈ Rm (with n ≤ m) be a set of linearly independent vectors. The lattice generated by these vectors is defined as: ( n ) X L(b1 , . . . , bn ) = xi bi : xi ∈ Z . (2) i=1
2
The set of vectors {b1 , . . . , bn } is called a basis of the lattice. It is often convenient to represent the basis as a matrix B = [b1 , b2 , . . . , bn ] ∈ Rm×n having the basis vectors as its columns. Consequently, the lattice can be equivalently denoted as L(B) = {Bx : x ∈ Zn }. The security of lattice-based cryptography fundamentally relies on the presumed intractability of several well-known computational problems, like the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). Shortest Vector Problem (SVP): Given a lattice basis B, find a non-zero lattice vector v ∈ L(B) such that its Euclidean norm ||v|| is minimized. The length of this shortest non-zero vector is known as the first successive minimum of the lattice, denoted as λ1 (L). Closest Vector Problem (CVP): Given a lattice basis B and a target vector t ∈ Rm (not necessarily in the lattice), find a lattice vector v ∈ L(B) that minimizes the distance ||v − t||. SVP and CVP are the most foundational worst-case problems in lattice theory. Both problems are known to be NP-hard and remain computationally intractable for classical and quantum algorithms even when approximated within polynomial factors. However, cryptographic constructions generally require problems that are hard on average rather than in the worst case. The Learning With Errors (LWE) problem bridges this gap. Definition 1 (Learning With Errors (LWE)). Let n, m, q be positive integers. Let A ∈ Zm×n be q a uniformly random matrix and s ∈ Znq be a secret vector. The LWE samples are given by the pair (A, c), where c = As + e (mod q), and e ∈ Zm is sampled independently from a discrete Gaussian distribution DZm ,σ with standard deviation σ = αq. The search variant (Search-LWE, SLWE) aims to find s, the decision variant (Decision-LWE, DLWE) aims to distinguish (A, c) from uniform randomness. q-ary Lattices Given an integer modulus q ≥ 2 and a uniformly random public matrix A ∈ Zm×n (with m > n), a primal q-ary lattice Λq (A) is defined as the set of all integer vectors that q belong to the image of A modulo q: n o Λq (A) = v ∈ Zm ∃s ∈ Znq such that v ≡ As (mod q) . (3) LWE as Average-Case Bounded-Distance Decoding (BDD). The Bounded-Distance Decoding (BDD) problem is a variant of the closest vector problem (CVP), where the target point is guaranteed to be so close to the lattice that there is a unique closest vector. LWE can be seen as an average-case BDD problem over the q-ary lattice Λq (A) [6]. Because any valid algebraic evaluation As (mod q) mathematically constitutes a true lattice point v ∈ Λq (A), the LWE target vector c represents a spatial coordinate shifted away from the lattice point v by the discrete Gaussian noise e. Therefore, finding this closest lattice vector v isolates the error e and recovers the cryptographic secret s.
2.2
Quadratic Unconstrained Binary Optimization (QUBO)
In combinatorial optimization, QUBO represents binary variables x ∈ {0, 1}N minimizing f (x) = x⊤ Qx, where Q is an upper-triangular real-weighted matrix. QUBO is mathematically isomorP P phic to the Ising Hamiltonian H(z) = − i<j Jij zi zj − i hi zi for zi ∈ {+1, −1}. Coherent Ising Machines (CIMs) support fully-connected graph topologies for these models via measurementfeedback architectures [16, 17].
3
3
The Exact Model: A Penalty-Free QUBO Formulation via a Least-Squares CVP Objective
This section establishes the mathematical core of the framework: a reduction that turns LWE into an exact, penalty-free QUBO whose energy is the squared error norm. The guiding principle is to make the cryptographic noise the quantity to be minimized rather than a constraint to be penalized. Standard QA/CIM mappings of LWE either introduce auxiliary variables to encode the modular arithmetic or add penalty/slack terms to enforce feasibility, both of which distort the energy landscape. We instead remove the modulus by algebraic elimination and define the objective as a least-squares residual whose minimizer is, by maximum likelihood, the true error vector. The result is a penalty-free cost function in which the target sits at the unique global minimum and the trivial-zero symmetry is broken by the residual’s own linear term.
3.1
Reduction from LWE to CVP
We begin with the standard LWE relation over Zq : As + e ≡ c (mod q). To eliminate the secret vector s, we define a matrix W whose columns form a basis for the left nullspace of A modulo q, satisfying W⊤ A ≡ 0 (mod q). Multiplying the LWE relation by W⊤ from the left yields: W⊤ c ≡ W⊤ (As + e) = W⊤ As + W⊤ e ≡ W⊤ e
(mod q)
(4)
Rearranging the terms, we obtain: W⊤ (e − c) ≡ 0
(mod q)
(5)
Eq. (5) indicates that the vector (e − c) lies precisely within the lattice spanned by the columns of A modulo q. Let M be the generating matrix of this q-ary lattice space, typically constructed as M = [A | qI]. By explicitly extracting a full-rank integer basis for this lattice (as detailed in Appendix A) and performing lattice basis reduction (such as LLL or BKZ), we obtain a reduced basis matrix B0 . Thus there exists an integer vector y satisfying c − e = B0 y. The primary objective is to recover the error vector e, which is sampled from a distribution with a small variance. This is mathematically equivalent to finding an integer vector y that minimizes the squared Euclidean norm of e: ∥e∥2 = ∥c − B0 y∥2 = ∥B0 y − c∥2
(6)
This formulation represents a standard Closest Vector Problem (CVP), where the goal is to find a lattice point B0 y that is closest to the target vector c.
3.2
Search Space Recentering via Babai’s Algorithm
Babai’s Nearest Plane algorithm [5] provides an approximate closest lattice point, and we denote its corresponding coefficient vector as ycenter . We parameterize the target integer vector y as an offset ∆y from this center point: ∆y = y − ycenter =⇒ y = ∆y + ycenter
(7)
Substituting this offset parameterization into our objective norm function, we obtain: ∥e∥2 = ∥B0 (∆y + ycenter ) − c∥2 = ∥B0 ∆y + B0 ycenter − c∥2
(8)
To recenter the search space around the origin, we define a shifted target vector cshift representing the residual error of the approximate center point: cshift = c − B0 ycenter 4
(9)
Substituting cshift , the distance minimization objective is transformed into: ∥e∥2 = ∥B0 ∆y − cshift ∥2
(10)
By reformulating the problem with cshift , the subsequent search algorithm only needs to explore small displacement vectors ∆y around the origin. This recentering technique significantly bounds the search radius and improves the overall computational efficiency of recovering the error vector e.
3.3
QUBO Objective Formulation for the LWE Problem
We use ∥e∥2 as the objective function to include the discrete Gaussian distribution of e. This approach mathematically corresponds to performing Maximum Likelihood Estimation (MLE) under the assumption that the noise follows a discrete Gaussian distribution. Within the BDD regime the planted error is the unique closest offset of c to the lattice, so this least-squares minimizer recovers the true error with high probability. Remark 1 (Statistical Equivalence via Maximum Likelihood Estimation). For a Learning With Errors (LWE) instance with independent Gaussian noise, minimizing the squared Euclidean norm of the error vector ∥e∥2 is mathematically equivalent to computing the Maximum Likelihood Estimate (MLE) of these variables. Proof. In the standard LWE setting, each component ei (i = 1, . . . , m) of the error vector e is sampled independently from a discrete Gaussian distribution over Z centered at 0 with standard deviation σ. The probability function for a single error component ei is proportional to: e2i P (ei ) ∝ exp − 2 (11) 2σ Because the components ei are independent and identically distributed (i.i.d.), the joint probability distribution (or the likelihood function L) of the entire error vector e is the product of the probabilities of its individual components: ! m m m X Y Y e2i ∥e∥2 e2i = exp − 2 (12) L(e) = P (ei ) ∝ exp − 2 = exp − 2σ 2σ 2 2σ i=1
i=1
i=1
Because the variance σ 2 is a static independent constant inherent to the LWE parameters, the statistical maximization of the log-likelihood function corresponds identically to the minimization of the residual squared norm: arg maxe ln L(e) ≡ arg mine ∥e∥2 .
4
NISQ Realization: Relaxation to an Approximate Model and Recovery of Exactness
While the mathematical formulations in Section 3 provide an exact mapping to a quadratic objective and represent a hardware-independent general model, evaluating them on current Noisy Intermediate-Scale Quantum (NISQ) devices requires overcoming physical precision limits. Therefore, we introduce an adaptive encoding strategy to successfully embed the problem onto the CIM. This approach makes a trade-off by introducing a continuous approximation, nevertheless, our hybrid framework provides intrinsic robustness to reconstructing the secret from heuristic hardware outputs.
5
4.1
Approximate Encoding, Hardware Embedding and Result Recovery
4.1.1
Matrix Conditioning and CR-BNP
Instead of modeling the entire space as previous methods did, we partition the lattice into a frozen subspace (F) reserved for classical substitution, and an exploration subspace (E) exclusively mapped to the CIM. This partitioning strategy significantly reduces the number of variables in the QUBO formulation, making it highly feasible for current hardware capacities and precision limits. While Section 3 utilizes the standard Babai’s Nearest Plane algorithm to provide an approximate closest lattice point, we introduce a modification here. Within the exploration subspace, we deliberately defer the discrete rounding operation (⌊·⌉). Instead, we allow the modified algorithm to use continuous projection coefficients to sequentially compute the continuous coordinates (yc ). We term this approach Continuous Relaxed Babai’s Nearest Plane (CR-BNP). Subsequently, we extract the fractional residuals (δ = yc − ⌊yc ⌉) to drive the Adaptive Mixed-Radix Encoding and formulate our QUBO model. Once the discrete assignments for the exploration subspace are resolved by the CIM, we apply the traditional discrete Babai’s algorithm to determine the remaining coordinates in the frozen subspace (F ). This continuous-discrete division not only mitigates premature rounding error propagation across the entire space but also explicitly extracts the continuous ambiguities required for the adaptive encoding detailed in the next step. 4.1.2
Adaptive Mixed-Radix Dimensionality Reduction
Recognizing that the fractional deviations δi quantify spatial proximity, we devise an Adaptive Mixed-Radix Encoder to bound the offset ∆y introduced in Section 3. Because the CRBNP projection already centers the search space near the true lattice point, the residual discrete offset is bounded. Thus, we constrain the search domain per dimension to the local integer neighborhood, ∆yi ∈ {−1, 0, 1}. Rather than blindly imposing expensive ternary expansions across all variables, the encoder operates exclusively within the exploration subspace. Setting empirical continuous thresholds τlow and τhigh , it dynamically allocates bit-widths based on spatial ambiguity: dimensions with low ambiguity (|δi | < τlow ) are fixed as 0-bit constants; dimensions exhibiting strong directional tendencies (|δi | ≥ τhigh ) are pruned into 1-bit constrained Boolean biases; and only highly localized, ambiguous fractional limits (τlow ≤ |δi | < τhigh ) retain a full 2-bit (ternary) encoding. This dynamic pruning systematically performs combinatorial dimensionality reduction, compressing the exponentially large raw configuration space into a highly compact logical domain. It also narrows the dynamic amplitude range of the resulting QUBO coefficients, making the model more amenable to hardware precision limits. 4.1.3
Hardware Execution and Bounded Correction
To maximize the utilization of available physical qubits (e.g., the 550-spin capacity of our target CIM), we employ a variable partitioning strategy. Let Nlog denote the total number of logical variables required for the QUBO model. We select a small number of pivot variables, denoted as K (e.g., K = 5 in Section 6), subject to the parallel embedding constraint 2K ×(Nlog −K) ≤ 550. These K variables are deterministically chosen from the 1-bit assigned dimensions by sorting their continuous fractional ambiguities |δi | in descending order. By exhaustively enumerating the 2K possible Boolean assignments for these pivot variables, we inject each assignment as a constant bias into the QUBO formulation. The resulting 2K independent sub-problems, each of size Nlog − K, are then packed block-diagonally into a sparse global configuration. Prior to mapping, each sub-problem is individually linearly scaled by its
6
maximum absolute coefficient amplitude and uniformly quantized. This strategy enables the entire ensemble to be mapped onto the CIM hardware in a single batched submission. Translating the continuous landscape into a discrete QUBO formulation introduces misalignments at integer boundaries. Confined by hardware precision limits, this misalignment can cause continuous pseudo-minima to incur rounding penalties upon forced discretization. To rescue these near-miss configurations upon retrieving the hardware solutions, we apply a classical bounded neighborhood corrector (R ≤ 2) over the full candidate vector to repair small deviations. Specifically, the R = 1 search loops through all indices to test a single ±1 step mutation, while R = 2 enumerates every pair of indices for combinatorial ±1 steps. Whenever the corrector actively mutates these 1 or 2 target dimensions, it deterministically shifts the continuous target projection for the remaining subspace and immediately invokes the discrete Babai’s nearest plane algorithm to re-evaluate all preceding indices. Consequently, a single ±1 step on a trailing exploration coordinate can adaptively repair long propagated mis-roundings in the leading frozen coordinates.
4.2
Complete Pipeline Summary
Algorithm 1 summarizes the end-to-end pipeline integrating the three preceding components. The five phases proceed sequentially: algebraic isomorphism (Phase 1) and Gram-Schmidt projection (Phase 2) prepare the lattice geometry; CR-BNP (Phase 3, Section 4.1.1) extracts the continuous fractional ambiguity; the adaptive mixed-radix encoder (Phase 4, Section 4.1.2) compresses the search into a logical-bit QUBO, with variable partitioning yielding 2K block-diagonal sub-problems for one CIM submission; finally, post-processing verification and the R ≤ 2 bounded corrector (Phase 5, Section 4.1.3) distinguish the true result and recover the secret. We defer the detailed process to Appendix B.
4.3
Sources of Inaccuracy and the Recovery Method
The pipeline does not solve the LWE instance exactly, it solves the dexp -dimensional exploration QUBO (near-)exactly. Sources of inexactness include: the heuristic 0/1/2-bit encoding window omitting the true offset, continuous-integer misalignments altering the QUBO landscape, limited hardware input precision, and frozen-subspace Babai mis-rounding. The recovery layer is designed to rescue these losses. Each CIM submission returns an ensemble of low-energy configurations at distinct energy levels. Whenever the true point coincides with one of them or lies within the R ≤ 2 neighborhood of one, the bounded corrector restores it and the Tearly certificate confirms exactness. Section 6 validates this behavior empirically.
5
Theoretical Analysis
5.1
Orthogonal Decomposition and the Role of the Frozen Subspace
We first show that the global squared error splits across the two subspaces. Let F denote the frozen subspace handled by classical substitution and F ⊥ the exploration subspace mapped to QUBO. Any global error vector e′ decomposes uniquely into a component parallel to F (denoted efroz = πF (e′ )) and one parallel to F ⊥ (denoted eproj (z) = πF ⊥ (e′ ), which is explicitly parameterized by the logical variables z): e′ = efroz + eproj (z).
(13)
By orthogonality the squared Euclidean norm separates additively: ∥e′ ∥2 = ∥efroz ∥2 + ∥eproj (z)∥2 .
7
(14)
Algorithm 1 CIM-BDD: Systematic Execution Flow Require: LWE instance (A, c) with A ∈ Zm×n , modulus q, standard deviation σ. q Ensure: The true error vector e and secret s. 1: Phase 1: Algebraic Isomorphism & Global Reduction 2: Randomly select m′ rows of A such that the leading n × n submatrix Atop is invertible modulo q −1 3: Compute transition matrix Tmat ← Abot Atop (mod q). 4: Apply BKZ/LLL [4] on initial CVP basis to yield integer basis B0 . 5: Inherit GSO components: B0 = B∗ Uµ . 6: Phase 2: Gram-Schmidt Projection 7: Extract the corresponding m′ -dimensional sub-target from c, lift it to c′ , and project c′ onto B∗ to obtain full continuous coefficient vector α. 8: Isolate exploration subspace: extract αexp and Uµ,exp . 9: Phase 3: Continuous Relaxed Babai’s Nearest Plane (CR-BNP) 10: Compute yc via O(d2exp ) Gaussian back-substitution: Uµ,exp yc = αexp . 11: Phase 4: Adaptive Encoding & Subspace QUBO Gen. 12: Extract continuous fractional ambiguity: δ ← yc − ⌊yc ⌉. 13: Map continuous δ into logical bits using 0/1/2-bit mappings and thresholds τlow , τhigh . 14: Formulate affine transformation: ỹexp ← ybase + Tenc z. 15: Formulate QUBO matrix Eproj (z) purely within F ⊥ . 16: Apply variable partitioning (exhaustive enumeration of K pivot bits), pack independent instances block-diagonally, and map to CIM. 17: Phase 5: Verification & Recovery 18: for each partition branch hardware sample zhw extracted from a single CIM submission do 19: Reconstruct physical displacement yexp ← ybase + Tenc zhw . 20: Compute frozen coordinates yfroz using Discrete Babai’s nearest plane algorithm. ⊤ , y⊤ ]⊤ . 21: Let candidate vector ycand = [yfroz exp 22: Evaluate global discrete energy E ← ∥c′ − B0 ycand ∥2 . 23: if E > Tearly then 24: Perform bounded neighborhood corrector (R ≤ 2) over all coordinates of ycand , each coordinate correction (±1 step) invokes Babai’s nearest plane algorithm on front indices. Update E and ycand . 25: end if 26: if E ≤ Tearly then 27: Output: Recover s ← (A−1 top (B0 ycand )top ) (mod q). 28: return s, and the global error e = (c − As) mod q 29: end if 30: end for
8
Eq. (14) is the structural basis for splitting the work between hardware and classical postprocessing. The second term, ∥eproj (z)∥2 , is confined to the exploration subspace, minimizing the QUBO energy E(z) minimizes it over the encoded domain. Conversely, for a fixed hardware assignment zopt , minimizing the total error ∥e′ ∥2 reduces to minimizing the first term ∥efroz ∥2 , a standard lower-dimensional CVP over the frozen basis Bfroz that the classical post-processor resolves by Babai’s nearest-plane algorithm. Eq. (14) holds as a continuous identity, but our modeling imposes discrete integer constraints, which may couple the two subspaces. Therefore, minimizing the total error does not strictly decouple into independent minimizations of the two terms. This is one source of the inaccuracy of our modeling.
5.2
Lattice Geometry and the Choice of Subdimension
Lemma 1 (Length of the Last Gram-Schmidt Vector). Let Λ be an m′ -dimensional q-ary lattice ′ with volume q m −n , corresponding to an LWE instance with secret dimension n. Under the Geometric Series Assumption (GSA), if the lattice is reduced by an algorithm with root-Hermite factor γH , the length of the last Gram–Schmidt vector is estimated as: n
′
∥b∗m′ ∥ ≈ q 1− m′ · γH −(m −1) .
(15)
Proof. Under the GSA heuristic, the lengths of the Gram-Schmidt vectors decay geometrically, i.e., ∥b∗i ∥ ≈ ρ i−1 ∥b∗1 ∥ with ρ = γH −2 . Since the lattice volume equals the product of these lengths, we have: m′ Y ′ ′ ′ ′ Vol(Λ) = ∥b∗i ∥ ≈ ∥b∗1 ∥m ρm (m −1)/2 = q m −n . i=1 ′
′
′
Solving for the first vector yields ∥b∗1 ∥ ≈ q 1−n/m ρ−(m −1)/2 . Substituting into ∥b∗m′ ∥ ≈ ρ m −1 ∥b∗1 ∥ and using ρ1/2 = γH −1 gives Eq. (15). Setting the derivative of Eq. (15) to zero yields an idealized GSA-optimal subdimension of m′ = 152 for our instance (Figure 1). We chose the sub-optimal point m′ = 88, which actually is a harder operating point, mainly for demonstration and stress-testing, not to maximize the recovery rate. A real attacker would tune toward larger m′ with a correspondingly stronger block size β; our choice of m′ = 88 is a conservative operating point that exposes the failureand-recovery behaviour of the pipeline, with a shorter time of BKZ reduction because larger m′ slows the BKZ, which will be a problem when considering larger instances.
5.3
Decoding Limits and Exploration Subspace Reliability
To quantify the decoding limits exclusively within the hardware-mapped exploration subspace, we first evaluate the continuous coordinate error at the last dimension using empirical values instead of the theoretical ones in Section 5.2. Because its coordinate error avoids any accumulated covariance from other variables, evaluating this dimension provides a clean baseline for our estimation. Lemma 2 (Standard Deviation of the Continuous Coordinate Error at the Last Dimension). In the CR-BNP framework, let the continuous coordinates yc solve Uµ,exp yc = αexp with the true error e ∼ DZm′ ,σ . The standard deviation of the coordinate error at the last dimension m′ evaluates to: σ σlast = . (16) ∥b∗m′ ∥ Proof. The continuous projection coefficient is αi = ⟨c′ , b∗i ⟩/∥b∗i ∥2 . Writing c′ = B∗ Uµ ytrue + e gives, on the exploration block, αexp = Uµ,exp ytrue,exp + eproj,exp with eproj,i = ⟨e, b∗i ⟩/∥b∗i ∥2 . 9
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,exp − ytrue,exp = U−1 µ,exp eproj,exp . Since Uµ,exp is upper unitriangular, so is its inverse, whose last row is a single 1 on the diagonal, thus ϵy,m′ = eproj,m′ = ⟨e, b∗m′ ⟩/∥b∗m′ ∥2 . Projecting e ∼ DZm′ ,σ onto the fixed vector b∗m′ gives Var(ϵy,m′ ) =
σ 2 ∥b∗m′ ∥2 Var(⟨e, b∗m′ ⟩) σ2 = = , ∗ ∗ ∥bm′ ∥4 ∥bm′ ∥4 ∥b∗m′ ∥2
(17)
and σlast = σ/∥b∗m′ ∥ follows. We now estimate how ternary widening removes the per-coordinate bottleneck in the exploration subspace. Claim 1 (Last Coordinate Reliability via Ternary Widening). Restricting our analysis to the exploration subspace, we take a specific randomized row-selection seed for the n = 40 configuration (m′ = 88) as a representative empirical example. Here, the Gram-Schmidt tail degrades to ∥b∗88 ∥ ≈ 15.531 (slightly below the idealized GSA prediction). By Lemma 2, the continuous coordinate error at this last dimension exhibits a standard deviation σlast ≈ 8.005/15.531 ≈ 0.515. In this exploration region, a classical single-pass nearest-plane rounding succeeds at this last coordinate only if the fractional error lies in [−0.5, 0.5], corresponding to Pr(|Z| ≤ 0.5/0.515) = 2Φ(0.971) − 1 ≈ 0.668. Assuming the last coordinate is assigned a full ternary QUBO encoding (∆y88 ∈ {−1, 0, 1}), the interval widens from ±0.5 to ±1.5. This expansion restores the per-coordinate reliability at the tail: 1.5 plast = Pr |Z| ≤ 0.515 = 2Φ(2.913) − 1 ≈ 0.9964. Claim 2 (Cumulative Coverage of the Exploration Subspace). To estimate the cumulative coverage within the dexp = 12 exploration subspace, we formulate a probabilistic projection under three assumptions: (1) per-coordinate statistical independence; (2) the last-dimension probability plast uniformly applies across all exploration dimensions; and (3) every coordinate is universally granted a full ternary encoding. Under these conditions, the theoretical cumulative coverage within the exploration subspace evaluates to: Pexplore ≈ (plast )12 ≈ (0.9964)12 ≈ 0.957. 10
Note that Pexplore ≈ 95.7% serves as an estimation for the actual exploration subspace coverage, because actually the coordinates are not statistically independent, the standard deviations for dimensions in the exploration space are not equal to σlast generally, and our adaptive encoder does not apply full ternary widths to all dimensions.
5.4
Early-Stopping Certificate and DLWE Distinguishing Advantage
We establish a mathematical early-stopping threshold Tearly that functions as a one-sided cryptographic certificate. We formulate a distinguisher D that evaluates the residual energy of the recovered lattice point to bound the Decision-LWE advantage. Theorem 1 (One-Sided Distinguisher and DLWE Advantage). Let D be a Decision-LWE distinguisher that executes the encoded CIM-BDD solver. On input challenge (A, c), if the solver recovers a candidate vector ycand satisfying the residual energy bound E = ∥c′ − B0 ycand ∥2 ≤ Tearly , the distinguisher outputs 1 (guessing LWE). Otherwise, it defaults to outputting 0 (guessing Uniform). The threshold is analytically defined as: √ Tearly = m′ σ 2 + 4σ 2 2m′ . (18) Let psucc denote the solver’s operational probability of correctly locating the true LWE error vector. The standard distinguishing advantage AdvDLWE (D) = | Pr[D(LWE) = 1] − Pr[D(Uniform) = 1]| is lower-bounded by: AdvDLWE (D) ≥ psucc · (1 − αtail ) − ϵvol , (19) √ where αtail is the statistical right-tail probability of a χ2m′ distribution evaluated at m′ + 4 2m′ , p and ϵvol = Vol Bm′ ( Tearly ) / det(Λq ) is the volumetric false-acceptance bound derived from the lattice Gaussian Heuristic. Proof. (i) Evaluation on True LWE Instances (Pr[D(LWE) = 1]): Normalizing Xi = ei /σ, the P ′ 2 P 2 ′ ′ 2 true-point energy is E = ∥e∥2 = σ 2 m i=1 Xi , with i Xi ∼ χm′ (mean m , variance 2m ). ′ 2 ′ 4 Hence E[E] = m σ and Var(E) = 2m σ . Placing √ the threshold four standard deviations above 2 ′ the mean gives Eq. (18), i.e. Tearly /σ = m + 4 2m′ . The mathematical probability that the true planted error stochastically violates this generous threshold is bounded by the analytic tail √ 2 ′ ′ αtail = Pr[χm′ > m +4 2m ]. Since the algorithm empirically locates this true lattice point with probability psucc , the joint probability of outputting 1 is well approximated by psucc · (1 − αtail ). (ii) Evaluation on Uniform Instances (Pr[D(Uniform) = 1]): A uniform random target ′ u ∼ U(Zm outputs 1 only if a wrong lattice q ) contains no planted error. The distinguisher p point accidentally falls within the Euclidean ball Bm′ ( Tearly ) centered at the target. By the Gaussian Heuristic, the expected number of such lattice p points asymptotically upper-bounds this probability: Pr[D(Uniform) = 1] ≤ ϵvol = Vol(Bm′ ( Tearly ))/ det(Λq ). (iii) Distinguishing Advantage: Substituting these bounds yields AdvDLWE (D) = Pr[D(LWE) = 1] − Pr[D(Uniform) = 1] ≥ psucc · (1 − αtail ) − ϵvol .
This early-stopping threshold Tearly serves as a one-sided statistical certificate: crossing below Tearly certifies the secret, whereas failing to cross is uninformative as to whether the target was LWE or uniform. It gives a search-to-decision distinguisher, whose advantage approximately equals the search success probability. For Search-LWE, the certificate accelerates verification that could also be done by recomputing s; for Decision-LWE, a uniform instance has no secret to recompute, so the threshold-crossing event is the only available distinguisher.
11
6
Experiments and Evaluation
All experiments are conducted on CPQC-550 at the Coherent Ising Machine platform through the Kaiwu SDK [25], with all instances drawn from the TU Darmstadt LWE Challenge [26].
6.1
Toy Instance Validation
Although the toy instances could be solved directly using the modeling in Section 3, to validate the pipeline presented in Section 4 — the CR-BNP projection, the adaptive mixed-radix encoder, the block-diagonal variable partitioning, and the bounded corrector (R ≤ 2) — we route the n = 5 instance (m′ = 12, q = 29, σ ≈ 0.29) through every stage with an exploration subspace of dexp = 8. Setting τlow = 0.05 and τhigh = 0.20, the encoder collapses the search space into √ 4 logical 2 ′ 2 2 ′ bits (0-bit:6, 2-bit:2), with √ a χ early-stopping threshold Tearly ≈ 2.7 from m σ + 4σ 2m = 12(0.0841) + 4(0.0841) 24 ≈ 2.6562. A single CIM submission returns four distinct results (Table 1). Samples #1 and #2 (lowest EQUBO = −434) are the discrete ground state directly (Etotal = 1), #3 and #4 are pseudominima whose true lattice energy reaches Etotal = 73 and 162, and the bounded corrector pays this gap at R=1 and R=2, all landing on the same ground state E=1 < Tearly = 2.7. The pipeline recovers the secret s = (7, 27, 14, 23, 26). The same submission yields both direct ground states and pseudo-minima: the framework requires only that the ground state lie within the R ≤ 2 neighborhood of some returned candidate, a weaker requirement than other schemes that treat QUBO bit-strings as literal ground states. Note that the two-bit map represents the ternary step set {−1, 0, +1} with four bit-strings, so the central value is doubly encoded. This is a deliberately redundant, sign-symmetric encoding: it keeps the search window centered from the Babai’s algorithm at the cost of one redundant code-point, and it induces a ground-state degeneracy. For instance, samples #1 and #2 in Table 1 are distinct bit-strings of equal energy. Table 1: Results of LWE_5_010 (q = 29, σ ≈ 0.29). Four distinct results from a single CIM submission. Eproj is the continuous-relaxation energy (what the QUBO minimizes), EQUBO is the Ising objective (an affine image of Eproj , not a lattice energy), Etotal is the true integer lattice energy. Samples #1–#2 (lowest EQUBO ) are the discrete ground state directly, #3–#4 are the pseudo-minima (Etotal = 73, 162) which the bounded corrector (R ≤ 2) rescues, all recovering the same ground state E=1, below the χ2 certificate Tearly = 2.7. Sample
Source
Bitstring
EQUBO
Eproj
Etotal
Corrector
#1 #2 #3 #4
Res:0 Res:1 Res:2 Res:3
[0, 1, 0, 1] [1, 0, 1, 0] [1, 0, 0, 0] [1, 1, 1, 1]
−434 −434 −216 +116
0.76 0.76 59.92 150.06
1 1 73 162
R=0 (direct) R=0 (direct) R=1 on dim07 → E=1 R=2 on dim07 , dim04 → E=1
Remark. This instance (LWE_5_010) could be solved by the modeling in Section 3 alone, since classical Babai’s nearest-plane (only use LLL) already finds the solution (∆y = 0). We use it instead to trace the Section 4 procedure end-to-end, the exploration-subspace division also illustrates the encoder’s qubit reduction relative to modeling the full instance. Preprocessing here requires only LLL reduction rather than BKZ-20.
6.2
Validation at n = 40 (LWE_40_005): Multi-Seed Study
At n = 40 with m′ = 88 and BKZ-20 (or even BKZ-30) reduction, a single pass of Babai’s nearest-plane algorithm fails to recover the correct lattice point, yielding baseline residuals of 12
order 6 × 104 , several-fold above the χ2 threshold Tearly = 9040. Holding the LWE_40_005 instance and all algorithmic parameters fixed, we vary only the random seed that selects an Atop invertible modulo q, yielding 11 row partitions (seed ∈ {42, 1, 2, . . . , 10}) of the same underlying LWE problem. Each seed is evaluated under two reduction strengths: Baseline single-pass BKZ-20 and Progressive BKZ-20 → 30. For each seed, CR-BNP isolates dexp = 12 exploration dimensions, the adaptive encoder with τlow = 0.05 and τhigh = 0.20 compresses them into 10– 19 logical bits depending on the empirical δ distribution, and variable partitioning splits the instance into 32 block-diagonal branches aggregated into one submission. Table 2 summarizes the results. Baseline BKZ-20 recovers the secret on 2 of 11 seeds (18%; 3 hits in total); progressive BKZ-20 → 30 doubles this to 4 of 11 (36%; 21 hits). On every successful seed, the residual energy follows a consistent descent: EBabai ∼ 4 × 104 –6 × 104 (single-pass nearest-plane, several-fold above Tearly ) → ER=0 ∼ 4 × 104 –7 × 104 (CIM continuous pseudominimum evaluated on the discrete lattice) → Efinal ∈ [5,270, 6,509] (post-corrector discrete ground state), spanning roughly one order of magnitude. Specifically, because each randomized minimal row selection extracts a distinct m′ -dimensional subset of the global discrete Gaussian error, the true ground-state energies naturally fluctuate per seed. The empirically resolved Efinal values tightly cluster around the theoretically expected residual energy µE = m′ σ 2 ≈ 5,639 and successfully get through the early-stopping threshold Tearly = 9,040, confirming an exact cryptographic lattice point recovery. The estimated single-pass success probability for each seed could be calculated as Pcomp = Pfroz × Pexplore . As established in Claim 2, the ternary widening inherently pushes Pexplore ≈ 95.7%,h isolating mathematical bottleneck to the frozen subspace limit: Pfroz = ∗ the system’s i Q76 ∥bi ∥/2 − 1 . For baseline BKZ-20, the theoretical mean P comp = 18.0% agrees with i=1 2Φ σ our empirical recovery of 18.18% (2/11). Under progressive BKZ-20→30 reduction, the empirical recovery rises to 36.36% (4/11), higher than the 26.5% mathematical expectation. We read the two as consistent in magnitude rather than as a statistically significant gap; the modest excess is the expected signature of the corrector, while under the weak BKZ-20 baseline, the corrector doesn’t help much due to the poorly reduced basis. One specific seed (seed=4) succeeds under baseline BKZ-20 but fails under BKZ-20 → 30. This occurs because the stronger reduction shifts the δ-encoding distribution. So BKZ-30 is beneficial for most seeds but occasionally adversarial for an individual instance. The most informative single run is seed=7, the only seed that recovers the secret under both BKZ configurations, at the identical post-corrector energy Efinal = 5,270: the same cryptographic ground state reached via two different lattice geometries. For the hardware time, we observed the single batched tCIM stays in the millisecond regime (0.24–17.36 ms across the 22 runs), and did not observe a correlation between time and block size. Also, tCIM carries no information about recovery: the fastest run overall (0.24 ms, seed 10/baseline) fails, a comparably fast run (0.39 ms, seed 5/progressive) succeeds, and the slowest (17.36 ms, seed 42/baseline) fails. Recovery is also stable under small changes of the exploration dimension. Repeating the baseline study with dexp = 11 (all else fixed) gives an essentially identical outcome, with the same two seeds succeeding (seed=4, seed=7, 18%) at the same post-corrector energies Efinal = 6,509 and 5,270, recovering the same secret and agreeing on the failing seeds.
6.3
Decision-LWE (DLWE) Validation
We now instantiate the theoretical bounds of Theorem 1 using the specific n = 40 configuration (m′ = 88, σ = 8.005). The early-stopping certificate threshold evaluates to Tearly = 9040, the theoretical right-tail probability is αtail ≈ 2.85 × 10−4 , and the theoretical Gaussian Heuristic volume limits the volumetric false-acceptance bound to ϵvol ≈ 5 × 10−13 . To validate the distinguishing advantage AdvDLWE (D), we evaluate the empirical acceptance 13
Table 2: Multi-seed robustness study on LWE_40_005 (n = 40, m′ = 88, q = 1601, Tearly = 9040). Each row is an independent run differing only in the random seed for row selection. For each reduction we report Nlog , the number of logical qubits in QUBO; tCIM , the wall-clock time of a single CIM submission; the per-seed analytic success rate Pcomp ; and the final outcome. For the baseline we also list Efinal , the post-corrector residual energy; for the progressive run, δ-valid, whether the encoder covers the true solution within {0, ±1} steps per dimension. The ensemble mean of Pcomp predicts the recovery rate. seed
Baseline BKZ-20 Nlog Efinal tCIM (ms) Pcomp
42 1 2 3 4 5 6 7 8 9 10
15 17 15 12 15 17 16 15 15 11 13
Summary
27,070 26,944 24,880 27,537 6,509 26,712 27,938 5,270 28,885 25,502 27,953
17.36 0.80 9.99 0.60 0.41 6.83 5.28 9.42 10.22 0.91 0.24
Outcome
0.189 0.169 0.181 0.184 0.170 0.200 0.179 0.191 0.178 0.151 0.188
fail fail fail fail break fail fail break (2 hits) fail fail fail
P comp =0.180
2/11=18%
Progressive BKZ-20 → 30 δ-valid Nlog tCIM (ms) Pcomp Outcome ✓ ✓ × × × ✓ ✓ ✓ × × ×
16 17 13 17 15 10 19 14 12 12 11
9.30 8.82 0.93 8.26 3.08 0.39 9.62 0.56 0.87 0.77 0.55
0.278 0.267 0.306 0.260 0.272 0.248 0.288 0.224 0.267 0.247 0.257
break (5 hits) fail break (E = 5,778) fail fail break (13 hits) fail break (2 hits) fail fail fail
P comp =0.265
4/11=36%
probabilities based on the event {E ≤ Tearly }: As demonstrated in Section 6.2, successfully solved LWE seeds drive the residual energy below Tearly (e.g., Efinal ∈ [5,270, 6,509]). However, when the solver fails, it yields a residual energy overlapping the ∼ 2.5–2.9 × 104 range. Because these failed instances miss the threshold, the distinguisher defaults to 0. Consequently, the empirical probability of outputting 1 on an LWE target is bounded by the algorithmic recovery rate: Pr[D(LWE) = 1] = psucc · (1 − αtail ) ≈ psucc . To validate the null hypothesis, we generated N = 220 independent uniform-random targets ′ crand ∼ U(Zm q ), then evaluated them using a classical lattice enumeration solver. Across all targets, zero instances crossed Tearly (the minimum global energy observed was 28,564, far above the threshold, as plotted in Figure 2). The single hardware (CIM) control run is consistent with this (Erand = 28564). This confirms the theoretically negligible estimation (ϵvol ≈ 5 × 10−13 ). Substituting the empirical boundaries into Theorem 1, the DLWE distinguishing advantage of the CIM-BDD framework evaluates to the algorithmic recovery rate: AdvDLWE = Pr[D(LWE) = 1] − Pr[D(Uniform) = 1] ≈ |psucc − 0| = psucc . This yields an absolute single-shot distinguishing advantage of 0.18 (under baseline BKZ-20) and 0.36 (under progressive BKZ-20→30). Amortizing over k independent row-selection seeds, the advantage robustly amplifies to 1 − (1 − psucc )k .
7
Computational Complexity and Scalability
Table 3 positions our framework against representative families of quantum-assisted lattice cryptanalysis. The two metrics which scale far better than competing NISQ frameworks are qubit economy and hardware call count. HAWI demonstrates DLWE on n = 2 (a 5-qubit instance) with a qubit budget scaling as ≤ m(m+1) = O(m2 ) and on the order of 104 shots per expectation value, while Lv et al. [22] estimate (by resource counting rather than on hardware) about 1,126 logical qubits for an n = 40 uSVP attack, rising to 13,768 at KYBER-512 scale (n = 256). Our framework attacks n = 40 on real hardware with fewer than 20 logical qubits and a single hardware call with a 36% success probability under progressive BKZ-20→30. 14
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 recovered), 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. Progressive BKZ-20 → 30 raises the solved fraction from 2/11 to 4/11. The threshold separates solved from unsolved : only solved seeds cross it, while failed-LWE and uniform targets are both ≫ Tearly . Energy magnitude above the threshold is not discriminative, the operative signal is the binary crossing event.
7.1
Asymptotic Complexity Analysis
Decomposing the end-to-end pipeline, the total time complexity is Ttotal =
T | BKZ {z }
global reduction
+ O(d2exp ) + O(dexp ) + O(1) + | {z } | {z } | {z } CR-BNP
encoder
CIM call
O(m′4 ) | {z }
.
(20)
bounded corrector (R≤2)
The BKZ preprocessing TBKZ scales as exp(O(β)) where β is the BKZ block size. The explorationsubspace operations (CR-BNP back-substitution and the adaptive encoder) are at most quadratic in dexp (< 15 in our instances). The CIM call is a single evaluation exhibiting constant-time ′ scaling. The bounded corrector iterates over m2 pairs, each evaluation requires an O(m′2 ) matrix-vector energy reassembly plus an O(dfroz · m′ ) Babai’s nearest plane at the front-end. For our n = 40 configuration (m′ = 88, dexp = 12), the time of the bounded corrector is negligible against TBKZ , so the end-to-end wall-clock is dominated by TBKZ , not by the hardware-side operation. Empirically, the single batched CIM submission on the encoded n = 40 instance takes 0.4–9.3 ms (progressive BKZ-20 → 30) across the four successful seeds of Section 6.2, with logical bit-widths Nlog ∈ {10, 13, 14, 16} produced by the adaptive encoder. The batched tCIM stays two to four orders of magnitude below the classical reduction time TBKZ (of order 103 ms for the progressive schedule). We also timed the optimized C++ fplll solver (CVP.closest_vector, Schnorr–Euchner enumeration) on the full encoded dexp = 12 exploration sub-lattice (frozen subspace fixed by Babai): it averages 0.86 ms, i.e. the CIM is not faster than classical enumeration at the 12-dimension scale. The expectation is that the constant running time of the CIM manifests a scaling advantage as dexp grows past the point where exhaustive enumeration becomes infeasible.
15
Table 3: Comparison of quantum-assisted attacks on LWE/SVP along qubit count and hardwarecall count. These two axes are where the present co-design differs most from prior NISQ frameworks. Notes: for Lv [22], the qubit figure is a resource estimate at n = 40 (its actual hardware demonstration is a 3-qubit toy instance) and its VQE results are simulation-based; for Qayyum [20, 21], the qubit count is a theoretical upper bound (Prop. 1/2) and the experiments are classical MIP solves rather than runs on a quantum annealer; for Joseph [19], “dim” refers to the quantum SVP simulation. Method
Target
Demo. n
Qubits
HAWI [23] Qayyum [20, 21] Joseph [19] Dable-Heath [24] Lv [22]
DLWE SLWE & SIS SVP SVP SLWE→uSVP
n = 2 (HW) n ≤ 6 (MIP) dim ≤ 4 (sim.) dim ≤ 7 (sim.) n ≤ 5 (sim.)
≤ m(m+1) None (m sub-models) Gradient descent (∼ 10 iters) ∼ 104 shots (QAOA) O(mnq) (slack-heavy) Explicit (slack vars) QUBO/annealing (proposed) est. only O(N log N ) None (1st excited state) Sub-adiabatic sweep repeated O(n log n)–O(n5/2 ) (enc.-dep.) Restricted qubit (n sub-models; 1 cyclic) CIM-CFC sampling ∼ 103 runs/inst. (sim.) ∼1126 (est., n=40) Explicit Variational loop sim. only
C++ fplll Enum. CVP n = 40 (Exact) N/A This work SLWE & DLWE n = 40 (HW) ≤19 (Logical)
7.2
Penalty
None None
Opt. Loop Scaling
O(2d ) · O(d2froz ) + O(TBKZ ) O(TBKZ )
HW calls
N/A 1 batched submission
Scalability to Cryptographic Dimensions
Scaling beyond n = 40 is an open direction that may require coordinated adjustments: extending the subspace of the exploration area; widening the search radius (e.g., extending the ternary domain ±1 to ±2, ±3, . . . via wider mixed-radix mappings); replacing the classical Babai nearest-plane in the frozen subspace with a Lindner–Peikert Nearest Planes enumeration [6]; and enlarging the BKZ block size to improve basis orthogonality. We leave these for future work. We also emphasize that this hybrid framework does not alter the fundamental asymptotic hardness of LWE. As Eq. (20) shows, the global complexity is dominated by the classical BKZ preprocessing, which scales as exp(O(β)).
8
Conclusion
We presented CIM-BDD, a hybrid BDD solver for the Search and Decision variants of LWE. Its core is a strictly penalty-free QUBO mapping (Section 3): an algebraic elimination of the secret absorbs the modulus into a primal q-ary lattice and recasts LWE as a Closest Vector Problem (especially BDD), then uses the Babai-recentered least-squares residual directly as the QUBO energy. The cryptographic noise thus becomes the objective rather than a penalized constraint. To fit the NISQ hardware (Section 4), we use a CR-BNP-driven adaptive 0/1/2-bit encoder, block-diagonal partitioning over the most ambiguous coordinates to make full use of the hardware capacity, a R ≤ 2 corrector as a deterministic correction layer, and the early-stopping threshold Tearly acts as a one-sided certificate, to recover the secret from the approximate relaxation. On the TU Darmstadt LWE Challenge at n = 40 (q = 1601, σ = 8.005) with m′ = 88, single-pass Babai fails, whereas the CIM-plus-corrector pipeline recovers the secret on 2 of 11 row-seeds (3 hits) under baseline BKZ-20 and on 4 of 11 (21 hits) under progressive BKZ20 → 30, each in a single millisecond-scale submission. Since each seed attacks the same secret and carries a one-sided certificate, the attack stops at the first crossing, so the expected number of reductions for progressive BKZ-20→30 is 1/0.36 ≈ 3. The cumulative recovery probability 1 − (1 − 0.36)k reaches 83% by k = 4 and exceeds 98% by k = 10 with independent seeds reducible in parallel. The whole modeling takes only Nlog ≤ 19 logical bits. Beyond raw recovery rates, the CIM contributes a robust recovery mechanism: each submission returns an ensemble of low-energy configurations, and the R ≤ 2 corrector succeeds whenever the true point lies in the neighborhood of any of them—a weaker condition than requiring a single exact ground-state bitstring. Its batched submission time stays constant in the millisecond regime (here 0.24–17.4 ms) irrespective of logical bit-width, while the end-to-end cost remains dominated by classical BKZ. In conclusion, this work provides a methodological template for evaluating post-quantum security primitives on physical Ising architectures, with the role of the CIM understood as an 16
ensemble sampler of low-energy states whose practical value at cryptographic scale remains to be demonstrated. Our framework establishes a scalable foundation for tackling higher-dimensional cryptographic challenges in the future.
References [1] National Institute of Standards and Technology (NIST), “FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard”, 2024. [2] National Institute of Standards and Technology (NIST), “FIPS 204: Module-Lattice-Based Digital Signature Standard”, 2024. [3] Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography”, in Journal of the ACM, Volume 56, Issue 6, 2009 [4] A. K. Lenstra, H. W. Lenstra, and L. Lovász, “Factoring polynomials with rational coefficients”, Math. Ann., 1982. [5] L. Babai, “On Lovász’ lattice reduction and the nearest lattice point problem”, in STACS, 1985. [6] R. Lindner and C. Peikert, “Better Key Sizes (and Attacks) for LWE-Based Encryption”, in CT-RSA, 2011. [7] 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. [8] Y. Chen and P. Q. Nguyen, “BKZ 2.0: Better lattice security estimates”, Advances in Cryptology–ASIACRYPT 2011, pp. 1–20, Springer, 2011. [9] 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. [10] M. R. Albrecht, R. Player, and S. Scott, “On the concrete hardness of Learning with Errors”, J. Math. Cryptol., 2015. [11] A. Becker, L. Ducas, N. Gama, and T. Laarhoven, “New directions in nearest neighbor searching with applications to lattice sieving”, in SODA, 2016. [12] 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. [13] 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. [14] 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. [15] 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
[16] 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. [17] 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. [18] 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. [19] D. Joseph, A. Ghionis, C. Ling, and F. Mintert, “Not-so-adiabatic quantum computation for the shortest vector problem”, Phys. Rev. Res., 2020. [20] A. Qayyum and M. Haris, “Cryptanalysis of LWE and SIS-based cryptosystems by using quantum annealing”, Prikladnaya Diskretnaya Matematika, Supplement, pp. 117–123, 2023. [21] A. Qayyum, “Advancing LWE cryptanalysis: an updated MIP model and QUBO formulation for quantum annealing”, Prikladnaya Diskretnaya Matematika, pp. 194–200, 2025. [22] 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. [23] 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. [24] E. Dable-Heath, L. Casas, V. Hertz, C. Porter, F. Mintert, and C. Ling, “Quantum algorithmic solutions to the shortest vector problem on simulated coherent Ising machines”, arXiv preprint arXiv:2304.04075v3, 2023. [25] Kaiwu SDK, https://kaiwu-sdk-docs.qboson.com/en/. (2022). [26] 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 primal q-ary lattice Λq (A) is often defined using a generating matrix [A | qI]. However, this generating matrix is linearly dependent, so we further construct a fullrank, lower-triangular integer basis for the lattice. Given the primal LWE matrix A ∈ Zm×n and the target vector c ∈ Zm q q , we randomly ′ sample an m -dimensional subset of equations (n < m′ ≤ m). Let this sampled sub-problem be ′ ×n ′ represented by the matrix A′ ∈ Zm and the corresponding sub-target vector be c′ ∈ Zm q q . Algebraic Elimination of the Secret. To construct the basis for Λq (A′ ), we partition the ′ sub-matrix A′ and any corresponding valid lattice vector v ∈ Λq (A′ ) ⊂ Zm into a top block of dimension n and a bottom block of dimension m′ − n: Atop vtop ′ A = , v= . (21) Abot vbot We enforce that the leading n × n submatrix Atop is invertible modulo q, resampling the m′ rows if this condition fails. By the definition of the q-ary lattice, any valid lattice vector v evaluated modulo q must satisfy the congruence relation v ≡ A′ s (mod q) for some secret s ∈ Znq . Decomposing this congruence yields: vtop ≡ Atop s
(mod q),
(22)
vbot ≡ Abot s
(mod q).
(23)
Because Atop is explicitly chosen to be invertible over Zq , we can uniquely express the hidden cryptographic variable s from Eq. (22): s ≡ A−1 top vtop
(24)
(mod q).
Substituting Eq. (24) into Eq. (23) eliminates the secret s entirely, yielding a deterministic algebraic constraint between the top and bottom coordinates of any valid lattice point: vbot ≡ Abot (A−1 top vtop ) ≡ Tmat vtop (m′ −n)×n
where Tmat = Abot A−1 top (mod q) ∈ Zq
(25)
(mod q),
acts as the transition matrix. ′
Basis Construction. To lift this modular congruence into the discrete integer domain Zm , ′ we introduce an arbitrary integer vector k ∈ Zm −n to absorb the modulo q. This converts the congruence into an integer equality: (26)
vbot = Tmat vtop + qk. ′
This establishes a necessary and sufficient condition: a point v ∈ Zm mathematically belongs to the lattice Λq (A′ ) if and only if it can be parameterized by arbitrary free integer variables ′ vtop ∈ Zn and k ∈ Zm −n as follows: In×n 0n×(m′ −n) vtop vtop vtop v= = = . (27) vbot Tmat vtop + qk Tmat qI(m′ −n)×(m′ −n) k | {z } Binit
⊤ , k⊤ ]⊤ immediately provides the Extracting the coefficients of the free integer vector [vtop ′ ′ explicit block matrix representation of the initial lattice basis Binit ∈ Zm ×m . Binit is a full-rank integer basis ready to be globally reduced by BKZ/LLL algorithms into B0 .
19
B
Detailed Algebraic Formulations and Execution Pipeline
This appendix provides mathematical formulations in the CIM-BDD framework, progressing sequentially from global preprocessing to cryptographic recovery. Algorithm 1 synthesizes the step-by-step mathematical flow.
B.1
Pre-processing and Hardware Embedding(Algorithm Phases 1–4)
Step 1: Algebraic Isomorphism and Global Reduction. Given the primal LWE matrix A ∈ Zm×n and the target vector c ∈ Zm q q , we perform randomized trials to uniformly sample an ′ m -dimensional subset of rows without replacement. We enforce that its leading n × n submatrix Atop ∈ Zn×n is invertible modulo q, resampling the subset if this condition fails. The transition q (m′ −n)×n
matrix is computed algebraically as Tmat ≡ Abot A−1 . top (mod q) ∈ Zq This isomorphism systematically constructs the primal q-ary lattice Λq (A). Any valid lattice vector v ∈ Λq (A) satisfies the modulo relation vbot ≡ Tmat vtop (mod q). By expressing this modular congruence as an integer linear combination vbot = Tmat vtop + q · k for some arbitrary ′ integer vector k ∈ Zm −n , we explicitly formulate the block lower-triangular CVP basis Binit ∈ ′ ′ Zm ×m as the block matrix: ′ ′ In×n 0n×(m′ −n) Binit = ∈ Zm ×m . (28) Tmat q · I(m′ −n)×(m′ −n) Applying global lattice reduction (e.g., BKZ) performs integer unimodular transformations on ′ ′ Binit , yielding the highly orthogonalized integer basis B0 ∈ Zm ×m . The target vector maps unchanged as a target point c′ . Step 2: Gram-Schmidt Projection and Orthogonal Slicing. Global lattice reduction implicitly maintains the Gram-Schmidt Orthogonalization (GSO), decomposing the integer basis ′ ′ into continuous real matrices: B0 = B∗ Uµ , where B∗ ∈ Rm ×m is the orthogonal basis matrix, ′ ′ and Uµ ∈ Rm ×m is the upper unit-triangular matrix (Uµ [i, i] = 1). To construct an analytically uncoupled orthogonal coordinate we project the discrete P system, ′ ∗ , where α ∈ Rm′ is the α b target c′ onto the continuous orthogonal basis B∗ . Let c′ = m j=1 j j ⟨c′ ,b∗ ⟩
continuous projection coefficient vector, αi = ∥b∗ ∥i2 ∈ R ∀i ∈ {1, . . . , m′ }. i To geometrically decouple the exploration zone (the trailing dexp dimensions, denoted as the orthogonal complement subspace F ⊥ ), we extract the residual continuous target projection αexp ∈ Rdexp and the bottom-right submatrix Uµ,exp ∈ Rdexp ×dexp . Because Uµ is structurally upper-triangular, this trailing continuous subspace is decoupled from low-index variables. Step 3: Continuous Relaxed Babai’s Nearest Plane (CR-BNP). We apply a continuous relaxation by suspending the discrete rounding operations to locate the continuous intersection point within F ⊥ . This translates to solving the continuous upper-triangular linear system Uµ,exp yc = αexp to obtain the relaxed fractional coordinates yc ∈ Rdexp . By expanding the i-th row of this linear system, we directly obtain the O(d2exp ) Gaussian back-substitution formula: dexp
(yc )i +
X
dexp
Uµ,exp,i,j · (yc )j = αexp,i
=⇒
j=i+1
(yc )i = αexp,i −
X
Uµ,exp,i,j · (yc )j .
(29)
j=i+1
We then establish a discrete integer center ycenter = ⌊yc ⌉ ∈ Zdexp . The alignment error is isolated as the continuous fractional ambiguity δ = yc − ycenter ∈ [−0.5, 0.5]dexp , which dictates the subsequent physical hardware mapping.
20
Step 4: Adaptive Encoding and Subspace QUBO Formulation. Transfer the continuous subspace (R) back into the discrete domain (Z) for hardware execution. Let z ∈ {0, 1}Nlog denote the logical binary variables evaluated by CIM. Based on the magnitude and sign of the continuous ambiguity δ, an adaptive encoder constructs a non-negative integer step-size encoding matrix Tenc and a deterministic base shift vector offsetenc , governed by empirical thresholds τlow , τhigh : • 0-Bit (|δi | < τlow ): We fix offsetenc,i = 0, appending no columns to Tenc . • 1-Bit (|δi | ≥ τhigh ): A single bit explores the most likely adjacent integer. We fix offsetenc,i = 0, and append one column containing the value sgn(δi ) to Tenc . • 2-Bit (τlow ≤ |δi | < τhigh ): To symmetrically explore the local integer neighborhood {−1, 0, 1}, we explicitly set a negative shift offsetenc,i = −1, and append two independent columns to Tenc with the value +1. The absolute search floor is fixed as ybase = ycenter + offsetenc ∈ Zdexp . Consequently, the candidate displacement vector generated by the hardware is constrained to the integer lattice domain: ỹexp = ybase + Tenc z ∈ Zdexp To construct a QUBO landscape, we evaluate the true squared Euclidean distance in the orthogonal continuous space. The coordinate continuous error relative to the basis B∗ is ∆ = αexp − Uµ,exp ỹexp ∈ Rdexp . Because orthogonal basis vectors have varying non-unit lengths, computing the true Euclidean norm requires weighting each squared coordinate error ∆2i by its squared basis length ∥b∗i ∥2 . Let Dexp = diag(∥b∗m′ −dexp +1 ∥2 , . . . , ∥b∗m′ ∥2 ) ∈ Rdexp ×dexp be the continuous diagonal weighting matrix. The penalty-free continuous energy Eproj (z) ∈ R≥0 optimized by QUBO evaluates to: dexp
Eproj (z) =
X
∆2i ∥b∗m′ −dexp +i ∥2 = ∆⊤ Dexp ∆
i=1
= (αexp − Uµ,exp ỹexp )⊤ Dexp (αexp − Uµ,exp ỹexp )
(30)
= (αexp − Uµ,exp (ybase + Tenc z))⊤ Dexp (αexp − Uµ,exp (ybase + Tenc z)) . Before mapping to the physical hardware, the derived continuous external fields and couplings are linearly scaled independently for each sub-QUBO into the 8-bit signed integer range supported by the CIM.
B.2
Post-Processing and Verification (Phase 5)
Step 5: Frozen-Subspace Babai’s Nearest Plane. Upon hardware convergence, the CIM returns a discrete bitstring zhw ∈ {0, 1}N . The true lattice displacement in the exploration zone is reconstructed as an integer vector yexp = ybase + Tenc zhw ∈ Zdexp . Substituting this configuration into the global lattice, a classical Babai’s Nearest Plane sequentially computes the ′ compensatory frozen integer coordinates yfroz ∈ Zm −dexp over Bfroz , subject to the dynamically ′ updated integer target cfroz = c′ − B0,exp yexp ∈ Zm . Step 6: Bounded Corrector and Secret Recovery. Concatenating the segments yields ⊤ , y⊤ ]⊤ ∈ Zm′ . The global discrete residual the global discrete candidate vector ycand = [yfroz exp energy is E = ∥c′ − B0 ycand ∥2 . If E > Tearly , the deterministic bounded corrector (R ≤ 2) operates on the full candidate vector to search adjacent integer assignments. Upon successfully capturing an energy state E ≤ Tearly , the noise-free lattice vector v = ′ B0 ycand ∈ Zm is verified. Finally, the true LWE cryptographic secret s ∈ Znq is algebraically recovered by solving s ≡ A−1 top vtop (mod q). 21