环 LWE 与模格

标准 LWE 需要进行大型矩阵-向量乘法，从而导致较大的密钥尺寸。Ring-LWE 由 Lyubashevsky、Peikert 和 Regev 于 2010 年提出，它将向量和矩阵替换为环 R_q = Z_q[X]/(f(X)) 中的多项式。这种结构化设置支持更紧凑的密钥和更快的运算，使环-LWE 成为现实世界中基于晶格的密码学的实用基础。

环-LWE 中使用的多项式 f(X) 通常为 f(X) = X^n + 1，其中 n 是 2 的幂。这是 2n 次圆分多项式。选择它是因为它在 Z 上不可约，能确保环 R_q 具备良好的代数性质，并支持使用数论变换（NTT）进行高效乘法。圆分环已经过深入研究，通常被认为是安全的。

在环-LWE 中，秘密 s 是 R_q 中的一个多项式，样本的形式为 (a, b = a*s + e)，其中 a 是均匀随机的环元素，e 是一个小误差多项式。对手可以看到许多这样的样本，并必须恢复 s，或将这些样本与均匀分布区分开来。其困难性依赖于环-LWE 假设，该假设可从理想晶格上的最坏情况问题归约得到。

对于对手而言，环-LWE 比普通 LWE 更难，但它所对应的安全性归约也略有不同。该归约来自理想晶格上的最坏情况问题（理想-SVP），而不是任意晶格上的问题。原则上，理想晶格的额外结构可能使其比一般晶格更容易处理，这也是一个活跃的研究领域。目前尚无利用这种结构的实际攻击。

模块-LWE（M-LWE）通过使用由环元素构成的 k x k 矩阵，而不是单个环元素或由整数构成的大矩阵，推广了 LWE 和环-LWE。当 k = 1 时，它退化为环-LWE；随着 k 增大，它逐渐接近标准 LWE。这个可调参数 k 可以在安全性信心与性能之间进行平衡。

CRYSTALS-Kyber（现称 ML-KEM，FIPS 203）基于 R_q 上秩为 k 的矩阵 Module-LWE。参数 k 直接控制安全级别：k=2 对应 128 位安全性（ML-KEM-512），k=3 对应 192 位安全性（ML-KEM-768），k=4 对应 256 位安全性（ML-KEM-1024）。模块结构使同一套代码库能够通过改变 k 来调整安全级别。

R_q = Z_q[X]/(X^n + 1) 中的多项式乘法是性能瓶颈。数论变换（NTT）是定义在 Z_q 上的离散傅里叶变换，它将多项式转换为求值形式，使乘法变为逐点相乘。在选择合适的 q 使 NTT 可用后，多项式乘法的时间复杂度从 O(n^2) 降为 O(n log n)，这是 ML-KEM 和 ML-DSA 中的一项关键优化。

NTT 要求 q 是满足 q = 1 mod 2n 的素数，从而确保 Z_q 包含一个本原 2n 次单位根。对于 n = 256 的 ML-KEM，q = 3329 满足这一要求。在配备 SIMD 指令的现代硬件上，Z_3329 上的 NTT 极其高效，因此普通处理器每秒可以执行数千次 ML-KEM 操作。

与标准 LWE 相比，环-LWE 和模块-LWE 能够大幅减小密钥大小。达到 128 位安全性的标准 LWE 公钥可能有 1 MB；环-LWE 可将其缩小到约 800 字节，而模块-LWE（ML-KEM-768）在提供 192 位后量子安全性的同时，公钥大小仅为 1184 字节。这种紧凑性使基于格的方案适用于 TLS 和嵌入式系统。

一些密码学家担心，分圆环额外的代数结构可能会实现一些不适用于普通 LWE 的攻击。2024 年，Elias Rokicki 及其合作者发表了关于 2n 次分圆多项式的分析，认为目前没有实际可行的攻击，但也强调了持续审查的重要性。NIST 的 PQC 流程考虑了这一风险，并部分出于减少对任何单一环结构依赖的考虑而选择了模块-LWE。

除了 Kyber 之外，环-LWE 还是 CRYSTALS-Dilithium（ML-DSA）这一由 NIST 标准化的签名方案的基础。Microsoft 的 SEAL 加密库通过环-LWE 实现同态加密。Google 的 Tink 密码学库包含对 ML-KEM 的支持。在 NIST 标准化流程的推动下，环-LWE 在极短时间内已从理论构造走向生产环境部署。

与标准 LWE 相比，环-LWE 的主要优势是什么？

环-LWE 将 LWE 转移到多项式环 R_q = Z_q[X]/(X^n+1) 中，大幅减小密钥大小，并支持基于 NTT 的快速算术运算。模块-LWE 通过秩为 k 的结构对其进行推广，构成 ML-KEM（FIPS 203）和 ML-DSA（FIPS 204）的基础。适合 NTT 的素数 q = 3329 支持高效实现。其安全性建立在理想格和模块格上问题的困难性之上。