带误差学习（LWE）基础

Regev 在 2005 年提出的带错误学习（LWE）：给定许多个在 Z_q 上的带噪声线性方程，求出秘密向量 s。噪声 e 很小，但会阻止高斯消元。没有噪声时，方程组很容易求解；即使加入极小的噪声，计算也会变得困难。

秘密向量 s ∈ Z_q^n。攻击者接收样本 (a_i, b_i)，其中 a_i ∈ Z_q^n 是随机向量，b_i = <a_i, s> + e_i mod q，e_i 是来自分布 χ 的小噪声（例如标准差为 σ = √n 的高斯噪声）。任务是：给定多项式数量的样本，求出 s。

没有噪声时：b_i = <a_i, s> mod q。高斯消元可以在 O(n^3) 时间内恢复 s。有噪声时：即使只有一个错误方程，也会破坏消元过程。噪声足够小，因此使用密钥可以成功解密；但又足够大，能够阻止密码分析。

Regev 证明了：通过量子归约，LWE 可以归约到最坏情况下的格问题（SIVP、GapSVP）。这意味着：如果 LWE 被破解，许多困难的格问题也将被解决——但目前还没有针对格问题的已知量子算法。LWE 能够抵抗量子攻击。

RLWE 将 Z_q^n 替换为环 Z_q[x]/(f(x))，其中 f 是一个分圆多项式。一个 RLWE 样本可以编码 n 个方程，因此效率高得多。RLWE 是 Kyber（KEM）、Dilithium（签名）以及 BFV/BGV/CKKS 同态加密方案的基础。

安全性取决于：n（维度，通常为 512-2048）、q（模数，1024-2^60）和 σ（噪声标准差）。n 越大、σ/q 比值越小，问题就越困难。NIST 的后量子标准使用 n=256（模块维度）以及 k 个模块（k=2、3、4）。

公钥：(A, b=As+e)。加密比特 m：选择随机向量 r，计算密文 (u=A^T r, v = b^T r + m*q/2)。解密：v - s^T u = e^T r + m*q/2 ≈ m*q/2。将结果舍入到最近的 m。噪声 e 会在加密过程中使密文隐藏 m。

判定 LWE：区分 (a, As+e) 与 (a, u)，其中 u 是均匀随机向量。在 LWE 困难性假设下，这两者在计算上不可区分。这是语义安全性的基础——对于没有秘密密钥的攻击者而言，密文看起来就像随机噪声。

已知的最佳攻击方法是 BKZ（分块 Korkine-Zolotarev）格规约。其复杂度为亚指数级，但不是多项式级。BKZ-β 需要执行 2^{0.292β} 次操作。对于 LWE-512，针对 BKZ 的安全性约为 128 位。目前还不知道针对 BKZ 的量子加速算法。

模块-LWE（用于 Kyber）是在秩为 k 的模块上定义的 RLWE。它提供了灵活性：k=2 对应 512 位安全性，k=3 对应 768 位，k=4 对应 1024 位。安全性和性能都会随 k 增长。NIST 选择 Kyber（更名为 ML-KEM）作为 PQC 标准。

RSA/ECC 的安全性基于整数分解和离散对数问题（可通过 Shor 算法受到量子攻击）。LWE 的安全性基于最坏情况下的格问题（目前没有已知的量子加速算法）。密钥大小：LWE 密钥约为 1 KB，而 RSA-2048 密钥为 256 字节。LWE 的密钥更大，但能够抵抗量子攻击。

即使拥有大量样本，LWE 为何仍然难以求解？

LWE：从带噪声的线性方程中求出秘密向量 s，属于量子计算也难以求解的问题。RLWE 使用多项式环来提高效率。它是 Kyber、Dilithium 和同态加密方案的基础。下一节：用于整数运算的 BGV 和 BFV 同态加密方案。