When the Learning With Errors Problem Meets the Coherent Ising Machine: A Penalty-Free Algorithm-Hardware Co-Design
2026-06-22 • Cryptography and Security
Cryptography and Security
AI summaryⓘ
The authors introduce CIM-BDD, a new method to solve the Learning With Errors (LWE) problem, which underpins secure post-quantum cryptography. Their approach turns the LWE problem into a simpler optimization task without penalty terms and uses a special encoding to run efficiently on current quantum hardware. They also develop a way to stop early once enough information is found, which helps distinguish certain problem instances. The authors tested their method on real quantum hardware, showing it works on a 40-dimensional LWE example, combining classical and quantum techniques.
Learning With Errors (LWE)Post-Quantum CryptographyBounded-Distance-Decoding (BDD)Quadratic Unconstrained Binary Optimization (QUBO)Closest Vector Problem (CVP)Noisy Intermediate-Scale Quantum (NISQ)Coherent Ising MachineBabai's Nearest Plane algorithmDecision-LWEQuantum-classical hybrid cryptanalysis
Authors
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 \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.