格方案中的安全证明与归约

密码方案的安全性证明是一种形式化的数学论证，用于说明攻破该方案意味着能够解决某个底层困难问题。证明并不保证绝对安全；它表明，任何针对该方案的高效攻击者都可以被转化为一个能够高效解决该困难问题的求解器。如果该困难问题难以求解，那么该方案就是安全的。

Regev 在 2005 年发表的奠基性证明表明，能够在多项式时间内解决判定性 LWE 的算法，可用于解决 n 维格上的最坏情况 GapSVP（间隙最短向量问题）。该归约是量子的：它使用量子采样过程，将 LWE 求解器转化为格求解器。这意味着在量子计算条件下，LWE 至少与最坏情况格问题一样困难。

Regev 的归约并不紧致：归约中的多项式因子意味着，证明所保证的安全级别会比目前已知的最佳攻击所表明的安全级别略弱。在实际选择参数时，密码学家会使用目前已知最佳攻击所提供的具体安全性（通过格估计器计算），而不是理论归约界限，因为归约结果较为保守。

基于 LWE 的加密方案可以通过混合论证证明具有 IND-CPA（选择明文攻击下不可区分）安全性。证明表明，IND-CPA 区分器可以推出一个 LWE 区分器。在第一个混合步骤中，真实密文被替换为均匀随机字符串；根据 LWE 假设，可以得到不可区分性。这为基础的基于格的加密提供了简洁的安全性证明。

对于 TLS 中使用的密钥封装机制，仅有 IND-CPA 安全性并不足够：它们还需要 IND-CCA2（选择密文攻击）安全性。Fujisaki-Okamoto（FO）变换可以将任意 IND-CPA 方案转换为随机预言机模型（ROM）中的 IND-CCA2 KEM。ML-KEM 对底层模块-LWE 加密应用了 FO 变换的一个变体，从而提供实际部署所需的 CCA2 安全性。

随机预言机模型（ROM）将哈希函数建模为真正随机的函数。包括 FO 变换在内的许多安全性证明都需要 ROM。在实践中，SHA-3 等哈希函数并不是真正的随机预言机，因此 ROM 中的证明无法在标准模型中保证安全性。不过，ROM 证明已被密码学界广泛接受为安全性的有力证据。

标准模型证明不对哈希函数作任何理想化假设，因此严格强于 ROM 证明。大多数实际的基于格的方案都采用 ROM 证明，因为针对基于格的 KEM 的标准模型 CCA2 证明复杂得多，而且会产生更差的具体参数。NIST 接受了基于 ROM 的 ML-KEM 证明，认为它们足以满足目标安全级别。

ML-KEM 的安全性证明分为两步。首先，在 M-LWE 假设下证明底层模块-LWE 加密具有 IND-CPA 安全性。其次，Fujisaki-Okamoto 变换（具体来说，是 Kyber 中使用的 T 和 U 变换）在量子随机预言机模型（QROM）中将其提升为 IND-CCA2 安全性，从而应对以叠加态查询随机预言机的攻击者。

Albrecht、Player 和 Scott 开发的格估计器是计算基于 LWE 的方案具体安全性的标准工具。它对目前已知最佳格攻击的成本进行建模（包括采用筛法或枚举的 BKZ），并针对给定参数（n、q、sigma）输出估计的比特安全性。随着新算法和硬件成本模型的发布，该工具会定期更新。

块 Korkine-Zolotarev（BKZ）算法是实际应用中最佳的格约化算法。块大小为 beta 的 BKZ 使用最佳筛法算法，以大约 2^{0.292*beta} 次门操作的复杂度找到短向量。对于 ML-KEM-768，估计的经典安全性约为 180 位，量子安全性约为 164 位，远高于 192 位目标。

渐近安全性证明表明，当参数足够大时，方案是安全的，但并未说明在实践中“足够大”究竟意味着什么。具体安全性分析通过估计针对所选参数的最佳攻击的实际成本，填补了这一空缺。后量子标准化高度依赖具体安全性分析，并选择能够抵御预期量子硬件攻击的参数，其考察时间范围为 30 年。

在 ML-KEM 中，哪种变换用于将 IND-CPA 的基于格的加密提升为 IND-CCA2 安全性？

基于格的方案通过将方案的安全性归约为 LWE 或 SVP 的困难性来进行安全性证明。Regev 的归约保证 LWE 至少与最坏情况格问题一样困难。Fujisaki-Okamoto 变换在 ROM 中将 IND-CPA 提升为 IND-CCA2。具体安全性通过格估计器结合 BKZ 复杂度模型进行评估。归约紧性方面的差距意味着，实际参数的选择依赖于攻击成本估计，而不能仅依赖归约界限。