Search papers, labs, and topics across Lattice.
This paper constructs a framework for encoding small Module Learning With Errors (MLWE) instances as Quadratic Unconstrained Binary Optimization (QUBO) models, facilitating their resolution through quantum annealing. The authors analyze the stability of the optimization landscape, revealing that the noise region forms a convex polytope characterized by the QUBO energy gap between optimal and suboptimal solutions. Numerical experiments validate the framework's effectiveness in recovering secret coefficients and error vectors, while also assessing the scalability of the approach for larger MLWE instances on quantum architectures.
The stability of QUBO formulations for MLWE problems reveals a surprising convex structure that could enhance quantum optimization strategies.
Lattice-based post-quantum cryptography relies on the hardness of the Learning With Errors (LWE) and Module Learning With Errors (MLWE) problems. This work introduces a constructive framework for encoding small MLWE instances as Quadratic Unconstrained Binary Optimization (QUBO) models suitable for quantum annealing. The formulation jointly represents secret coefficients and explicit error variables within a unified binary optimization structure, enabling their simultaneous recovery from the ground-state solution. Beyond the encoding, we develop a stability analysis of the resulting optimization landscape under additive perturbations. We show that the admissible noise region forms a convex polytope defined by competing candidate secrets, and establish an equivalent characterization in terms of the QUBO energy gap between the optimal and second-best solutions. Numerical experiments on low-dimensional benchmark instances using exact simulation demonstrate correct recovery of both secret and discretized error vectors, and confirm consistency between geometric stability regions and energy-gap behavior. We further quantify the scaling of logical variables and embedding overhead with increasing MLWE dimensions to assess feasibility on quantum annealing architectures. The results establish a systematic connection between MLWE problems and quantum optimization while providing a framework for analyzing robustness properties of QUBO formulations. Although current quantum annealing hardware remains insufficient for cryptographically relevant parameters, the proposed methodology offers a structured basis for studying lattice-based problems in quantum optimization settings without implying a practical threat to standardized post-quantum schemes.
