4. 基于格的密码学基础
后量子密码的迁移之所以在近几年加速，很大程度上是因为格（Lattice）这一数学结构同时提供了“抗量子攻击”和“可工程化”两个条件。理解格密码，不必从高深的代数数论出发，抓住三个关键词即可：格点、噪声、困难问题。本节围绕格的基本概念、LWE 与 SIS 两类核心问题、安全性假设，以及 Kyber、Dilithium 的设计思路展开，帮助你在评估厂商方案时看懂其背后的安全逻辑。
一、格是什么：离散的周期性点阵
直观地说，格是 n 维空间中由一组线性无关的基向量 b₁, b₂, …, bₙ 的所有整数系数线性组合构成的点集：
L = { a₁·b₁ + a₂·b₂ + … + aₙ·bₙ | aᵢ ∈ ℤ }二维情形下，它就像一张无限延伸、规则排列的点阵。同一个格可以由无数组不同的基表示，其中有些基向量短而“正交”，有些则长而“歪斜”。这种“同一对象、多种描述”的特性，正是格密码安全性的来源之一：给定一个“坏基”，要找到格中短向量或最近格点，计算上极其困难。
格密码依赖的经典困难问题主要有两个：最短向量问题（SVP）——在格中找到长度最短的非零向量；最近向量问题（CVP）——给定空间中的一点，找到离它最近的格点。在高维情形下，这两个问题目前没有已知的量子多项式时间算法，这构成了格密码抗量子的基础。
二、LWE 与 SIS：两类互补的困难问题
LWE（Learning With Errors，带误差学习）是“求解型”问题。给定矩阵 A 和向量 b = A·s + e（mod q），其中 s 是秘密向量，e 是服从某种小分布（如离散高斯）的噪声向量，攻击者需要从 (A, b) 中恢复 s。如果没有噪声 e，这就是一个普通的线性方程组，高斯消元即可求解；正是噪声把问题“搅浑”，使其归约到格上的困难问题。LWE 是公钥加密和密钥封装的主流基础。
SIS（Short Integer Solution，短整数解）是“寻找型”问题。给定矩阵 A，要求找到一个非零的短向量 x，使得 A·x = 0（mod q）。SIS 与 LWE 在结构上互为对偶，通常用于构造哈希函数和数字签名。
两者的关系可以这样理解：LWE 关心“带噪声的线性方程能否解出秘密”，SIS 关心“能否找到满足线性约束的短向量”。它们共同支撑起格密码的算法家族。
三、安全性假设：为什么“难”可以量化
格密码的安全性不是一句“很难破解”，而是建立在可归约的安全证明之上。其逻辑是：如果存在一个算法能攻破基于 LWE 的加密方案，那么就能用它构造出求解格上困难问题的算法。因此，只要格问题足够难，方案就安全。
工程上更常用的是模块格（Module-Lattice）假设，即 MLWE 与 MSIS。它们把向量元素从整数换成多项式环 R_q = ℤ_q[x]/(xⁿ+1) 中的元素，在保持困难性的同时大幅降低密钥和运算开销。安全性通常用“比特安全强度”衡量，例如 Kyber-768 被评估为约 NIST 安全等级 3（对应 AES-192 量级）。需要强调的是，这些数值来自对已知攻击（格基约减、对偶攻击等）的评估，属于基于当前最佳攻击的估计，而非数学上的绝对下界。
四、Kyber 与 Dilithium 的设计思路
Kyber（ML-KEM）用于密钥封装。其核心是一个基于 MLWE 的公钥加密方案：公钥包含矩阵 A 与向量 t = A·s + e，私钥为 s。封装时，发送方用公钥加密一个随机共享密钥并附带密文；解封装时，接收方用私钥解密并做“再加密校验”，若密文不匹配则输出一个伪随机值，从而抵御选择密文攻击。Kyber 的工程亮点在于：参数小（Kyber-768 公钥约 1184 字节、密文约 1088 字节）、运算以 NTT（数论变换）加速多项式乘法，适合在嵌入式与网络设备中落地。
Dilithium（ML-DSA）用于数字签名。它采用“Fiat-Shamir with Aborts”范式：签名者反复采样短向量 y，计算承诺 w = A·y，再对消息哈希得到挑战 c，最后输出 z = y + c·s。若 z 的范数超过阈值则丢弃重来，以保证签名不泄露私钥信息。验证方检查 A·z − c·t 是否等于承诺的哈希。Dilithium 同时依赖 MLWE 与 MSIS 的困难性，签名尺寸约 2–3 KB，比传统 ECDSA 大，但在可接受范围内。
五、迁移中的现实考量
格密码并非没有代价。密钥和签名尺寸增大，会影响 TLS 握手包大小与证书链传输；部分算法对侧信道攻击敏感，实现时需采用常数时间编码与掩码技术。企业在上线前应做混合模式试点，例如在 TLS 1.3 中同时协商 X25519 与 ML-KEM，既保留经典安全性，又提前验证后量子组件的兼容性。理解 LWE 与 SIS 的困难性来源，能帮助你在面对“某方案号称抗量子”的宣传时，判断其是否真正建立在经过同行评审的格假设之上。