在后量子密码学（Post-Quantum Cryptography）的版图中，格（Lattice）占据着无可争议的核心位置。NIST 于 2024 年正式发布的三项后量子标准中，ML-KEM（原 CRYSTALS-Kyber）与 ML-DSA（原 CRYSTALS-Dilithium）均以模格（Module Lattice）上的困难问题为安全根基；而更早进入标准化轨道的 FALCON 签名方案同样植根于 NTRU 格。可以说，理解格的数学本质，是理解整个后量子密码体系的前提条件。
本文将从格的基本定义出发，逐步引入格上经典困难问题、格基约化算法、LWE 家族假设，以及基于这些假设所构建的密码原语，最终讨论安全性评估方法论。文章面向具备线性代数与概率论基础的读者，力求在严谨性与可读性之间取得平衡。
一、格的定义与几何直觉
1.1 代数定义
设 \(\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）。“离散”意味着格中任意两个不同的格点之间存在一个正的最小距离，这一性质将格与稠密的实数子集区别开来，也赋予了格上困难问题以计算意义。
1.2 基与基的非唯一性
同一格可以拥有无穷多组不同的基。若 \(\mathbf{B}\) 是格 \(\mathcal{L}\) 的一组基，则 \(\mathbf{B}' = \mathbf{B} \mathbf{U}\) 也是 \(\mathcal{L}\) 的一组基，当且仅当 \(\mathbf{U}\) 是一个行列式为 \(\pm 1\) 的整数方阵，即幺模矩阵（Unimodular Matrix）。这一事实意味着：格是客观确定的离散点集，但描述它的基却存在”好坏”之分——某些基的向量几乎正交且长度接近格的最短向量，另一些基的向量则可能高度共线、长度极大。格基约化（Lattice Basis Reduction）的核心目标，就是将一组”坏”基变换为”好”基。
1.3 基本域与行列式
格基确定了一个基本域（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})\)，它是格的不变量，不随基的选取而变化。直觉上，格行列式衡量了格点的”稀疏程度”：体积越大，单位空间内的格点越少。
1.4 几何直觉
在二维平面中，格可以直观地理解为由两个不平行向量铺出的无限平行四边形网格。若两个基向量近乎正交且长度相近，网格呈”方正”形态，寻找最短向量较为容易；若基向量高度倾斜、长短悬殊，网格被极度拉伸，用眼睛可一望而知的最短向量在高维空间中却变得极难用算法找到。维度的诅咒（Curse of Dimensionality）正是格密码学安全性的直觉来源。
二、格上的困难问题
格密码学的安全性依赖于若干被广泛认为困难的计算问题。以下逐一介绍。
2.1 最短向量问题（SVP）
最短向量问题（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\) 为多项式甚至常数时，问题的困难性是后量子密码安全性的基石。
2.2 最近向量问题（CVP）
最近向量问题（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。
2.3 其他重要问题
逐次最小值独立向量问题（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 问题之间存在深刻的等价关系。
2.4 量子抗性
Shor 算法可以在量子多项式时间内解决整数分解和离散对数问题，但目前没有已知的量子算法能在多项式时间内解决上述格问题的困难版本。这正是格密码成为后量子候选方案之核心理由。
三、Gram-Schmidt 正交化与 Hermite 常数
3.1 Gram-Schmidt 正交化
给定格基 \(\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 长度往往呈现快速的几何衰减。
3.2 逐次最小值与 Minkowski 界
格的第 \(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}\)，衡量最短基向量相对于理论下界的逼近程度。
3.3 GSO 与格问题的联系
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 算法
4.1 历史背景
LLL 算法（Lenstra-Lenstra-Lovász Algorithm）由 Arjen Lenstra、Hendrik Lenstra 和 László Lovász 于 1982 年提出，最初动机是因式分解有理系数多项式。这一算法在多项式时间内将任意格基约化为”近似最短”的形式，成为计算数论、密码分析、整数规划等领域的基础工具。
4.2 LLL 约化基的定义
一组格基 \(\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\)。
4.3 算法流程
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\) 为基向量元素的最大绝对值。
4.4 近似保证
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}\)。这一指数级近似因子在低维下已足够精确，但在密码学关注的高维（数百至上千维）下远不足以破解方案——这正是格密码安全性的保障之一。
4.5 Python 演示：二维格上的 LLL
以下给出一个简化的二维 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)），观察算法如何在常数次迭代内完成约化。
五、BKZ 算法族
5.1 从 LLL 到 BKZ
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 的约化质量。
5.2 BKZ 的工作流程
BKZ 算法对格基进行多轮扫描（Tour）。每轮扫描中，算法依次选取连续 \(\beta\) 个 GSO 投影向量构成的子格，在该子格上调用精确 SVP 求解器（通常为枚举算法或筛法），将求得的短向量插入当前基中并进行局部 LLL 约化。一轮扫描完成后，检查基是否发生变化；若无变化则算法终止。
BKZ-\(\beta\) 输出的基满足 Hermite 因子约为 \(\gamma_\beta^{n / (2(\beta - 1))}\)，其中 \(\gamma_\beta\) 为 \(\beta\) 维的 Hermite 常数。当 \(\beta\) 增大时，Hermite 因子趋近 1，但每个块内 SVP 求解的代价随 \(\beta\) 呈超指数增长。
5.3 BKZ 2.0 与现代改进
Chen 和 Nguyen 在 2011 年提出 BKZ 2.0，引入了以下关键改进：
（1）极端剪枝（Extreme Pruning）：在枚举 SVP 求解中使用激进的剪枝策略，以较低的单次成功概率换取大幅加速，通过多次随机化重启弥补概率损失。
（2）预处理（Preprocessing）：在对每个块调用 SVP 求解器之前，先用较小块大小的 BKZ 对该块进行预处理，提高枚举效率。
（3）自动终止策略（Early Termination）：当连续多轮扫描的斜率变化低于阈值时提前终止，避免在收敛尾部浪费计算。
Progressive BKZ 进一步优化了启动过程：算法从小块大小开始逐步增大至目标块大小，避免在初始阶段使用大块大小处理极差的基。这些改进使得 BKZ 在实践中能够高效处理维度达数百的格。
5.4 筛法与枚举
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 行为符合启发式模型」这两个尚未被严格证明的前提来保护后量子通信安全。从工程实践来看，这要求参数选择必须留出比传统密码学更大的安全余量——不是因为格密码不安全，而是因为我们对安全边界的认识还不够精确。
六、LWE 问题
6.1 定义
带错误学习问题（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），是控制问题困难程度的关键参数。
6.2 正规形式
Applebaum 等人（2009）证明了 LWE 的正规形式（Normal Form）：可以不失一般性地假设秘密向量 \(\mathbf{s}\) 也从误差分布 \(\chi\) 中采样，而非均匀分布。这一变换在实际方案中极为重要，因为它使得秘密向量的元素很小，从而显著减少密钥尺寸和计算开销。ML-KEM 等方案均采用正规形式。
6.3 最坏情形到平均情形归约
Regev 证明了 LWE 问题的困难性可以归约到格上的最坏情形困难问题：如果存在高效算法求解（判定）LWE，则存在量子算法在多项式时间内求解 GapSVP 和 SIVP 的 \(\tilde{O}(n/\alpha)\) 近似版本。这一归约的重要性在于：密码学中通常需要平均情形困难性（对随机实例困难），而 LWE 的困难性可以追溯到格问题的最坏情形困难性——即使最坏情形下的格实例也至少与随机 LWE 实例同样困难。
Peikert（2009）后来给出了经典归约（不依赖量子计算），条件略有不同。Brakerski 等人（2013）进一步将归约推广到更宽泛的参数范围。这些归约为 LWE 基方案的安全性提供了坚实的理论基础。
笔者认为，LWE 的最坏情形到平均情形归约是格密码学区别于所有其他后量子候选方案的根本理论优势，其重要性怎么强调都不过分。在传统密码学中，我们无法证明 RSA 的安全性归约到整数分解的最坏情形——可能存在某些「特殊结构」的 RSA 模数比随机模数更容易分解。对于编码基和多变量基的后量子方案，情况类似：它们的安全性依赖于随机实例的困难性假设，而非最坏情形保证。但 Regev 的归约告诉我们，破解一个随机 LWE 实例至少与解决该维度上最困难的格问题一样难。这意味着攻击者无法通过「挑选弱实例」来走捷径——每一个实例都至少与最坏情形一样难。这种保证在理论密码学中几乎是独一无二的，也正是 NIST 在后量子标准化中最终倾向于格基方案的深层原因。
6.4 LWE 的矩阵形式
在实际方案中，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})\)。
七、Ring-LWE 与 Module-LWE
7.1 效率瓶颈与结构化格
标准 LWE 的一个实际问题是效率：公钥矩阵 \(\mathbf{A}\) 的尺寸为 \(m \times n\)，当 \(n\) 取密码学安全级别所需的值（如 \(n \geq 512\)）时，公钥尺寸和运算复杂度均较大。为了克服这一瓶颈，密码学家引入了结构化格（Structured Lattice）的概念。
7.2 Ring-LWE
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）上的困难问题，而非一般格。理想格具有额外的代数结构，这引发了学术界关于该结构是否可能被利用来加速攻击的持续讨论。目前尚无针对理想格的显著量子或经典加速。
7.3 Module-LWE
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 高效运算的同时，降低了对理想格特殊结构的依赖，被认为在效率与安全假设保守性之间取得了良好的平衡。
7.4 NTRU 格
NTRU 格可以视为 RLWE 的”近亲”。NTRU 加密（Hoffstein, Pipher, Silverman, 1998）的安全性依赖于在特定多项式环上求解短向量问题。与 LWE 家族不同，NTRU 的归约并不直接来自最坏情形格问题，但其实际安全性经过二十余年的密码分析检验，被认为在适当参数下是可靠的。FALCON 签名方案基于 NTRU 格上的 GPV 框架。
八、基于 LWE 的基本构造
8.1 Regev 加密方案
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 问题的困难性。
8.2 对偶 Regev 加密
对偶 Regev（Dual Regev）加密将密钥生成与加密过程对调：公钥仍然是一组 LWE 样本，但秘密向量在加密时选取。这一变体在理论分析中更为方便，且与基于身份的加密（IBE）等高级构造的联系更为紧密。Gentry、Peikert 和 Vaikuntanathan（2008）在对偶 Regev 框架下构建了基于格的 IBE 方案。
8.3 GPV 签名框架
GPV 框架（Gentry, Peikert, Vaikuntanathan, 2008）是基于格的 Hash-and-Sign 签名范式。其核心思想是：签名者持有一组格的”陷门基”（Trapdoor Basis），即一组特别短的格基；验证者仅知道格本身（通过公钥矩阵 \(\mathbf{A}\) 描述）。签名时，签名者将消息散列到格的陪集（Coset）中，利用陷门基采样一个短的陪集向量作为签名。验证者检查签名是否属于正确的陪集且足够短。
陷门采样（Trapdoor Sampling）是 GPV 框架的技术核心。Micciancio 和 Peikert（2012）给出了高效的陷门生成与离散高斯采样算法，使得 GPV 框架在实践中可行。FALCON 签名方案即是 GPV 框架在 NTRU 格上的实例化。
8.4 从 CPA 到 CCA 安全
上述基本方案仅达到 CPA 安全。在实际部署中通常需要 CCA 安全（抗选择密文攻击）。Fujisaki-Okamoto（FO）变换是将 CPA 安全的 KEM/PKE 提升为 CCA 安全的标准工具。ML-KEM 正是将基于 MLWE 的 CPA 安全方案通过 FO 变换得到 CCA 安全 KEM 的产物。FO 变换的核心思想是在解密过程中重新加密并比对密文，以检测篡改。
九、格问题的安全性评估
9.1 Core-SVP 方法论
格密码方案的安全性评估通常采用 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}\)（量子筛法估计）。
9.2 格估计器（Lattice Estimator）
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 在后量子标准化过程中广泛使用了格估计器的结果。
9.2.1 格估计器使用示例
以下以一组接近 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 + 筛法）来估计攻击代价，但无法排除明天就有人发现全新的攻击范式。更令人不安的是，格问题的最坏情形到平均情形归约虽然在理论上极为优美，但归约中的参数损失意味着实际安全性与理论保证之间存在显著的间隙。我们本质上是在用「尚未被证伪」的硬度估计来保护未来数十年的通信安全——这种赌注的规模，值得每一位从业者保持清醒的敬畏。
9.3 NIST 安全级别映射
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. 深度限制成本）仍在讨论中，不同的成本模型可能导致数个比特的安全性差异。
9.4 开放问题与未来方向
格密码安全性评估仍有若干悬而未决的问题。格筛法的实际内存瓶颈能否被新技术克服？理想格和模格的代数结构是否隐藏着尚未发现的攻击？量子计算对格问题的加速是否仅限于平方根级别？这些问题的答案将直接影响后量子密码参数的选取和标准的长期可靠性。
密码学界目前的共识是：在保守的参数选取下，格密码方案的安全性是可信的。但正如历史上每一种密码学假设一样，持续的密码分析研究是保持信心的必要条件。理解本文介绍的数学基础，是参与这一持续研究过程的第一步。
密码学百科系列 · 第 37 篇
← 上一篇：离散对数与配对密码学 | 系列目录 | 下一篇：概率论与密码分析 →