容错学习问题 LWE 是什么？抗量子密码学的数学基石

容错学习问题（Learning With Errors，LWE）是密码学和理论计算机科学中一个非常重要的数学难题，由 Oded Regev 在 2005 年提出。它是当今“后量子密码学”最重要的基础之一，Regev 也因这项工作获得了 2018 年的哥德尔奖。

问题是什么

先看一个简单的情况：给你一组线性方程，比如若干个形如“a1 乘 s1 加 a2 乘 s2 加……等于 b”的方程，其中系数 a 都已知，要求出未知的秘密向量 s。如果方程是精确的，这个问题很容易，用中学学过的高斯消元法就能解出来。

LWE 问题的关键在于“带误差”：每个方程的结果 b 上都被加了一点点随机的小误差，而且所有的计算都在一个模数下进行，也就是只看除以某个数之后的余数。给定大量这样带误差的方程，要求找出秘密向量 s。就是这一点点小误差，让问题从“很容易”变成了“极其困难”：高斯消元的过程会把误差不断放大，最后完全淹没真实的信息。可以把它想象成：你得到了很多条关于一个秘密的线索，但每条线索都被故意说得有点不准，而且你不知道每条线索偏差了多少。

为什么它是密码学的基石

密码学的安全性建立在某些数学问题“很难求解”的基础上。现在广泛使用的 RSA 和椭圆曲线密码，依赖的是大整数分解和离散对数问题的困难性。但 1994 年提出的肖尔算法表明，一旦有了足够强大的量子计算机，这些问题就能被高效地求解，这意味着现有的大部分公钥密码体系将不再安全。

LWE 问题则被认为即使在量子计算机上也难以求解。Regev 的重要贡献在于证明了：解决 LWE 问题，至少和解决某些“格”上的困难问题一样难，而格问题被研究了很久，至今没有找到有效的经典算法或量子算法。这为基于 LWE 构建的密码系统提供了坚实的安全性保证。

应用

基于 LWE 及其变体（如环上的 LWE、模 LWE），研究者构建了大量的密码方案，统称为格密码。2024 年，美国国家标准与技术研究院（NIST）正式发布了首批后量子密码标准，其中的密钥封装标准 ML-KEM（源自 CRYSTALS-Kyber）和数字签名标准 ML-DSA（源自 CRYSTALS-Dilithium），都基于模 LWE 等格问题。此外，LWE 还是全同态加密的基础，让人们可以直接在加密的数据上进行计算，这在隐私保护的 AI 计算中有重要的应用前景。