Learning With Errors 问题

形式陈述

LWE 不是一个只由“带小噪声的线性方程”描述的单一问题，而是一族带参数的平均情形问题。固定维数 $n$ 、模数 $q\ge 2$ 、样本数 $m$ ，以及定义在有限环 $\mathbb Z_q$ 上的误差概率分布 $\chi$ ；只有 $q$ 为素数时， $\mathbb Z_q$ 才同时是域。标准均匀秘密版本先采样一次

s\leftarrow U(\mathbb Z_q^n),

随后对 $i=1,\ldots,m$ 独立采样

a_i\leftarrow U(\mathbb Z_q^n),\qquad e_i\leftarrow\chi,\qquad b_i=\langle a_i,s\rangle+e_i\pmod q.

这给出分布 $\mathsf{LWE}_{n,q,\chi,m}$ 。秘密 $s$ 在一次实验开始时采样，并在全部样本间保持不变；“均匀秘密”说的是它的实验分布，不是每条样本重新抽取秘密。小秘密、二元秘密或固定未知秘密是其他版本，必须把秘密分布或量词另行写进问题定义。

搜索 LWE 接收 $(a_i,b_i)_{i=1}^m$ 并要求恢复这次实验中的 $s$ 。判定 LWE 则要求区分上述联合分布与 $m$ 个独立均匀对

(a_i,u_i)\leftarrow U(\mathbb Z_q^n\times\mathbb Z_q).

搜索与判定的等价或归约不是定义的一部分，只在特定模数、误差族、秘密分布和样本访问条件下成立。因而写“LWE 困难”时，至少要同时说明 $n,q,\chi,m$ 、搜索或判定版本，以及秘密如何产生。

直觉

把所有样本按行排成矩阵，可写成 $b=As+e\pmod q$ 。若 $e=0$ ，足够多的线性无关行通常让模线性代数直接给出 $s$ ；加入小而独立的误差后，每一行都略微偏离同一个秘密，精确消元会把这些偏差混合起来。困难性来自“同一隐藏线性结构”和“逐样本噪声”的组合，不是因为模运算或随机数本身神秘。

参数之间有真实张力。噪声相对 $q$ 太小，攻击者可能更容易辨认线性关系；噪声太大，基于 LWE 的解密又难以可靠判决。统一的安全尺度因此必须协调维数、模数、样本预算与误差分布，而不能把其中某一个数值单独叫作“安全参数”。

困难性归约的范围

Regev 的原始结果使用特定的离散化高斯误差族，而不是任意“窄分布”。在常见表述中，令误差率为 $\alpha$ ，要求 $\alpha q>2\sqrt n$ ；若相应参数的 LWE 可被高效求解，则存在量子算法近似求解某些最坏情形格问题，例如 $\mathsf{GapSVP}$ 与 $\mathsf{SIVP}$ ，近似因子量级为 $\widetilde O(n/\alpha)$ 。模数范围、成功概率以及搜索—判定转换仍须按所引用的定理版本补全。

这条结论的方向是“平均情形 LWE 求解器推出最坏情形格算法”，所以格问题在该近似尺度上的困难性为 LWE 提供条件性依据。它既没有覆盖任意 $q$ 、任意 $\chi$ 和任意秘密分布，也没有断言每组能运行的工程参数都自动继承同一归约。后续经典归约改变了若干条件与参数变换，应以各自定理单独引用，不能把“经典”二字补到 Regev 原始量子归约上。

例子与边界

取玩具参数 $q=11$ 和秘密 $s=(2,4)$ 。样本 $a_1=(3,1),e_1=1$ 给出 $b_1=0$ ，而 $a_2=(1,2),e_2=-1$ 给出 $b_2=9$ 。若忽略噪声，把这两条关系硬当作精确方程求解，得到的是 $(7,1)$ 而非真正的 $s$ ；例子展示了误差如何破坏直接消元，不提供任何安全尺度。实际参数要大得多，并由攻击成本和解密失败分析共同选择。

LWE 的搜索版与判定版在适当参数下相关，但结论需注明分布和模数条件。实现中误差采样偏差、模约简、侧信道和参数复用都可能破坏理论保证；“加入任意随机噪声”不自动得到 LWE 安全。

LWE 也不同于普通实数线性回归。这里的观测在 $\mathbb Z_q$ 上回绕，误差按密码学规定的离散分布产生，目标是恢复秘密或区分整个样本分布；统计估计里的均方预测误差并不是这两个计算问题的成功条件。

推论与应用

阅读 LWE 时应始终分开三层。本页“形式陈述”固定 search/decision 问题族；“困难性归约的范围”说明最坏情形格问题如何为特定参数的平均情形 LWE 提供条件性依据；进入公钥加密、密钥交换或同态加密后，才来到具体构造层。构造还会引入密钥生成、舍入或编码、正确性间隔和新的安全归约，不能反过来充当 LWE 模型本身的定义。

Ring-LWE 与 Module-LWE 把秘密和样本放进带额外代数结构的环或模。它们能带来更紧凑的密钥和更快运算，却使用不同的问题族与归约，不能只凭名称中的 LWE 就与无结构 $\mathbb Z_q^n$ 版本交换参数或安全结论。

参考资料

Oded Regev, “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography,” Journal of the ACM 56(6), 2009；原始量子最坏情形归约及参数条件，会议版发表于 STOC 2005。
Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé, “Classical Hardness of Learning with Errors,” STOC 2013；经典归约及其独立参数范围。
Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，lattice cryptography and LWE。

形式陈述 ​

困难性归约的范围 ​

反向链接

形式陈述

困难性归约的范围