Search papers, labs, and topics across Lattice.
This paper introduces CIM-BDD, a hybrid Bounded-Distance-Decoding solver that reformulates the Learning With Errors (LWE) problem into a Quadratic Unconstrained Binary Optimization (QUBO) problem using a penalty-free mapping. By embedding LWE into a $q$-ary lattice and minimizing cryptographic noise directly as the objective, the authors achieve significant efficiency gains for implementation on Noisy Intermediate-Scale Quantum (NISQ) devices. The proposed method is validated through an end-to-end demonstration on the TU Darmstadt LWE Challenge, showcasing its effectiveness for both Search- and Decision-LWE tasks in a 40-dimensional instance.
A penalty-free approach to LWE cryptanalysis enables efficient quantum-classical hybrid solutions that could redefine post-quantum cryptography.
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.
