2026-04-13 · cryptography
【密码学百科】后量子密码总览：NIST 标准化与五大技术路线
后量子密码学（PQC）旨在抵御量子计算机的攻击——本文全面介绍 NIST PQC 标准化竞赛的历程与结果、五大技术路线的核心参数对比、Rainbow/SIKE/SABER 的淘汰原因，以及 NIST 最终标准选择背后的现实权衡
在后量子密码学（Post-Quantum Cryptography）的版图中，格（Lattice）占据着无可争议的核心位置。NIST 于 2024 年正式发布的三项后量子标准中，ML-KEM（原 CRYSTALS-Kyber）与 ML-DSA（原 CRYSTALS-Dilithium）均以模格（Module Lattice）上的困难问题为安全根基；而更早进入标准化轨道的 FALCON 签名方案同样植根于 NTRU 格。可以说，理解格的数学本质，是理解整个后量子密码体系的前提条件。
本文将从格的基本定义出发，逐步引入格上经典困难问题、格基约化算法、LWE 家族假设，以及基于这些假设所构建的密码原语，最终讨论安全性评估方法论。文章面向具备线性代数与概率论基础的读者，力求在严谨性与可读性之间取得平衡。
先看一张图，把这一节的关键关系串起来。
graph TD
A[格] --> B[SVP 与 CVP]
B --> C[LLL 与 BKZ]
C --> D[LWE RLWE]
D --> E[后量子方案]设 \(\mathbf{b}_1, \mathbf{b}_2, \ldots, \mathbf{b}_n \in \mathbb{R}^m\)（\(n \leq m\)）为一组线性无关的向量。由这组向量生成的格定义为：
\[\mathcal{L}(\mathbf{B}) = \left\{ \sum_{i=1}^{n} z_i \mathbf{b}_i \;\middle|\; z_i \in \mathbb{Z} \right\}\]
其中矩阵 \(\mathbf{B} = [\mathbf{b}_1, \ldots, \mathbf{b}_n]\) 称为格基（Basis）。整数 \(n\) 称为格的秩（Rank），\(m\) 称为嵌入维度（Embedding Dimension）。当 \(n = m\) 时，称该格为满秩格（Full-Rank Lattice）。
从群论的角度看，格是 \(\mathbb{R}^m\) 中的离散加法子群（Discrete Additive Subgroup）。“离散”意味着格中任意两个不同的格点之间存在一个正的最小距离，这一性质将格与稠密的实数子集区别开来，也赋予了格上困难问题以计算意义。
同一格可以拥有无穷多组不同的基。若 \(\mathbf{B}\) 是格 \(\mathcal{L}\) 的一组基，则 \(\mathbf{B}' = \mathbf{B} \mathbf{U}\) 也是 \(\mathcal{L}\) 的一组基，当且仅当 \(\mathbf{U}\) 是一个行列式为 \(\pm 1\) 的整数方阵，即幺模矩阵（Unimodular Matrix）。这一事实意味着：格是客观确定的离散点集，但描述它的基却存在”好坏”之分——某些基的向量几乎正交且长度接近格的最短向量，另一些基的向量则可能高度共线、长度极大。格基约化（Lattice Basis Reduction）的核心目标，就是将一组”坏”基变换为”好”基。
格基确定了一个基本域（Fundamental Domain），通常取为半开平行体：
\[\mathcal{P}(\mathbf{B}) = \left\{ \sum_{i=1}^{n} x_i \mathbf{b}_i \;\middle|\; 0 \leq x_i < 1 \right\}\]
基本域的体积等于 \(\sqrt{\det(\mathbf{B}^T \mathbf{B})}\)，在满秩情形下退化为 \(|\det(\mathbf{B})|\)。这一量被称为格行列式（Lattice Determinant）或格的体积 \(\mathrm{vol}(\mathcal{L})\)，它是格的不变量，不随基的选取而变化。直觉上，格行列式衡量了格点的”稀疏程度”：体积越大，单位空间内的格点越少。
在二维平面中，格可以直观地理解为由两个不平行向量铺出的无限平行四边形网格。若两个基向量近乎正交且长度相近，网格呈”方正”形态，寻找最短向量较为容易；若基向量高度倾斜、长短悬殊，网格被极度拉伸，用眼睛可一望而知的最短向量在高维空间中却变得极难用算法找到。维度的诅咒（Curse of Dimensionality）正是格密码学安全性的直觉来源。
格密码学的安全性依赖于若干被广泛认为困难的计算问题。以下逐一介绍。
最短向量问题（Shortest Vector Problem, SVP）是格理论中最经典的困难问题。给定格 \(\mathcal{L}\) 的一组基 \(\mathbf{B}\)，要求找到一个非零格向量 \(\mathbf{v} \in \mathcal{L} \setminus \{\mathbf{0}\}\)，使得 \(\|\mathbf{v}\|\) 取得最小值。这个最小值记为 \(\lambda_1(\mathcal{L})\)，称为格的第一逐次最小值（First Successive Minimum）。
精确 SVP（Exact SVP）在一般范数下已被证明是 NP-Hard（Ajtai, 1998）。在实际应用中更常考虑的是近似版本 \(\gamma\)-SVP：找到一个非零格向量 \(\mathbf{v}\)，使得 \(\|\mathbf{v}\| \leq \gamma \cdot \lambda_1(\mathcal{L})\)，其中 \(\gamma \geq 1\) 为近似因子（Approximation Factor）。当 \(\gamma\) 为超多项式时，问题存在多项式时间算法（如 LLL）；当 \(\gamma\) 为多项式甚至常数时，问题的困难性是后量子密码安全性的基石。
最近向量问题（Closest Vector Problem, CVP）给定格基 \(\mathbf{B}\) 和目标向量 \(\mathbf{t} \in \mathbb{R}^m\)，要求找到一个格向量 \(\mathbf{v} \in \mathcal{L}(\mathbf{B})\)，使得 \(\|\mathbf{v} - \mathbf{t}\|\) 最小。CVP 可被视为 SVP 的推广：SVP 是目标向量为零时的特殊情形。CVP 在计算复杂性上至少与 SVP 同样困难。Babai 在 1986 年提出的最近平面算法（Nearest Plane Algorithm）可以在多项式时间内求解 \(2^{n/2}\)-CVP。
逐次最小值独立向量问题（Shortest Independent Vectors Problem, SIVP）要求找到 \(n\) 个线性无关的格向量，使得其中最长者的长度尽量短。间隙版本 GapSVP（Gap Shortest Vector Problem）是 SVP 的判定版本：给定格基和阈值 \(d\)，判断 \(\lambda_1 \leq d\) 还是 \(\lambda_1 > \gamma \cdot d\)。GapSVP 在 Regev 的 LWE 安全性归约中扮演关键角色。
有界距离解码问题（Bounded Distance Decoding, BDD）是 CVP 的受限版本：给定一个距格点足够近的目标向量（距离小于 \(\lambda_1 / 2\)），要求找到该最近格点。BDD 与 LWE 问题之间存在深刻的等价关系。
Shor 算法可以在量子多项式时间内解决整数分解和离散对数问题，但目前没有已知的量子算法能在多项式时间内解决上述格问题的困难版本。这正是格密码成为后量子候选方案之核心理由。
给定格基 \(\mathbf{b}_1, \ldots, \mathbf{b}_n\)，Gram-Schmidt 正交化（Gram-Schmidt Orthogonalization, GSO）定义如下：
\[\widetilde{\mathbf{b}}_i = \mathbf{b}_i - \sum_{j=1}^{i-1} \mu_{i,j} \widetilde{\mathbf{b}}_j, \quad \mu_{i,j} = \frac{\langle \mathbf{b}_i, \widetilde{\mathbf{b}}_j \rangle}{\langle \widetilde{\mathbf{b}}_j, \widetilde{\mathbf{b}}_j \rangle}\]
GSO 向量 \(\widetilde{\mathbf{b}}_1, \ldots, \widetilde{\mathbf{b}}_n\) 是原基向量在正交补上的投影。需要特别强调的是，GSO 向量一般并非格向量——它们的系数是实数而非整数。然而，GSO 向量的长度序列 \(\|\widetilde{\mathbf{b}}_1\|, \ldots, \|\widetilde{\mathbf{b}}_n\|\) 刻画了格基的”质量”。对于一组”好”的约化基，GSO 长度的衰减应当尽量缓慢；而对于随机基，GSO 长度往往呈现快速的几何衰减。
格的第 \(i\) 个逐次最小值 \(\lambda_i(\mathcal{L})\) 定义为使得存在 \(i\) 个线性无关的格向量、其长度均不超过 \(r\) 的最小 \(r\) 值。Minkowski 第一定理给出了 \(\lambda_1\) 的上界：
\[\lambda_1(\mathcal{L}) \leq \sqrt{n} \cdot \mathrm{vol}(\mathcal{L})^{1/n}\]
更精确的估计使用 Hermite 常数 \(\gamma_n\)：
\[\lambda_1(\mathcal{L}) \leq \sqrt{\gamma_n} \cdot \mathrm{vol}(\mathcal{L})^{1/n}\]
Hermite 常数 \(\gamma_n\) 仅在低维度下有精确值（如 \(\gamma_1 = 1\)，\(\gamma_2 = 2/\sqrt{3}\)，\(\gamma_8\) 对应 \(E_8\) 格），在高维度下满足渐近估计 \(\gamma_n \approx n / (2\pi e)\)。Hermite 常数也定义了格基约化的”目标”：一组基的 Hermite 因子（Hermite Factor）为 \(\|\mathbf{b}_1\| / \mathrm{vol}(\mathcal{L})^{1/n}\)，衡量最短基向量相对于理论下界的逼近程度。
GSO 的一个重要性质是 \(\prod_{i=1}^{n} \|\widetilde{\mathbf{b}}_i\| = \mathrm{vol}(\mathcal{L})\)。由此可推导出：\(\|\mathbf{b}_1\| \geq \|\widetilde{\mathbf{b}}_1\| \geq \lambda_1\)（第一个不等号因为 \(\widetilde{\mathbf{b}}_1 = \mathbf{b}_1\)，第二个不成立——事实上 \(\lambda_1 \leq \|\mathbf{b}_1\|\) 总是成立的，但 \(\|\mathbf{b}_1\|\) 可能远大于 \(\lambda_1\)）。一组约化良好的基使得 \(\|\mathbf{b}_1\|\) 尽量接近 \(\lambda_1\)。LLL 算法正是通过控制 GSO 系数和相邻 GSO 长度之比来实现这一目标的。
LLL 算法（Lenstra-Lenstra-Lovász Algorithm）由 Arjen Lenstra、Hendrik Lenstra 和 László Lovász 于 1982 年提出，最初动机是因式分解有理系数多项式。这一算法在多项式时间内将任意格基约化为”近似最短”的形式，成为计算数论、密码分析、整数规划等领域的基础工具。
一组格基 \(\mathbf{b}_1, \ldots, \mathbf{b}_n\) 称为 \(\delta\)-LLL 约化基（\(1/4 < \delta \leq 1\)），如果满足以下两个条件：
（1）尺寸约化条件（Size Reduction）：对所有 \(1 \leq j < i \leq n\)，有 \(|\mu_{i,j}| \leq 1/2\)。
（2）Lovász 条件：对所有 \(1 < i \leq n\)，有 \(\delta \|\widetilde{\mathbf{b}}_{i-1}\|^2 \leq \|\widetilde{\mathbf{b}}_i\|^2 + \mu_{i,i-1}^2 \|\widetilde{\mathbf{b}}_{i-1}\|^2\)。
Lovász 条件的直觉含义是：相邻 GSO 向量的长度不能下降得太快。参数 \(\delta\) 越接近 1，约化质量越高；经典选取 \(\delta = 3/4\)。
LLL 算法的核心循环在尺寸约化与基向量交换之间交替进行。当某对相邻向量违反 Lovász 条件时，交换它们的位置并重新进行尺寸约化。算法的终止性可以通过一个严格递减的势函数来证明：
\[D = \prod_{i=1}^{n} \|\widetilde{\mathbf{b}}_i\|^{2(n-i+1)}\]
每次交换使 \(D\) 至少缩小常数因子，而 \(D\) 有正下界，因此交换次数有限。总体复杂度为 \(O(n^5 d \log^3 M)\)，其中 \(d\) 为嵌入维度，\(M\) 为基向量元素的最大绝对值。
LLL 算法输出的第一个基向量 \(\mathbf{b}_1\) 满足：
\[\|\mathbf{b}_1\| \leq \left(\frac{2}{\sqrt{4\delta - 1}}\right)^{n-1} \lambda_1(\mathcal{L})\]
当 \(\delta = 3/4\) 时，近似因子为 \(2^{(n-1)/2}\)。这一指数级近似因子在低维下已足够精确，但在密码学关注的高维（数百至上千维）下远不足以破解方案——这正是格密码安全性的保障之一。
以下给出一个简化的二维 LLL 算法实现，帮助读者建立直觉：
import numpy as np
def lll_reduce_2d(b1, b2, delta=0.75):
"""
对二维格基 [b1, b2] 执行 LLL 约化。
b1, b2 为 numpy 数组，delta 为 Lovász 参数。
返回约化后的基向量。
"""
def mu(v, u):
return np.dot(v, u) / np.dot(u, u)
def size_reduce(b1, b2):
m = mu(b2, b1)
if abs(m) > 0.5:
b2 = b2 - round(m) * b1
return b1, b2
max_iter = 100
for _ in range(max_iter):
b1, b2 = size_reduce(b1, b2)
# 计算 GSO
mu12 = mu(b2, b1)
b1_star_sq = np.dot(b1, b1)
b2_star_sq = np.dot(b2, b2) - mu12**2 * b1_star_sq
# Lovász 条件检查
if b2_star_sq < (delta - mu12**2) * b1_star_sq:
b1, b2 = b2, b1 # 交换
else:
break
return b1, b2
# 示例：一组"坏"基
b1 = np.array([1, 0])
b2 = np.array([47, 2])
print(f"约化前：b1 = {b1}, b2 = {b2}")
print(f" |b1| = {np.linalg.norm(b1):.4f}, |b2| = {np.linalg.norm(b2):.4f}")
r1, r2 = lll_reduce_2d(b1, b2)
print(f"约化后：b1 = {r1}, b2 = {r2}")
print(f" |b1| = {np.linalg.norm(r1):.4f}, |b2| = {np.linalg.norm(r2):.4f}")运行结果中，原本长度悬殊的基向量 \((1, 0)\) 和 \((47, 2)\) 经过 LLL
约化后变为两个长度相近、更加正交的向量，直观展示了格基约化的效果。读者可以尝试将
b2 替换为更极端的向量（如
(1000001, 2)），观察算法如何在常数次迭代内完成约化。
LLL 算法的近似因子随维度指数增长，对于密码学尺度的格（维度数百以上）并不够强。BKZ 算法（Block Korkine-Zolotarev）由 Schnorr 和 Euchner 于 1994 年提出，通过在连续的局部块（Block）上求解精确 SVP 来获得更好的全局约化质量。
BKZ 的核心参数是块大小 \(\beta\)（Block Size）。当 \(\beta = 2\) 时，BKZ 退化为 LLL；当 \(\beta = n\) 时，BKZ 等价于 HKZ 约化（Hermite-Korkine-Zolotarev），可以找到精确的最短向量，但计算量随维度呈指数增长。实践中选取 \(\beta\) 在 20 至 60 之间，可以在合理时间内获得远优于 LLL 的约化质量。
BKZ 算法对格基进行多轮扫描（Tour）。每轮扫描中，算法依次选取连续 \(\beta\) 个 GSO 投影向量构成的子格，在该子格上调用精确 SVP 求解器（通常为枚举算法或筛法），将求得的短向量插入当前基中并进行局部 LLL 约化。一轮扫描完成后，检查基是否发生变化；若无变化则算法终止。
BKZ-\(\beta\) 输出的基满足 Hermite 因子约为 \(\gamma_\beta^{n / (2(\beta - 1))}\)，其中 \(\gamma_\beta\) 为 \(\beta\) 维的 Hermite 常数。当 \(\beta\) 增大时，Hermite 因子趋近 1，但每个块内 SVP 求解的代价随 \(\beta\) 呈超指数增长。
Chen 和 Nguyen 在 2011 年提出 BKZ 2.0，引入了以下关键改进：
（1）极端剪枝（Extreme Pruning）：在枚举 SVP 求解中使用激进的剪枝策略，以较低的单次成功概率换取大幅加速，通过多次随机化重启弥补概率损失。
（2）预处理（Preprocessing）：在对每个块调用 SVP 求解器之前，先用较小块大小的 BKZ 对该块进行预处理，提高枚举效率。
（3）自动终止策略（Early Termination）：当连续多轮扫描的斜率变化低于阈值时提前终止，避免在收敛尾部浪费计算。
Progressive BKZ 进一步优化了启动过程：算法从小块大小开始逐步增大至目标块大小，避免在初始阶段使用大块大小处理极差的基。这些改进使得 BKZ 在实践中能够高效处理维度达数百的格。
BKZ 内部的 SVP 求解器目前有两大流派。枚举算法（Enumeration）的时间复杂度约为 \(2^{O(\beta^2)}\)，空间需求为多项式级别。格筛法（Lattice Sieving），如 GaussSieve、HashSieve、BDGL 筛法，时间复杂度为 \(2^{O(\beta)}\)，但空间复杂度同样为 \(2^{O(\beta)}\)。对于较小的块大小（\(\beta \leq 60\)），枚举加剪枝通常更快；对于较大的块大小（\(\beta > 60\)），筛法在理论上渐近更优，但其巨大的内存需求使实际部署面临挑战。
一个经常被忽视的观点是，我们用来选择格密码参数的工具——格估计器——本身建立在关于 BKZ 行为的启发式假设之上。Core-SVP 方法论假设 BKZ 的瓶颈是其内部 SVP 求解器，并假设 BKZ 的输出遵循所谓的「几何级数假设」（GSA）。但 GSA 只是对 BKZ 实际行为的一种近似描述，在格维度增大时，GSA 与实际输出之间的偏差是否会扩大，目前尚无定论。更令人不安的是，格筛法的 \(2^{0.292\beta}\) 复杂度是渐近估计——它预设了指数级的内存可用性，而在实际攻击中内存往往是比计算更紧的瓶颈。我们本质上是在用「假设攻击者受内存限制」和「假设 BKZ 行为符合启发式模型」这两个尚未被严格证明的前提来保护后量子通信安全。从工程实践来看，这要求参数选择必须留出比传统密码学更大的安全余量——不是因为格密码不安全，而是因为我们对安全边界的认识还不够精确。
带错误学习问题（Learning With Errors, LWE）由 Oded Regev 于 2005 年提出。其定义如下：给定安全参数 \(n\)、模数 \(q\) 和误差分布 \(\chi\)（通常为离散高斯分布），秘密向量 \(\mathbf{s} \in \mathbb{Z}_q^n\) 均匀随机选取。LWE 问题的目标是：给定多项式数量的样本 \((\mathbf{a}_i, b_i)\)，其中 \(\mathbf{a}_i \xleftarrow{\$} \mathbb{Z}_q^n\)，\(e_i \xleftarrow{\$} \chi\)，\(b_i = \langle \mathbf{a}_i, \mathbf{s} \rangle + e_i \pmod{q}\)，恢复秘密向量 \(\mathbf{s}\)（搜索版本），或区分这些样本与均匀随机样本（判定版本）。
直觉上，LWE 是一个”带噪声的线性方程组”问题。若没有误差项 \(e_i\)，标准高斯消元即可在多项式时间内求解 \(\mathbf{s}\)；误差的存在使得问题变得困难。误差分布的标准差 \(\sigma\) 与模数 \(q\) 的比值 \(\alpha = \sigma / q\) 称为噪声率（Noise Rate），是控制问题困难程度的关键参数。
Applebaum 等人（2009）证明了 LWE 的正规形式（Normal Form）：可以不失一般性地假设秘密向量 \(\mathbf{s}\) 也从误差分布 \(\chi\) 中采样，而非均匀分布。这一变换在实际方案中极为重要，因为它使得秘密向量的元素很小，从而显著减少密钥尺寸和计算开销。ML-KEM 等方案均采用正规形式。
Regev 证明了 LWE 问题的困难性可以归约到格上的最坏情形困难问题：如果存在高效算法求解（判定）LWE，则存在量子算法在多项式时间内求解 GapSVP 和 SIVP 的 \(\tilde{O}(n/\alpha)\) 近似版本。这一归约的重要性在于：密码学中通常需要平均情形困难性（对随机实例困难），而 LWE 的困难性可以追溯到格问题的最坏情形困难性——即使最坏情形下的格实例也至少与随机 LWE 实例同样困难。
Peikert（2009）后来给出了经典归约（不依赖量子计算），条件略有不同。Brakerski 等人（2013）进一步将归约推广到更宽泛的参数范围。这些归约为 LWE 基方案的安全性提供了坚实的理论基础。
笔者认为，LWE 的最坏情形到平均情形归约是格密码学区别于所有其他后量子候选方案的根本理论优势，其重要性怎么强调都不过分。在传统密码学中，我们无法证明 RSA 的安全性归约到整数分解的最坏情形——可能存在某些「特殊结构」的 RSA 模数比随机模数更容易分解。对于编码基和多变量基的后量子方案，情况类似：它们的安全性依赖于随机实例的困难性假设，而非最坏情形保证。但 Regev 的归约告诉我们，破解一个随机 LWE 实例至少与解决该维度上最困难的格问题一样难。这意味着攻击者无法通过「挑选弱实例」来走捷径——每一个实例都至少与最坏情形一样难。这种保证在理论密码学中几乎是独一无二的，也正是 NIST 在后量子标准化中最终倾向于格基方案的深层原因。
在实际方案中，LWE 通常以矩阵形式表述。秘密矩阵 \(\mathbf{S} \in \mathbb{Z}_q^{n \times k}\) 由 \(k\) 个独立的秘密向量构成，公开矩阵 \(\mathbf{A} \in \mathbb{Z}_q^{m \times n}\) 均匀随机生成，误差矩阵 \(\mathbf{E} \in \mathbb{Z}_q^{m \times k}\) 从误差分布中采样，公开矩阵 \(\mathbf{B} = \mathbf{A}\mathbf{S} + \mathbf{E} \pmod{q}\)。一组 LWE 样本等价于 \((\mathbf{A}, \mathbf{B})\)。
标准 LWE 的一个实际问题是效率：公钥矩阵 \(\mathbf{A}\) 的尺寸为 \(m \times n\)，当 \(n\) 取密码学安全级别所需的值（如 \(n \geq 512\)）时，公钥尺寸和运算复杂度均较大。为了克服这一瓶颈，密码学家引入了结构化格（Structured Lattice）的概念。
Ring-LWE（RLWE）由 Lyubashevsky、Peikert 和 Regev 于 2010 年提出。它将 LWE 中的向量运算替换为多项式环 \(R_q = \mathbb{Z}_q[x] / (f(x))\) 上的运算，其中 \(f(x)\) 通常取分圆多项式 \(x^n + 1\)（\(n\) 为 2 的幂）。在 RLWE 中，秘密 \(s\)、随机元素 \(a\) 和误差 \(e\) 均为 \(R_q\) 中的多项式，样本形式为 \((a, b = a \cdot s + e) \in R_q^2\)。
RLWE 的核心优势在于：一个 \(R_q\) 元素包含 \(n\) 个系数，一对 RLWE 样本等价于 \(n\) 个标准 LWE 样本，但存储量仅为 \(O(n)\) 而非 \(O(n^2)\)。乘法运算可通过数论变换（Number Theoretic Transform, NTT）在 \(O(n \log n)\) 时间内完成。
RLWE 同样拥有最坏情形到平均情形归约，但归约目标是理想格（Ideal Lattice）上的困难问题，而非一般格。理想格具有额外的代数结构，这引发了学术界关于该结构是否可能被利用来加速攻击的持续讨论。目前尚无针对理想格的显著量子或经典加速。
Module-LWE（MLWE）是介于 LWE 与 RLWE 之间的折中方案，由 Brakerski、Gentry 和 Vaikuntanathan（2012）以及 Langlois 和 Stehlé（2015）系统研究。MLWE 将秘密和误差定义为 \(R_q\) 上的 \(k\) 维向量，公开矩阵为 \(R_q^{k \times k}\) 中的方阵。参数 \(k\) 提供了在 LWE（\(k\) 大、\(n\) 小）和 RLWE（\(k = 1\)、\(n\) 大）之间灵活调节的能力。
ML-KEM 采用 MLWE，其参数设定为 \(n = 256\)、\(k \in \{2, 3, 4\}\)，分别对应三个安全级别。Module 结构在保持 NTT 高效运算的同时，降低了对理想格特殊结构的依赖，被认为在效率与安全假设保守性之间取得了良好的平衡。
NTRU 格可以视为 RLWE 的”近亲”。NTRU 加密（Hoffstein, Pipher, Silverman, 1998）的安全性依赖于在特定多项式环上求解短向量问题。与 LWE 家族不同，NTRU 的归约并不直接来自最坏情形格问题，但其实际安全性经过二十余年的密码分析检验，被认为在适当参数下是可靠的。FALCON 签名方案基于 NTRU 格上的 GPV 框架。
理想格（Ideal Lattice）是多项式环 \(R_q = \mathbb{Z}_q[x]/(f(x))\) 中理想所对应的格，它继承了环的代数结构——这种额外的结构在带来效率优势的同时，也引发了”结构是否可能被攻击者利用”的持续关注。
主理想 SVP 的量子多项式时间算法。 Gentry 最初的全同态加密（FHE）方案以理想格为基础。后续研究表明，在分圆域（Cyclotomic Field）中，主理想（Principal Ideal）上的 SVP 可以在量子多项式时间内求解（Biasse-Song 2016，Cramer-Ducas-Wesolowski 2016）。这一结果的核心步骤是：首先利用量子算法求解主理想问题（PIP），将理想恢复为单个生成元；然后对生成元进行对数嵌入（Log-Embedding），在对数空间中寻找短向量。然而，这一攻击针对的是主理想格上的 SVP，而 RLWE/MLWE 的安全性归约并不依赖于主理想 SVP 的困难性——二者的困难问题在结构上存在本质区别。
NTRU 类方案的几何优势。 Ducas 和 Plançon（2023）的分析指出，对于基于 2 的幂次分圆多项式的 NTRU 类方案，攻击者在格约化过程中可获得约 10%——20% 的几何优势（相较于随机格）。具体而言，理想格的 Gram-Schmidt 正交化向量呈现出可预测的衰减模式，使得 BKZ 算法在理想格上的表现略优于在等维度随机格上的表现。这一发现虽未直接威胁当前参数的安全性，但为参数选取提供了更精细的安全余量（Security Margin）考量。
Module-LWE 的”稀释效应”。 Module-LWE 之所以被认为比 Ring-LWE 更为保守，关键在于模结构提供了一种”稀释效应”（Dilution Effect）。在 MLWE 中，即使单个环分量存在结构性弱点，整体安全性的下降也是渐进的——攻击者需要同时利用 \(k\) 个环分量的结构，而模维度 \(k\) 的增大会显著稀释单个分量的结构优势。这一性质使得 MLWE 在面对未来可能发现的理想格结构攻击时具备更强的鲁棒性。
当前共识与标准化选择。 截至目前，尚无已知的实际攻击能够利用理想格的代数结构来突破 ML-KEM 或 ML-DSA 在标准参数下的安全性。然而，密码学界出于审慎原则，在参数选取时保留了额外的安全余量以应对潜在的结构性攻击。这也是 NIST 最终选择基于 Module-LWE 的 ML-KEM 作为首要密钥封装机制、而非基于 Ring-LWE 的 NTRU 方案的重要原因之一——在效率可接受的前提下，优先选择安全假设更为保守的构造。
Regev（2005）在提出 LWE 问题的同时给出了一个简洁的公钥加密方案。密钥生成选取随机矩阵 \(\mathbf{A}\) 和秘密向量 \(\mathbf{s}\)，公钥为 \((\mathbf{A}, \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e})\)。加密时，选取随机向量 \(\mathbf{r}\)，计算密文 \((\mathbf{u}, v) = (\mathbf{A}^T \mathbf{r}, \mathbf{b}^T \mathbf{r} + \lfloor q/2 \rceil \cdot m)\)，其中 \(m \in \{0, 1\}\) 为明文比特。解密时，计算 \(v - \mathbf{u}^T \mathbf{s}\)，得到 \(\lfloor q/2 \rceil \cdot m\) 加上一个较小的误差项，通过四舍五入恢复 \(m\)。
该方案的正确性要求误差积累不超过 \(q/4\)，这对参数选取施加了约束。方案的 IND-CPA 安全性直接归约到判定 LWE 问题的困难性。
对偶 Regev（Dual Regev）加密将密钥生成与加密过程对调：公钥仍然是一组 LWE 样本，但秘密向量在加密时选取。这一变体在理论分析中更为方便，且与基于身份的加密（IBE）等高级构造的联系更为紧密。Gentry、Peikert 和 Vaikuntanathan（2008）在对偶 Regev 框架下构建了基于格的 IBE 方案。
GPV 框架（Gentry, Peikert, Vaikuntanathan, 2008）是基于格的 Hash-and-Sign 签名范式。其核心思想是：签名者持有一组格的”陷门基”（Trapdoor Basis），即一组特别短的格基；验证者仅知道格本身（通过公钥矩阵 \(\mathbf{A}\) 描述）。签名时，签名者将消息散列到格的陪集（Coset）中，利用陷门基采样一个短的陪集向量作为签名。验证者检查签名是否属于正确的陪集且足够短。
陷门采样（Trapdoor Sampling）是 GPV 框架的技术核心。Micciancio 和 Peikert（2012）给出了高效的陷门生成与离散高斯采样算法，使得 GPV 框架在实践中可行。FALCON 签名方案即是 GPV 框架在 NTRU 格上的实例化。
上述基本方案仅达到 CPA 安全。在实际部署中通常需要 CCA 安全（抗选择密文攻击）。Fujisaki-Okamoto（FO）变换是将 CPA 安全的 KEM/PKE 提升为 CCA 安全的标准工具。ML-KEM 正是将基于 MLWE 的 CPA 安全方案通过 FO 变换得到 CCA 安全 KEM 的产物。FO 变换的核心思想是在解密过程中重新加密并比对密文，以检测篡改。
理解格密码方案的参数选取，是衔接理论与实践的关键环节。以下以 NIST 正式标准 FIPS 203（ML-KEM）和 FIPS 204（ML-DSA）为例，具体剖析参数设计背后的考量。
ML-KEM 参数一览：
| 参数 | ML-KEM-512 | ML-KEM-768 | ML-KEM-1024 |
|---|---|---|---|
| 安全级别 | NIST Level 1（128 比特） | Level 3（192 比特） | Level 5（256 比特） |
| 模维度 \(k\) | 2 | 3 | 4 |
| 多项式环 | \(\mathbb{Z}_{3329}[x]/(x^{256}+1)\) | 同左 | 同左 |
| 公钥尺寸 | 800 字节 | 1184 字节 | 1568 字节 |
| 密文尺寸 | 768 字节 | 1088 字节 | 1568 字节 |
| 共享密钥 | 32 字节 | 32 字节 | 32 字节 |
ML-DSA 参数一览：
| 参数 | ML-DSA-44 | ML-DSA-65 | ML-DSA-87 |
|---|---|---|---|
| 安全级别 | Level 2 | Level 3 | Level 5 |
| 公钥尺寸 | 1312 字节 | 1952 字节 | 2592 字节 |
| 签名尺寸 | 2420 字节 | 3309 字节 | 4627 字节 |
参数设计解读。 \(q = 3329\) 的选取并非随意——它是满足 \(q \equiv 1 \pmod{256}\) 的最小素数之一，这意味着 \(\mathbb{Z}_q\) 中存在 256 次本原单位根，从而支持 256 点数论变换（NTT）。NTT 将多项式乘法的时间复杂度从朴素的 \(O(n^2)\) 降至 \(O(n \log n)\)，是格密码高效实现的基石。\(n = 256\) 取 2 的幂次，同样是为了匹配 NTT 的蝶形运算结构，并保证分圆多项式 \(x^{256} + 1\) 在 \(\mathbb{Z}_q\) 上完全分裂为线性因子。不同安全级别通过调节模维度 \(k\) 来实现：\(k\) 越大，攻击者面对的格维度（\(k \times 256\)）越高，格约化的计算代价呈指数增长。
性能基准。 在配备 AVX2 指令集的现代 x86 处理器上，ML-KEM-768 的典型性能为：密钥生成约 20 μs，封装（Encapsulation）约 25 μs，解封装（Decapsulation）约 25 μs。与经典的 X25519 ECDH 协议相比，ML-KEM-768 在计算速度上慢约 2——3 倍，但公钥尺寸（1184 字节 vs. 32 字节）约为后者的 37 倍。这一尺寸差异是格密码在网络协议部署中面临的主要挑战——尤其是在 TLS 握手、证书链等场景中，额外的带宽开销不可忽视。
格密码方案的安全性评估通常采用 Core-SVP 方法论。其核心假设是：攻击格方案最有效的方法是运行 BKZ-\(\beta\)，而 BKZ 的瓶颈是其中块大小 \(\beta\) 的 SVP 求解。因此，安全级别以”需要多大的 \(\beta\) 才能将格基约化到足以破解方案”来衡量。
具体步骤如下：首先根据方案参数构造攻击所需的格；然后估计 BKZ-\(\beta\) 输出的 Hermite 因子或 GSO 长度分布；再确定使攻击成功的最小块大小 \(\beta_{\min}\)；最后将 \(\beta_{\min}\) 维 SVP 的求解代价作为安全性的度量。对于经典攻击，SVP 代价通常取枚举的 \(2^{0.292\beta}\)（使用格筛法的渐近估计）；对于量子攻击，取 \(2^{0.265\beta}\)（量子筛法估计）。
Albrecht 等人开发并维护的格估计器（Lattice Estimator）是评估格密码安全性的标准开源工具。它集成了针对 LWE/RLWE/MLWE 的多种攻击算法的复杂度估计，包括：
（1）原始攻击（Primal Attack）：将 LWE 实例嵌入到格中，求解唯一 SVP（unique-SVP）。
（2）对偶攻击（Dual Attack）：在对偶格中寻找短向量，利用其与 LWE 秘密的相关性进行区分。
（3）混合攻击（Hybrid Attack）：结合格约化与穷举搜索，对小秘密或稀疏秘密尤其有效。
（4）组合攻击：如 Arora-Ge 攻击、BKW 攻击等。
对于每种攻击，估计器输出所需的时间和内存复杂度，取其最小值作为方案的安全估计。NIST 在后量子标准化过程中广泛使用了格估计器的结果。
以下以一组接近 ML-KEM-512 的 LWE 参数为例，演示格估计器（lattice-estimator）的具体使用流程。假设参数为：\(n = 1024\)，\(q = 2^{32}\)，误差分布为离散高斯 \(\sigma = 3.19\)（标准差约 \(3.19\)，对应 \(\alpha \approx \sigma \sqrt{2\pi} / q \approx 1.86 \times 10^{-9}\)）。
# 安装与使用格估计器（https://github.com/malb/lattice-estimator）
# git clone https://github.com/malb/lattice-estimator.git
# cd lattice-estimator && sage
from estimator import *
# 定义 LWE 参数
n = 1024
q = 2**32
# 离散高斯误差，标准差 sigma = 3.19
sigma = 3.19
params = LWE.Parameters(
n=n,
q=q,
Xs=ND.DiscreteGaussian(sigma), # 秘密分布（Normal Form 下与误差同分布）
Xe=ND.DiscreteGaussian(sigma), # 误差分布
)
# 运行所有已知攻击的复杂度估计
print("=== LWE 参数安全性估计 ===")
print(f"参数: n={n}, q=2^32, σ={sigma}")
print()
# 原始攻击（uSVP 嵌入）
res_primal = LWE.primal_usvp(params)
print(f"原始攻击 (uSVP): ~2^{float(res_primal['rop']):.1f} 次操作")
# 对偶攻击
res_dual = LWE.dual_hybrid(params)
print(f"对偶混合攻击: ~2^{float(res_dual['rop']):.1f} 次操作")
# 最终安全估计 = 所有攻击中的最小值
print()
print("综合安全估计: 约 128+ 比特经典安全")上述参数的典型估计结果大致如下：原始攻击（uSVP 嵌入）所需的最优 BKZ 块大小 \(\beta \approx 380\)——\(420\)，对应经典安全约 \(2^{128}\)——\(2^{140}\) 次操作；对偶混合攻击的复杂度处于相近量级。这意味着该参数组合满足 NIST Level 1 的安全要求。如果将 \(n\) 缩小到 \(512\) 而保持 \(q\) 和 \(\sigma\) 不变，安全性将大幅下降至约 \(80\)——\(90\) 比特，不再满足任何标准安全级别的要求。
读者可以自行修改参数，观察 \(n\)、\(q\)、\(\sigma\) 三者之间的制衡关系：增大 \(n\) 提升安全性但增加密钥尺寸；增大 \(q\) 使方案更容易正确解密但降低安全性；增大 \(\sigma\) 提升安全性但增大解密失败概率。
个人思考。 在所有密码学分支中，格密码的参数选取大概是最令人焦虑的环节。传统的 RSA 或 ECC，我们有数十年的密码分析积累，参数推荐建立在大量已知攻击的精确复杂度分析之上。而格密码的安全性估计本质上是在做「外推」——我们用当前最好的格约化算法（BKZ + 筛法）来估计攻击代价，但无法排除明天就有人发现全新的攻击范式。更令人不安的是，格问题的最坏情形到平均情形归约虽然在理论上极为优美，但归约中的参数损失意味着实际安全性与理论保证之间存在显著的间隙。我们本质上是在用「尚未被证伪」的硬度估计来保护未来数十年的通信安全——这种赌注的规模，值得每一位从业者保持清醒的敬畏。
NIST 定义了五个安全级别，分别对标经典密码学原语的安全强度：Level 1 对标 AES-128，Level 2 对标 SHA-256 碰撞，Level 3 对标 AES-192，Level 4 对标 SHA-384 碰撞，Level 5 对标 AES-256。对于格密码方案，安全级别的确定流程是：使用格估计器评估最优攻击的复杂度（以比特为单位），然后与对应经典原语的暴力搜索/碰撞搜索复杂度进行比较。
ML-KEM-512 目标为 Level 1（经典安全约 118 比特），ML-KEM-768 目标为 Level 3（约 182 比特），ML-KEM-1024 目标为 Level 5（约 256 比特）。需要注意的是，量子攻击的成本模型（门级成本 vs. 深度限制成本）仍在讨论中，不同的成本模型可能导致数个比特的安全性差异。
格密码安全性评估仍有若干悬而未决的问题。格筛法的实际内存瓶颈能否被新技术克服？理想格和模格的代数结构是否隐藏着尚未发现的攻击？量子计算对格问题的加速是否仅限于平方根级别？这些问题的答案将直接影响后量子密码参数的选取和标准的长期可靠性。
格密码从理论研究走向工业标准，经历了近十年的系统评估。以下梳理关键时间节点与技术演进脉络。
标准化时间线：
核心假设的演进路径。 格密码的安全根基经历了从 LWE 到 Ring-LWE 再到 Module-LWE 的渐进演化。标准 LWE 拥有最强的安全归约（最坏情形到平均情形），但效率较低；Ring-LWE 通过引入环结构大幅提升效率，代价是安全性依赖于理想格困难问题；Module-LWE 在两者之间寻得平衡，通过模维度 \(k\) 灵活调节结构依赖程度。每一步演化都是在效率与结构风险之间的审慎权衡。
SIKE 的崩溃：新假设的前车之鉴。 2022 年，基于超奇异同源（Supersingular Isogeny）的密钥交换方案 SIKE——NIST 竞赛第四轮候选方案之一——被 Castryck 和 Decru 以经典多项式时间算法完全攻破。这一事件深刻提醒了密码学界：新型数学假设的安全性需要经过长期、充分的密码分析检验。相比之下，格问题已经过近三十年的持续研究，安全性基础远为坚实，但 SIKE 的教训仍然促使社区对格方案的参数选取保持额外的审慎态度。
实际部署现状。 后量子密码正在加速进入生产环境：
开放问题与参数演化。 随着格约化算法的持续改进，参数选取面临动态调整的压力。当前安全性估计的核心变量包括：BKZ 块大小 \(\beta\) 的实际求解代价（经典筛法 vs. 量子筛法）、内存模型的选取（RAM 模型 vs. 量子 RAM 模型）、以及格约化算法在理想格/模格上是否存在尚未量化的加速。密码学界需要在”参数足够保守以应对未来攻击改进”与”参数足够紧凑以满足部署需求”之间持续寻找平衡点。
密码学界目前的共识是：在保守的参数选取下，格密码方案的安全性是可信的。但正如历史上每一种密码学假设一样，持续的密码分析研究是保持信心的必要条件。理解本文介绍的数学基础，是参与这一持续研究过程的第一步。
密码学百科系列 · 第 37 篇
← 上一篇：离散对数与配对密码学 | 系列目录 | 下一篇：概率论与密码分析 →
把当前热点继续串成多页阅读，而不是停在单篇消费。
2026-04-13 · cryptography
后量子密码学（PQC）旨在抵御量子计算机的攻击——本文全面介绍 NIST PQC 标准化竞赛的历程与结果、五大技术路线的核心参数对比、Rainbow/SIKE/SABER 的淘汰原因，以及 NIST 最终标准选择背后的现实权衡
2026-04-13 · cryptography
格基密码是后量子密码学的主力方案——本文深入解析 NIST 首选的 ML-KEM（原 CRYSTALS-Kyber）密钥封装和 ML-DSA（原 CRYSTALS-Dilithium）数字签名的算法细节、安全性分析和实现优化
2026-05-18 · algorithms
LLL 算法是密码分析中最强大的工具之一。
2027-03-25 · cryptography
从 SM3/SM4/SM2 的设计对比到国密 TLS 握手、生态落地、PQC 迁移——国密技术的完整知识图谱。
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。