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

技术摘要：模模块学习误差（MLWE）的 QUBO 建模

问题陈述
基于格的后量子密码学（PQC），特别是依赖于模块学习误差（MLWE）问题的方案，是保护系统免受量子攻击的主要候选方案。MLWE 的核心难点在于从噪声线性关系 $b = As + e \pmod q$ 中恢复隐藏的秘密向量 $s$，其中 $A$ 是公有矩阵，$e$ 是一个小的误差向量。虽然经典的格规约算法（如 BKZ）和量子增强搜索方法已被广泛研究，但在如何将秘密变量和误差变量显式编码进一个适用于量子退火的统一优化框架方面，仍存在理解上的空白。现有的公式化方法通常侧重于决策输出或消除噪声变量，缺乏用于分析解在扰动下稳定性的透明表示。

方法论
作者提出了一个用于将小型 MLWE 实例编码为二次无约束二值优化（QUBO）模型的构造性框架。该方法包含以下步骤：

1. 联合编码： 与通过边缘化处理噪声的方法不同，本研究通过单个二值向量 $z$ 显式地对秘密系数（$s$）和误差分量（$e$）进行编码。整数值通过有限位的二值展开进行表示（例如，$s_i = \sum 2^k x_{ik}$）。
2. 目标函数构建： MLWE 恢复问题被转化为残差最小化问题。对于含噪声的情况，目标函数定义为：
   $$\min_{s,e} \|As + e - b\|^2_2 + \lambda\|e\|^2_2$$
   其中 $\lambda$ 是正则化参数。通过代入二值编码，该式转化为标准的 QUBO 形式：
   $$\min_{z \in \{0,1\}^{N_{logical}}} z^\top Q z + c^\top z$$
3. 矩阵结构： 生成的交互矩阵 $Q$ 呈现块状结构：
   $$Q = \begin{bmatrix} Q_{ss} & Q_{se} \\ Q_{es} & Q_{ee} \end{bmatrix}$$
   其中 $Q_{ss}$ 表示秘密变量之间的相互作用，$Q_{ee}$ 编码噪声正则化，而 $Q_{se}$ 则捕捉秘密与噪声之间的耦合。
4. 稳定性分析： 本文对优化景观（optimization landscape）进行了稳定性分析。它将能够保持正确解的容许扰动（噪声）区域刻画为一个噪声空间中的凸多胞形，该多胞形由对应于竞争候选秘密的半空间交集定义。这种几何视角与 QUBO 基态与第一激发态之间的能量间隙（$\Delta E = E_2 - E_1$）相联系。

关键结果
作者在低维基准实例（具体为模数 $q=4$ 的 $3 \times 3$ 系统）上使用精确模拟（穷举枚举）进行了数值实验：

• 正确恢复： 在无噪声（$e=0$）和有噪声（$e \neq 0$）的情况下，QUBO 公式均成功识别了植入的秘密向量和离散化的误差向量，并将其作为唯一的全局最小值。
• 稳定性验证： 数值结果证实了几何稳定性与能量行为之间的理论联系。能量间隙保持为正值的区域与几何推导出的容许扰动的凸多胞形相吻合。
• 规模分析： 研究量化了逻辑变量的数量缩放（$N_{logical} = n\lceil \log_2 q \rceil + m\lceil \log_2 q_e \rceil$）。对于具有密码学相关性的实例（例如 $n=256, m=512$ 的类 Kyber 参数），逻辑变量数量达到约 5,120 个。
• 硬件约束： 分析强调，虽然逻辑变量的数量随维度线性增长，但由于 $A$ 的结构，生成的 QUBO 具有稠密连通性，这产生了显著的嵌入开销。这使得具有密码学相关性的实例远超当前量子退火硬件的能力范围。

意义与主张
本文将自身的贡献定位为方法论层面而非实际的密码分析威胁。作者明确指出，鉴于当前硬件在处理相关规模参数时的不足，这项工作并不意味着对标准化后量子方案构成实际威胁。

该工作的核心意义在于：

1. 统一表示： 提供了一个透明的框架，能够共同对秘密和误差进行建模，从而实现对它们在单一优化景观中相互作用的研究。
2. 鲁棒性框架： 建立了基于格的问题与量子优化之间的系统性联系，为通过几何（多胞形）和能量（间隙）视角分析 QUBO 形式的鲁棒性提供了工具。
3. 基准测试： 为在量子优化设置下研究基于格的问题建立了一个结构化基础，可作为未来混合量子-经典启发式算法或稀疏 QUBO 变体的参考。

总之，这项工作架起了基于格的密码学建模与硬件感知二值优化之间的桥梁，阐明了将 MLWE 编码进 QUBO 的理论可行性，同时也划定了当前量子退火架构所带来的实际限制。