Advancing LWE cryptanalysis: an updated MIP model and QUBO formulation for quantum annealing

Lattice-based cryptography is a cornerstone of post-quantum cryptographic systems, relying on the computational hardness of problems like Learning With Errors (LWE). This study advances our prior work on LWE cryptanalysis by introducing an enhanced Mixed-Integer Programming (MIP) model and a Quadratic Unconstrained Binary Optimization (QUBO) formulation tailored for quantum annealing. Unlike our previous approach, where the error terms were fixed parameters, the updated MIP model treats these errors as variables, enabling a more flexible and accurate approximation of the LWE secret vector. The MIP model is implemented using the PuLP library in Python, demonstrating through experiments that the revised formulation maintains feasibility across various problem sizes while improving the approximation of the secret vector. Additionally, we present a QUBO model derived from the MIP, which encodes the LWE problem for potential execution on quantum annealers like D-Wave systems. This QUBO formulation, previously only outlined in conference presentations, is now formally introduced, updated, and setting the stage for future quantum implementations. Our results highlight the adaptability of the updated MIP model and the theoretical feasibility of the QUBO approach, contributing to the exploration of quantum-assisted cryptanalysis of lattice-based cryptographic primitives. This work paves the way for subsequent studies that will incorporate practical quantum annealing results to further assess the efficacy of this methodology.