CRYSTALS-Kyber 后量子密钥封装机制的解密过程 我将详细讲解CRYSTALS-Kyber的解密过程，这是第一个被NIST选为标准的后量子密钥封装机制（KEM）。 题目描述 Kyber是基于格上带错误学习问题（MLWE）的密钥封装机制。解密过程的核心任务是：当收到密文(c₁, c₂)时，使用私钥sk正确恢复出封装密钥K。这个过程涉及多项式运算和错误补偿，需要精确处理计算误差。 解题过程详解 第一步：密文解析与私钥准备 输入：密文(c₁, c₂)，私钥sk = s（一个多项式向量） 操作： 将密文c₁解析为多项式向量â（编码的LWE实例A） 将密文c₂解析为多项式b（编码的LWE实例b） 从私钥中提取秘密向量s 关键点：c₁和c₂是经过压缩的，需要先进行解压缩操作恢复到多项式环R_ q = Z_ q[ x ]/(xⁿ+1)上的元素。 第二步：核心解密计算 计算公式：m' ← c₂ - sᵀ·c₁ 具体步骤： 计算内积sᵀ·c₁：这是私钥向量s与密文向量c₁的点积 执行减法：c₂减去上一步的结果 所有运算在模q下进行 数学原理：这实际上是在求解mLWE问题的近似解，还原出加密时添加的错误和消息。 第三步：错误补偿与消息恢复 操作过程： 将m'的系数从[ 0, q-1]范围映射到[ 0, 255 ]范围 使用Decompress函数：对每个系数执行四舍五入到最近的倍数操作 具体计算：m = Decompress(m', 1) = ⌊(m' × 2)/q⌉ mod 2 技术细节：这个步骤巧妙地利用了模数q和系数缩放来消除加密时引入的小误差，从而准确恢复出原始消息比特。 第四步：密钥派生 最终步骤： 将恢复的消息m作为输入到密钥派生函数KDF 生成共享密钥K = KDF(m) 安全性考虑：即使攻击者获得密文，没有私钥也无法正确执行错误补偿，因此无法得到正确的共享密钥。 关键难点与解决方案 错误处理：解密必须容忍加密时引入的随机误差，通过合理的参数选择和误差边界保证正确性 精度控制：压缩/解压缩操作需要精心设计以避免累积误差 参数匹配：所有计算必须严格遵循加密时使用的相同参数集（如q, n的值） 这个解密过程展示了如何通过巧妙的代数设计，在存在计算误差的情况下仍能可靠恢复共享密钥。