格密码学 (Lattice-based Cryptography)

教程导读：把格密码学算一遍

格密码学（Lattice-based Cryptography） 研究的是同一件事：把高维空间里的整数点阵变成可以证明安全的加密、签名与同态计算工具。本教程的主线只有一条——先动手算一个小例子，再上升原理。每个概念都从一张草稿纸、一段十几行的代码或一次手工迭代开始，而不是从定义堆砌开始。

「Lattice」这个词，正在从数学系的课堂悄悄搬进你的浏览器、手机和云机房。它背后是一整套被称为后量子密码（Post-Quantum Cryptography）的工程迁移：RSA 和椭圆曲线依赖的两个困难问题——大整数分解与离散对数——在量子计算机面前不堪一击，而格上的困难问题至今没有出现同等量级的量子攻速。于是全球标准组织把下一代公钥密码的宝押在了这片整数点阵上。理解格密码学，等于拿到了未来十年基础设施安全演化的入场券。

为什么这本教程与众不同

市面上讲格密码学的材料分两类：一类是论文与专著，数学密度极高，适合研究者；另一类是科普文章，只讲故事不给算法。这本教程走中间那条路，也是被长期忽视的那条路——可动手的工程视角。你会在第二张草稿纸上完整跑通一轮 LWE 加密；会在第六章亲手做一次 LLL 规约，盯着一个歪斜的基一步步变正交；会把 Kyber 与 Dilithium 的官方参数表逐项摊开对照，算出每字节的代价。

我们的信念是：格密码学里那些"吓人"的东西——对偶格、高斯采样、安全归约——绝大多数都能在二维或三维的小例子里找到直觉。二维能画出来，三维能想出来，剩下的一百维只是把同一件事重复一百遍。

全册知识地图

学习路径不是线性的，但依赖关系是硬的：不认识格点就谈不上格上的困难问题，不理解 LWE 就读不懂 Kyber，没见过 LLL 的迭代过程就无法理解安全强度估算为什么是一笔账。下图给出章与章之间的依赖关系，箭头方向表示"学过后再往右走会顺畅得多"。

图：全册知识地图与学习依赖

你将按什么顺序动手

全册 8 章，每章内部都遵循同一个节奏：先算、再看、后推。先把一个小例子在纸面或代码里算完，得到具体数字；再回头看这个例子暴露了什么结构；最后才给一般化的定义与定理。各章的"动手锚点"如下。

• 第 1 章：在坐标纸上画出一个由两个基向量张成的格，亲手验证同一个格可以有无数组基，并发现"好基/坏基"在手感上的差别。
• 第 2 章：用一个 17 为模数的玩具 LWE 实例，从加密到解密逐行验算；再做一个 SIS 哈希的小实验，亲眼看到抽屉原理如何变成安全性的来源。
• 第 3 章：把"破解方案"到"最坏情况格问题"的归约链条画成一串多米诺；再用攻击成本公式对着一组参数算安全位数。
• 第 4 章：把第 2 章的玩具 LWE 加密升级成 Kyber 的骨架，逐项对照官方参数表；给 Dilithium 的拒绝采样算一次噪声余量。
• 第 5 章：用一个奇数为模的整数玩具方案体验同态加法与乘法，亲眼看噪声如何膨胀；再对照 BFV、CKKS、TFHE 三大家族的选型表。
• 第 6 章：完整手工迭代一轮二维 LLL，记录每步的约简与交换；然后把 BKZ、枚举、筛法的成本公式排成一条难度阶梯。
• 第 7 章：摊开 NIST 标准的全部参数与尺寸数字，算一次与 RSA、ECC 的体积差；走一遍 TLS 混合密钥交换的实际报文流程。
• 第 8 章：对比 NTRU 与 Kyber 的构造哲学；用参数估计工具的工作流对一组自选参数做一次评估。

需要多少数学基础

三样东西，都不深。线性代数：会矩阵乘向量、知道什么是正交与投影即可，Gram-Schmidt 正交化会在第 1 章现场推导。模运算：会算"除以 q 的余数"、知道负数怎么取模即可，第 2 章第一节会带着算。概率直觉：知道"中心化的随机小误差大概率接近零"就够用，离散高斯分布出现时我们会画出它的形状。

高等代数里的行列式、环论里的多项式商环，都会在用到的地方现讲现用。本教程刻意避免为三行公式铺垫三十页代数——那是专著的任务，不是工程师教程的任务。

配套约定

全书代码以 Python 为主，只依赖标准库或 numpy；所有示例都可以原样贴进解释器跑出与正文一致的数字。书中出现的格点图与结构图，坐标都给了具体数值，建议你至少挑两张亲手重画一遍——画图的过程会逼着你确认自己真的理解了基向量怎么张成格点。

参数与尺寸数据以 NIST 正式标准（FIPS 203、204、205）及各方案官方规格书为口径；引用的工程性能数字会注明来源口径，因为同一算法在不同 CPU 与实现下的周期数可以差十倍。凡是没有把握到能写在纸上的数字，我们宁可写"量级"而不写假精确值——这个习惯本身就是格密码工程文化的一部分：参数即安全，数字必须可追溯。

下一站：第 1 章。拿两张坐标纸，我们把"格"这个主角请出来。