CRYSTALS-Kyber 后量子密钥封装机制的公钥加密过程 我将为您讲解CRYSTALS-Kyber的公钥加密过程，这是NIST后量子密码标准化项目中选定的密钥封装机制。 一、算法背景 CRYSTALS-Kyber是基于格上带错误学习问题（MLWE）的后量子公钥加密方案，由三个核心算法组成：密钥生成、加密和解密。今天重点讲解加密过程。 二、数学基础 环结构：Kyber在多项式环R_ q = Z_ q[ X ]/(X^n + 1)上操作，其中n=256，q=3329 向量和矩阵：使用维度为k的向量和k×k矩阵（k取值2,3,4对应不同安全级别） 编码：需要将消息和随机数编码为环上的多项式 三、加密过程详细步骤 步骤1：输入准备 公钥pk = (t, ρ)，其中t是k维向量，ρ是随机种子 随机消息m ∈ {0,1}^{256}（32字节） 随机对称密钥K ∈ {0,1}^{256} 步骤2：随机数生成 使用哈希函数H(·)生成随机向量r r ← NTT(Compress(H(m || K), 1)) // 将随机数压缩并转换为NTT域 生成随机矩阵A ∈ R_ q^{k×k} A ← Parse(PRF(ρ)) // 从种子ρ确定性生成 步骤3：错误项生成 生成错误向量e1 ∈ R_ q^k e1 ← SampleFromBη() // 从离散高斯分布采样 生成错误多项式e2 ∈ R_ q e2 ← SampleFromBη() 步骤4：密文计算 计算向量u ∈ R_ q^k： u = NTT^{-1}(A^T ◦ NTT(r)) + e1 // 其中◦表示矩阵向量乘法的NTT域运算 计算多项式v ∈ R_ q： v = NTT^{-1}(t^T ◦ NTT(r)) + e2 + Encode(m) // Encode(m)将消息m编码为环元素 步骤5：密文压缩 压缩u：u' = Compress(u, d_ u) // d_ u是压缩参数（通常为11比特） 压缩v：v' = Compress(v, d_ v) // d_ v是压缩参数（通常为5比特） 步骤6：最终输出 密文c = (u', v')，大小约为： Kyber512: 768字节 Kyber768: 1088字节 Kyber1024: 1568字节 四、技术要点解析 NTT优化 ： 所有多项式乘法在数论变换（NTT）域进行 NTT将复杂度从O(n²)降至O(n log n) Kyber使用负包裹卷积NTT实现高效乘法 错误处理 ： 错误项e1, e2确保方案基于MLWE问题的安全性 压缩操作引入的误差需要在解密时正确处理 错误边界经过精心设计以保证正确性 安全性考虑 ： 随机预言机模型：使用哈希函数模拟理想随机函数 离散高斯分布：提供统计安全性和抗侧信道攻击能力 参数选择：平衡安全性和效率，抵抗已知格攻击 这个加密过程展示了现代格密码的高效实现技术，特别是NTT优化和精心设计的压缩方案，使其在保持后量子安全性的同时具有实用性能。