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 的原始结果使用特定的离散化高斯误差族，而非任意“窄分布”。一个明确的搜索归约版本可限定为： $2\le q(n)\le\operatorname{poly}(n)$ 为整数， $0<\alpha(n)<1$ ，且 $\alpha q>2\sqrt n$ ；误差 $\bar\Psi_\alpha$ 由 $X\sim N(0,\alpha^2/(2\pi))$ 经 $\lfloor qX\rceil\bmod q$ 得到。若求解器能使用多项式数量的独立样本，在每个固定秘密上以指数接近一的成功概率、多项式时间恢复秘密，则可构造量子多项式时间最坏情形格算法，近似因子为 $\mathsf{SIVP}$ 的 $\widetilde O(n/\alpha)$ 和 $\mathsf{GapSVP}$ 的 $O(n/\alpha)$ 。原文 Theorem 3.1先归约到离散高斯采样，Lemmas 3.17、3.20 接到格问题，Lemma 4.3 连接连续与离散 LWE。

固定秘密与前面的均匀秘密版本可通过随机平移联系：均匀选择 $t\in\mathbb Z_q^n$ ，把每条样本改为 $(a,b+\langle a,t\rangle)$ ，隐藏秘密就变成均匀的 $s+t$ ；求出它后再减 $t$ 。这保留同一误差分布，但并不免除归约的成功概率和样本预算要求。

搜索主归约不要求模数为素数。原论文把判定求解器转为搜索求解器的 Lemmas 4.2、4.4 则要求多项式有界的素数模数，并分别规定区分器对秘密的量词。因而固定任意样本数 $m$ 的判定实例，不能只凭名称相同就套用这一搜索困难性结论。

这条结论的方向是“平均情形 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 提供条件性依据；进入公钥加密、密钥交换或同态加密后，才来到具体构造层。

Regev 加密把公开样本的随机子集和变成一位密文：正确性要检查解密间隔，安全性在 LWE 替换后还需剩余哈希的熵余量。GSW进一步组织成近似特征向量矩阵，通过位分解保持小系数，并逐门核算误差。构造引入的新接口和归约不能反过来充当 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；§2 式 (7)–(8)（误差族），Theorem 3.1、Lemmas 3.17、3.20、4.3（搜索归约），Lemmas 4.2、4.4（判定到搜索）。会议版发表于 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。

形式陈述 ​

困难性归约的范围 ​

反向链接

形式陈述

困难性归约的范围