1. 格密码导论
在进入格密码的具体构造之前，先要建立一个清晰的直觉：格（lattice）并不是某种神秘的代数对象，而是欧几里得空间中一组离散、周期排列的点。给定 n 个线性无关的向量 b1, …, bn ∈ ℝn，它们的所有整数线性组合构成一个格：
L(B) = { z₁·b₁ + z₂·b₂ + … + zₙ·bₙ | zᵢ ∈ ℤ }矩阵 B 称为格的一组基。关键点在于：同一个格可以有无穷多组不同的基。有的基向量短且接近正交，有的基向量长且高度倾斜，但它们张成的点集完全相同。这一“同一对象、多种描述”的性质，正是格密码安全性的几何根源——攻击者拿到的往往是一组“坏基”，而合法用户持有一组“好基”。
围绕格，密码学最关心两类困难问题。其一是最短向量问题（SVP）：在格中找出非零的最短向量；其二是最近向量问题（CVP）：给定空间中的目标点，找出格中离它最近的点。二者在一般维度下都被认为是计算困难的，且目前没有已知的量子算法能在多项式时间内求解。格密码的构造，本质上就是把“求解 SVP/CVP”嵌入到密钥恢复过程中，使得拥有陷门（好基）的一方可以轻松求解，而没有陷门的一方只能面对坏基苦苦挣扎。
上图左右两侧画的是同一个格：左侧基向量短且接近垂直，格点结构一目了然，最短向量几乎可以直接看出；右侧基向量长且倾斜，格点看起来杂乱，最短向量被“藏”了起来。攻击者通常只能拿到右侧这样的坏基，而解密方持有左侧的好基。这种“几何描述差异”带来的计算不对称，就是格密码的核心安全假设。
发展脉络与在后量子密码学中的地位
格密码并非新事物。早在 1982 年，Lenstra、Lenstra 和 Lovász 提出的 LLL 格基约化算法就展示了格在算法数论中的威力；1996 年 Ajtai 证明了格上存在最坏情况困难问题，并给出了从最坏情况到平均情况的归约，这为格密码奠定了理论基础。1999 年 Hoffstein、Pipher 和 Silverman 提出的 NTRU 是最早的实用格密码方案之一。2016 年前后，基于容错学习问题（LWE）及其环上变体 Ring-LWE 的方案迅速成熟，成为后量子标准化竞赛的主力。
在 NIST 后量子密码标准化进程中，格密码占据了最核心的位置：用于密钥封装的 CRYSTALS-Kyber（现标准名 ML-KEM）和用于数字签名的 CRYSTALS-Dilithium（ML-DSA）、Falcon 均属于格密码家族。相比基于编码、哈希或多变量多项式的方案，格密码的优势在于：安全性归约清晰、密钥与密文尺寸相对可控、运算以整数和多项式为主、易于在软硬件上高效实现，并且能同时支撑加密、密钥交换和签名等多类原语。
需要强调的是，格密码的安全性目前建立在“没有已知高效量子算法求解 SVP/CVP”这一假设之上，而不是已经被证明的绝对安全。因此，参数选择必须留出足够的安全余量，这也是本课程后续要反复讨论的核心问题。
本课程的学习路径与核心目标
本课程共 30 章，整体遵循“概念—构造—参数—分析—实践”的递进路线。第一阶段建立几何与代数基础，理解格、基、行列式、对偶格以及 SVP/CVP 的精确含义；第二阶段进入 LWE 与 Ring-LWE，掌握从“带噪声线性方程”到“密钥封装”的完整构造链条；第三阶段聚焦参数安全分析，学习如何用格基约化估计工具评估攻击复杂度，理解维度 n、模数 q、噪声分布宽度 σ 三者之间的制约关系；第四阶段通过示例实现与测试，把公式落到可运行的代码与可观察的数据上。
学习本课程后，你应当能够独立完成三件事：第一，给定一组格基，判断它属于“好基”还是“坏基”，并说明理由；第二，读懂一个 LWE 或 Kyber 类方案的公开参数，指出每个参数在安全性与效率之间扮演的角色；第三，使用格基约化估计方法，对一个示例参数集给出粗略的安全等级判断，并说明判断依据。下面给出一个贯穿课程的参数观察示例，帮助建立“参数如何影响安全”的初步感觉：
示例参数（仅用于教学演示，非实测结论）：
维度 n = 256
模数 q = 3329
噪声宽度 σ ≈ 1.0 ~ 3.2
观察点：n 增大 → 格维度升高 → 攻击复杂度上升，但密钥与运算量同步增大
q/σ 增大 → 噪声相对模数变小 → 攻击者更容易区分噪声 → 安全性下降这段示例说明了一个贯穿全课程的基本张力：安全性与效率并非独立可调。维度 n 提升会同时抬高攻击成本和实现开销；模数 q 与噪声 σ 的比值则直接决定 LWE 问题的难度。后续章节会把这些定性描述转化为可计算的估计流程。
最后需要建立一种正确的安全观：格密码的“后量子安全”不是一句口号，而是由具体的困难问题假设、具体的参数和具体的攻击模型共同支撑的。本课程不会停留在名词介绍，而是会带你一步步看清参数背后的数学约束与工程取舍，最终能够对一组真实参数说出“它为什么这样选、风险在哪里”。