形式陈述

在模数 $q$ 上选秘密 $s\in {\mathbb{Z}}_q^n$。样本为

$$(a,b=⟨a,s⟩+emodq),$$

其中 $a$ 均匀，误差 $e$ 来自窄分布。搜索 LWE 要从多项式个样本恢复 $s$；判定 LWE 要区分这些样本与均匀随机对。 参数 $n,q$ 与误差率共同决定正确性与安全性。

直觉

没有噪声时是普通线性方程；少量噪声破坏精确消元，却仍允许掌握陷门或密钥的一方进行可靠解码。

例子与边界

误差太小、样本过多或参数选择不当会导致攻击；误差太大又会破坏解密正确性。LWE 与简单的“对线性回归加高斯噪声”并非同一计算模型。

推论与应用

它是现代格密码、同态加密、后量子公钥加密与许多伪随机构造的核心假设。

参考资料

• Oded Regev, On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (2005), original LWE reduction.
• Dan Boneh, Victor Shoup, A Graduate Course in Applied Cryptography (2023/2026 draft), lattice cryptography and LWE.