QUBO Modeling of Module Learning With Errors: Stability and Scaling in Post-Quantum Cryptography

Technical Summary: QUBO Modeling of Module Learning With Errors

Problem Statement
Lattice-based post-quantum cryptography (PQC), specifically schemes relying on the Module Learning With Errors (MLWE) problem, is a leading candidate for securing systems against quantum attacks. The core difficulty of MLWE involves recovering a hidden secret vector $s$ from noisy linear relations $b = As + e \pmod q$, where $A$ is a public matrix and $e$ is a small error vector. While classical lattice reduction algorithms (e.g., BKZ) and quantum-enhanced search methods have been extensively studied, there is a gap in understanding how to explicitly encode both the secret and the error variables into a unified optimization framework suitable for quantum annealing. Existing formulations often focus on decision outputs or eliminate noise variables, lacking a transparent representation for analyzing the stability of the solution landscape under perturbations.

Methodology
The authors propose a constructive framework for encoding small MLWE instances into Quadratic Unconstrained Binary Optimization (QUBO) models. The methodology involves the following steps:

1. Joint Encoding: Unlike approaches that marginalize the noise, this work explicitly encodes both the secret coefficients ($s$) and the error components ($e$) into a single binary vector $z$. Integer values are represented via finite-bit binary expansions (e.g., $s_i = \sum 2^k x_{ik}$).
2. Objective Function Formulation: The MLWE recovery problem is transformed into a residual minimization problem. For the noisy case, the objective function is defined as:
   $$\min_{s,e} \|As + e - b\|^2_2 + \lambda\|e\|^2_2$$
   where $\lambda$ is a regularization parameter. Substituting the binary encodings converts this into a standard QUBO form:
   $$\min_{z \in \{0,1\}^{N_{logical}}} z^\top Q z + c^\top z$$
3. Matrix Structure: The resulting interaction matrix $Q$ exhibits a block structure:
   $$Q = \begin{bmatrix} Q_{ss} & Q_{se} \\ Q_{es} & Q_{ee} \end{bmatrix}$$
   where $Q_{ss}$ represents interactions among secret variables, $Q_{ee}$ encodes noise regularization, and $Q_{se}$ captures the coupling between secrets and noise.
4. Stability Analysis: The paper develops a stability analysis of the optimization landscape. It characterizes the region of admissible perturbations (noise) that preserve the correct solution as a convex polytope in the noise space, defined by the intersection of half-spaces corresponding to competing candidate secrets. This geometric view is linked to the energy gap ($\Delta E = E_2 - E_1$) between the ground state and the first excited state of the QUBO.

Key Results
The authors conducted numerical experiments on low-dimensional benchmark instances (specifically a $3 \times 3$ system with modulus $q=4$) using exact simulation (exhaustive enumeration):

• Correct Recovery: In both noiseless ($e=0$) and noisy ($e \neq 0$) settings, the QUBO formulation successfully identified the planted secret vector and the discretized error vector as the unique global minimum.
• Stability Verification: The numerical results confirmed the theoretical connection between geometric stability and energetic behavior. The region where the energy gap remained positive coincided with the geometrically derived convex polytope of admissible perturbations.
• Scaling Analysis: The study quantified the scaling of logical variables ($N_{logical} = n\lceil \log_2 q \rceil + m\lceil \log_2 q_e \rceil$). For a cryptographically relevant instance (e.g., Kyber-like parameters with $n=256, m=512$), the logical variable count reaches approximately 5,120.
• Hardware Constraints: The analysis highlights that while the number of logical variables grows linearly with dimension, the dense connectivity of the resulting QUBO (due to the structure of $A$) creates a significant embedding overhead. This places cryptographically relevant instances far beyond the capacity of current quantum annealing hardware.

Significance and Claims
The paper positions its contribution as methodological rather than a practical cryptanalytic threat. The authors explicitly state that the work does not imply a practical attack on standardized post-quantum schemes, given the insufficiency of current hardware for relevant parameter sizes.

The primary significance of the work lies in:

1. Unified Representation: Providing a transparent framework that jointly models secrets and errors, enabling the study of their interaction within a single optimization landscape.
2. Robustness Framework: Establishing a systematic connection between MLWE problems and quantum optimization, offering tools to analyze the robustness of QUBO formulations through both geometric (polytope) and energetic (gap) perspectives.
3. Benchmarking: Creating a structured basis for studying lattice-based problems in quantum optimization settings, serving as a reference for future hybrid quantum-classical heuristics or sparse QUBO variants.

In conclusion, the work bridges lattice-based cryptographic modeling and hardware-aware binary optimization, clarifying the theoretical feasibility of encoding MLWE into QUBO while delineating the practical limitations imposed by current quantum annealing architectures.