4. Kyber/Dilithium算法精讲
Kyber与Dilithium是NIST后量子标准化中最终入选的两种格密码算法：Kyber用于密钥封装（KEM），Dilithium用于数字签名。二者都建立在模格上的LWE/SIS类困难问题之上，但构造范式、安全归约路径和参数取舍差异明显。理解它们的关键，不是记住参数表，而是看清“困难问题→中间安全模型→最终方案”这条构造链，以及多项式乘法这一性能瓶颈是如何被NTT解决的。
一、Kyber的IND-CPA与IND-CCA2构造
Kyber的底层是一个公钥加密方案Kyber.CPAPKE，其安全性目标是IND-CPA（选择明文攻击下的不可区分性）。它的结构接近Regev加密的环上版本：私钥为向量 s，公钥为 (A, t = A·s + e)，其中 A 是环 R_q = Z_q[X]/(X^n+1) 上的矩阵，e 是小系数误差向量。加密时把消息编码为多项式 m，选取随机向量 r 与小误差 e1、e2，输出密文 (u, v) = (Aᵀ·r + e1, tᵀ·r + e2 + ⌈q/2⌉·m)。解密计算 v − sᵀ·u，结果近似为 ⌈q/2⌉·m 加上小噪声，再通过舍入恢复消息比特。其IND-CPA安全性可归约到判定性MLWE问题：若攻击者能区分密文，就能区分MLWE样本。
但IND-CPA不足以保证实际KEM安全，因为KEM需要抵抗选择密文攻击（IND-CCA2）。Kyber采用Fujisaki-Okamoto（FO）变换，把CPA方案升级为CCA2安全的KEM。核心思想是“可验证加密”：加密时不再使用外部随机数，而是用消息 m 与公钥哈希出的伪随机值 r = G(m‖H(pk)) 作为加密随机性；解密后重新加密，比较密文是否一致，不一致则输出拒绝符号 ⊥。这样攻击者无法构造合法但“被篡改”的密文来探测解密行为。最终共享密钥由 K = KDF(m‖H(c)) 导出，其中 c 是密文。Kyber的IND-CCA2安全性在随机预言机模型下归约到MLWE，并额外依赖对称原语（SHA3/SHAKE）的假设。
二、NTT与多项式乘法优化
Kyber与Dilithium的性能瓶颈都在多项式乘法。朴素卷积是 O(n²)，当 n=256 时约6.5万次乘加，而NTT（数论变换）把它降到 O(n log n)，约 256×8=2048 次蝶形运算。NTT本质是有限域上的FFT：选取满足 q ≡ 1 (mod 2n) 的素数 q，存在 2n 次本原单位根 ζ，把多项式从系数表示映射到NTT域，乘法变为逐点相乘。
Kyber取 q=3329，n=256，q−1=3328=13×256，满足条件；Dilithium取 q=8380417，q−1=8380416=2¹³×3×7×17，同样支持。由于环是 X^n+1（负循环），NTT分解为 n/2 个二次剩余对，实际使用“不完全NTT”把多项式拆成128个二次多项式，逐点乘法后再合并。工程实现中，蝶形运算的模乘用Montgomery或Barrett约减，避免昂贵的除法；Kyber的 q 小，可用16位整数运算，Dilithium的 q 大，需32位或64位中间量。NTT的另一个好处是密钥生成、加密、解密、签名、验签全部复用同一套变换，代码路径统一。
三、Dilithium的Fiat-Shamir with Aborts范式
Dilithium是签名方案，采用Fiat-Shamir with Aborts（FSwA）范式。它的基本流程是：私钥 s1、s2 小系数，公钥 t = A·s1 + s2。签名时选取掩码向量 y，计算 w = A·y，把 w 的高位部分 w1 与消息 μ 一起哈希得到挑战 c = H(w1‖μ)，再计算 z = y + c·s1。关键一步是“拒绝采样”：如果 z 的范数超过阈值 γ1，或 w 的低位部分 w0 不满足条件，就丢弃本次签名，重新选取 y。这个“abort”机制保证 z 的分布与 y 无关，从而不泄露私钥信息。
验签时，验证者计算 w' = A·z − c·t，检查 c = H(w'1‖μ) 且 z 的范数在界内。FSwA的安全性可归约到MLWE和自目标MSIS问题。与Kyber的FO变换不同，Dilithium不需要重加密比较，而是通过拒绝采样直接构造零知识证明式的签名。工程上，拒绝采样意味着签名时间不确定，平均需要尝试约4~7次（取决于参数集），这是Dilithium实现中必须处理的随机性来源。
四、参数集与安全级别
Kyber和Dilithium都提供三个安全级别，对应NIST的Category 1、3、5，大致等价于AES-128、AES-192、AES-256的经典安全强度。Kyber的参数集为Kyber512、Kyber768、Kyber1024，维度 k 分别为2、3、4，模数 q=3329，n=256。Dilithium的参数集为Dilithium2、Dilithium3、Dilithium5，维度 k×l 分别为 4×4、6×5、8×7，模数 q=8380417。安全级别越高，矩阵维度越大，密钥和签名尺寸也越大。
| 算法 | 参数集 | NIST级别 | 公钥尺寸 | 私钥尺寸 | 密文/签名尺寸 |
|---|---|---|---|---|---|
| Kyber | Kyber512 | 1 | 800 B | 1632 B | 768 B |
| Kyber | Kyber768 | 3 | 1184 B | 2400 B | 1088 B |
| Kyber | Kyber1024 | 5 | 1568 B | 3168 B | 1568 B |
| Dilithium | Dilithium2 | 2 | 1312 B | 2528 B | 2420 B |
| Dilithium | Dilithium3 | 3 | 1952 B | 4000 B | 3293 B |
| Dilithium | Dilithium5 | 5 | 2592 B | 4864 B | 4595 B |
五、密钥与签名尺寸分析
从尺寸看，Kyber的公钥和密文都在1~1.6 KB量级，远小于RSA-3072的384 B公钥但大于其密文，不过Kyber的密钥生成和封装速度比RSA快一个数量级以上。Dilithium的签名尺寸在2.4~4.6 KB，明显大于ECDSA的64~72 B，这是格签名“拒绝采样+大向量”带来的固有代价。工程迁移时必须评估：TLS握手中证书链膨胀、签名验证的带宽开销、以及嵌入式设备上的存储限制。
总结来看，Kyber与Dilithium共享MLWE困难问题与NTT加速，但Kyber用FO变换把CPA加密升级为CCA2 KEM，Dilithium用FSwA范式构造签名。参数集按NIST Category 1/3/5划分，尺寸随安全级别线性增长。工程实现的核心是NTT的模运算优化、拒绝采样的恒定时间处理，以及尺寸与性能的权衡。