【密码学百科】公钥密码的可证明安全：从 RSA-OAEP 到 Cramer-Shoup

自 Diffie 与 Hellman 在 1976 年提出公钥密码的概念以来，人们设计了大量公钥加密和签名方案。然而，仅仅构造出一个方案远远不够——我们必须回答一个根本问题：凭什么相信这个方案是安全的？早期的做法是依靠直觉和经验：如果一个方案公开多年无人攻破，就认为它是安全的。这种”无人攻破即安全”的思路存在显而易见的缺陷——攻击者可能只是还没有公开他的攻击方法。可证明安全(Provable Security)范式的出现彻底改变了这一局面。其核心思想是：将方案的安全性严格地归约(Reduction)到某个公认困难的数学问题上。如果有人能够攻破这个方案，那么他实际上就解决了那个被认为不可解的数学难题。这种归约式的论证将密码方案的安全性建立在坚实的数学基础之上，使得安全性分析从”猜测”走向”证明”。

本文将系统梳理公钥密码可证明安全的核心内容。我们从安全性定义出发，依次讨论 RSA-OAEP 在随机预言机模型(Random Oracle Model, ROM)下的 IND-CCA2 证明、Fujisaki-Okamoto 变换、Cramer-Shoup 在标准模型下的构造，再扩展到签名方案的可证明安全范式，最后讨论紧致归约的实践意义以及可证明安全框架自身的局限。

一、公钥加密的安全性定义回顾

先看一张图，把这一节的关键关系串起来。

graph TD
    A[困难假设] --> B[公钥构造]
    B --> C[ROM 或标准模型]
    C --> D[归约损失]
    D --> E[参数选择]

要证明一个方案安全，首先必须严格定义”安全”意味着什么。公钥加密的安全性定义经历了从直觉到形式化的漫长过程，最终形成了以不可区分性(Indistinguishability)为核心的层级体系。

IND-CPA(选择明文攻击下的不可区分性)是最基本的安全性目标。其安全游戏如下：攻击者获得公钥后，选择两段等长的明文 \(m_0\) 和 \(m_1\) 发送给挑战者；挑战者随机选择 \(b \in \{0, 1\}\)，将 \(m_b\) 的密文返回给攻击者；攻击者需要猜测 \(b\) 的值。如果任何多项式时间攻击者猜对的概率与随机猜测相比只有可忽略的优势，则称方案满足 IND-CPA 安全。IND-CPA 刻画的是一种被动窃听场景：攻击者只能观察密文，不能要求解密任何密文。

然而，真实世界中的攻击者往往具备更强的能力。IND-CCA1(午餐攻击下的不可区分性，又称非适应性选择密文攻击)允许攻击者在看到挑战密文之前，向解密预言机提交任意密文并获得对应的明文。但一旦挑战密文被发出，解密预言机就关闭了。这个定义由 Naor 和 Yung 在 1990 年首先形式化。

真正与实际应用场景匹配的定义是 IND-CCA2(适应性选择密文攻击下的不可区分性)，由 Rackoff 和 Simon 在 1991 年提出。在 IND-CCA2 游戏中，攻击者在收到挑战密文之后仍然可以继续查询解密预言机，唯一的限制是不能提交挑战密文本身。这一定义的强大之处在于它精确地模拟了许多实际攻击场景。例如，在电子邮件系统中，攻击者可以截获加密邮件，然后构造与之相关的新密文发送给接收方，通过观察接收方的行为来推断原文信息。1998 年 Bleichenbacher 对 PKCS#1 v1.5 的攻击就是这种场景的经典实例——攻击者反复向服务器发送精心构造的密文，根据服务器返回的错误信息逐步还原出 RSA 明文。

三种安全性定义之间存在严格的蕴含关系：IND-CCA2 蕴含 IND-CCA1，而 IND-CCA1 蕴含 IND-CPA。反方向则不成立——存在满足 IND-CPA 但不满足 IND-CCA1 的方案，也存在满足 IND-CCA1 但不满足 IND-CCA2 的方案。这种层级结构告诉我们，如果一个方案声称适合在真实网络环境中部署，那么它至少应当满足 IND-CCA2 安全性。

除了不可区分性，还存在基于不可延展性(Non-Malleability, NM)的安全性定义。Dolev、Dwork 和 Naor 证明了在 CCA2 攻击模型下，不可区分性和不可延展性是等价的，即 IND-CCA2 等价于 NM-CCA2。这一等价关系进一步巩固了 IND-CCA2 作为公钥加密安全性”黄金标准”的地位。

二、ElGamal 加密的安全性

ElGamal 加密是理解公钥加密可证明安全的最佳起点。在群 \(G\) 中，给定生成元 \(g\)，私钥为 \(x\)，公钥为 \(h = g^x\)。加密消息 \(m\) 时，选取随机数 \(r\)，计算密文 \((c_1, c_2) = (g^r, m \cdot h^r)\)。解密时利用 \(c_2 / c_1^x = m \cdot h^r / g^{rx} = m\) 即可恢复明文。

ElGamal 加密的 IND-CPA 安全性可以严格归约到判定性 Diffie-Hellman(Decisional Diffie-Hellman, DDH)假设上。DDH 假设断言：给定 \((g, g^a, g^b, g^c)\)，区分 \(c = ab\) 和 \(c\) 为随机值在计算上是不可行的。归约的思路十分清晰：假设存在一个攻击者 \(\mathcal{A}\) 能以不可忽略的优势攻破 ElGamal 的 IND-CPA 安全性，我们就可以构造一个算法 \(\mathcal{B}\)，利用 \(\mathcal{A}\) 作为子程序来解决 DDH 问题。具体而言，\(\mathcal{B}\) 收到 DDH 实例 \((g, g^a, g^b, Z)\)，将 \(g^a\) 作为公钥发送给 \(\mathcal{A}\)；当 \(\mathcal{A}\) 提交挑战明文对 \((m_0, m_1)\) 时，\(\mathcal{B}\) 将 \((g^b, Z \cdot m_b)\) 作为密文返回。如果 \(Z = g^{ab}\)，这就是合法的 ElGamal 密文；如果 \(Z\) 是随机的，密文中就不包含任何关于 \(m_b\) 的信息。因此，\(\mathcal{A}\) 的优势直接转化为 \(\mathcal{B}\) 解决 DDH 的优势。

然而，ElGamal 加密在 CCA 攻击下是完全不安全的。给定密文 \((c_1, c_2) = (g^r, m \cdot h^r)\)，攻击者可以构造新密文 \((c_1, c_2 \cdot g^s) = (g^r, m \cdot g^s \cdot h^r)\)，将其提交给解密预言机，获得 \(m \cdot g^s\)，从而恢复出原始明文 \(m\)。这种延展性(Malleability)是 ElGamal 不满足 IND-CCA2 的根本原因。ElGamal 的这一缺陷并非个例——几乎所有代数结构上的”朴素”加密方案都具有类似的延展性。如何在保留代数性质的同时抵抗选择密文攻击，成为公钥密码学中的核心挑战。正是为了回应这一挑战，Cramer 和 Shoup 构造了他们著名的加密方案。

三、RSA-OAEP 的 IND-CCA2 证明

RSA 加密本身仅是一个单向陷门置换(Trapdoor Permutation)，不直接构成一个完整的加密方案。要将其用于加密任意长度的消息，需要一个合适的填充方案。PKCS#1 v1.5 填充在 Bleichenbacher 攻击面前溃不成军，迫使密码学界寻找新的方案。Bellare 和 Rogaway 在 1994 年提出了最优非对称加密填充(Optimal Asymmetric Encryption Padding, OAEP)方案，其构造巧妙地利用了两轮 Feistel 网络。

OAEP 的编码过程如下：设消息为 \(m\)，选取随机数 \(r\)，计算 \(s = (m \| 0^{k_1}) \oplus G(r)\) 和 \(t = r \oplus H(s)\)，其中 \(G\) 和 \(H\) 是两个哈希函数。最终将 \((s \| t)\) 作为 RSA 的输入进行加密。解密时先还原 \((s \| t)\)，然后反向计算 \(r = t \oplus H(s)\) 和 \(m \| 0^{k_1} = s \oplus G(r)\)，最后检查末尾的 \(k_1\) 个零位是否正确。这个检查至关重要——它赋予了方案明文感知性(Plaintext Awareness)，使得攻击者在不知道随机数 \(r\) 的情况下几乎不可能构造出有效的密文。

OAEP 的安全性证明经历了有趣的曲折。Bellare 和 Rogaway 在 1994 年的原始论文中声称 RSA-OAEP 在随机预言机模型下是 IND-CCA2 安全的。然而，Shoup 在 2001 年指出原始证明存在缺陷：它只能证明 RSA-OAEP 在 RSA 置换具有”部分单向性”(Partial-Domain One-Wayness)条件下是安全的，而不是在标准的 RSA 假设下。具体来说，安全性归约的损失太大，使得从标准 RSA 假设出发无法得到有意义的安全性保证。

Fujisaki、Okamoto、Pointcheval 和 Stern(FOPS)在 2004 年最终给出了完整的证明，表明 RSA-OAEP 在随机预言机模型下确实是 IND-CCA2 安全的，前提是 RSA 问题本身是困难的。他们的证明策略分为两步：首先证明 OAEP 与任意部分单向的陷门置换结合时是 IND-CCA2 安全的；然后证明 RSA 的标准单向性蕴含部分单向性。后一步是关键的技术贡献——他们利用 RSA 的乘法同态性质，通过一个精巧的归约将部分单向性问题转化为标准 RSA 问题。

然而，RSA-OAEP 的安全性证明存在显著的紧致性问题。归约中的安全性损失与解密查询次数 \(q_D\) 相关。设攻击者对 RSA-OAEP 的优势为 \(\epsilon\)，则归约构造的 RSA 求解算法的优势大致为 \(\epsilon / q_D\)。在实际参数选取中，\(q_D\) 可能达到 \(2^{30}\) 或更大，这意味着为了保证 128 位安全性，RSA 模数需要比直觉上更大。这种非紧致的归约是 ROM 证明中的常见问题，也是密码学家追求标准模型证明的重要动机之一。

需要强调的是，随机预言机模型是一种理想化假设——它假设哈希函数的行为等同于一个真正的随机函数。Canetti、Goldreich 和 Halevi 在 1998 年构造了一个”病理性”的方案，在随机预言机模型下可证明安全，但用任何具体的哈希函数实例化后都不安全。这一结果表明，ROM 证明提供的安全性保证是有条件的，不能与标准模型证明相提并论。

ROM 失败案例与实践意义

CGH 反例的构造方式值得详细理解，因为它精确地揭示了 ROM 的局限性。其核心思想是：构造一个方案 \(\Pi'\)，它在内部检查随机预言机是否是”真正随机的”——如果预言机是真随机函数，方案行为正常；如果预言机是任何具体的（可计算的）哈希函数，方案就自动泄露私钥。在 ROM 中，预言机是不可计算的真随机函数，因此检查永远通不过，方案安全。但在实例化后，预言机是一个具体算法，检查通过，安全性崩溃。

从更技术的角度看，CGH 反例利用了可计算性与不可计算性之间的根本鸿沟。具体构造如下：给定一个已被证明在 ROM 下安全的方案 \(\Pi\)，构造新方案 \(\Pi'\)——\(\Pi'\) 的加密算法在执行正常加密之前，先执行一项额外检查。它选取预先确定的 \(n\) 个输入 \(x_1, \ldots, x_n\)，查询预言机得到 \(o_i = \mathcal{O}(x_i)\)，然后逐位验证这些输出是否与某个具体哈希函数 \(H\) 的输出一致（即检查 \(o_i \stackrel{?}{=} H(x_i)\) 是否对所有 \(i\) 成立）。若检查通过，\(\Pi'\) 将私钥直接附在密文中；否则正常执行 \(\Pi\) 的加密。在 ROM 中，真随机函数在这 \(n\) 个点上恰好与 \(H\) 一致的概率为 \(2^{-n \cdot \ell}\)（\(\ell\) 为输出位长），可忽略不计，因此 \(\Pi'\) 几乎总是正常加密，安全性证明照搬 \(\Pi\) 的证明即可。但当预言机被实例化为 \(H\) 本身时，检查恒定通过，私钥随每个密文一起泄露。这一构造之所以能”欺骗”ROM 证明，关键在于 ROM 将预言机建模为一个与所有可计算函数无关的理想对象——任何利用预言机”可计算性”的攻击策略在 ROM 证明中都不存在，但在实例化后立即生效。

这一反例虽然是人工构造的——没有理性的密码设计者会在方案中嵌入此类自毁逻辑——但它在数学上严格证明了一个根本性命题：不存在一个适用于所有方案的”ROM 安全蕴含实例化安全”的通用定理。换言之，ROM 证明是一种启发式保证而非绝对保证。这引出了一个实践中极为重要的问题：哪些 ROM 证明在实例化后仍然可靠？ 密码学界积累了以下经验性准则：

值得注意的一个积极发展是：Canetti、Jain 和 Scafuro 在 2019 年提出了 UC 可实例化随机预言机（UC-realizable ROM）的概念——在某些条件下，他们证明了特定的 ROM 方案可以在 UC 框架下安全地实例化。这为 ROM 证明的可靠性提供了更坚实的理论基础，尽管适用范围仍然有限。

综合来看，ROM 证明的实际价值可以从以下三个层面理解。第一，ROM 证明排除了所有”结构性攻击”——即不依赖哈希函数内部结构的通用攻击，而绝大多数实际密码攻击属于这一类。第二，ROM 证明不排除利用哈希函数特定弱点（如碰撞、长度扩展、差分特性）的攻击，但现代哈希函数（SHA-3、BLAKE3）的设计目标正是消除此类弱点。第三，标准模型替代方案可以完全规避 ROM 的理论缺陷，但代价显著：Cramer-Shoup 的密文含四个群元素（ElGamal 仅两个），Waters 签名的公钥大小与消息位长线性相关（256 位消息需 257 个群元素，远大于 Schnorr 签名的单元素公钥），且标准模型方案通常需要更特殊的数学结构（如双线性配对群），限制了可用的密码学实例化选择。因此，对于大规模部署的在线协议，ROM 方案在安全性与效率之间仍然提供了最好的平衡。

四、Fujisaki-Okamoto 变换

Fujisaki-Okamoto(FO)变换是一种通用技术，能够将仅满足 IND-CPA 安全的公钥加密方案升级为 IND-CCA2 安全的方案(或密钥封装机制，Key Encapsulation Mechanism, KEM)。这一变换在后量子密码学标准化进程中扮演了至关重要的角色。

FO 变换的基本思路如下：给定一个 IND-CPA 安全的公钥加密方案 \(\mathsf{PKE} = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})\)，构造新方案 $’ $ 时，加密消息 \(m\) 的过程变为：选取随机数 \(\sigma\)，计算密文 \(c = \mathsf{Enc}(pk, m; H(\sigma, m))\)，其中 \(H\) 是一个哈希函数，将 \((\sigma, m)\) 映射为加密所需的随机数。同时附加 \(\sigma\) 的承诺。解密时，先用私钥恢复 \(m\) 和 \(\sigma\)，然后重新加密验证密文的一致性——如果重新加密的结果与收到的密文不匹配，就拒绝解密。

这种”解密后重新加密验证”的策略被称为隐式拒绝(Implicit Rejection)机制。它的安全性直觉非常清晰：由于加密的随机数通过哈希函数与消息绑定，攻击者无法在不知道消息的情况下构造出有效的密文。在随机预言机模型下，攻击者要构造一个能通过验证的密文，就必须查询哈希函数 \(H\)，而这意味着攻击者实际上已经”知道”了明文，从而解密预言机对攻击者没有帮助。

FO 变换在 NIST 后量子密码标准化竞赛中得到了广泛应用。CRYSTALS-Kyber(现为 ML-KEM)、SABER、NTRU 等几乎所有基于格的 KEM 候选方案都采用了 FO 变换或其变体。具体而言，NIST 标准采用了 FO 变换的一个改进版本 \(\mathrm{FO}^{\not\perp}\)，其中解密失败时不返回错误符号，而是返回一个伪随机值。这种处理方式避免了解密失败信息可能导致的侧信道攻击。

FO 变换的安全性定理与直觉

FO 变换的安全性可以用如下定理精确刻画：

定理（FO 变换安全性，非形式化）：若 \(\mathsf{PKE}\) 是 IND-CPA 安全的公钥加密方案，且 \(\delta\)-正确（即解密失败概率至多为 \(\delta\)），则通过 FO 变换得到的 KEM \(\mathsf{KEM}'\) 在随机预言机模型下是 IND-CCA 安全的。具体地，对于任何发起至多 \(q_H\) 次随机预言机查询和 \(q_D\) 次解封装查询的攻击者 \(\mathcal{A}\)：

\[\mathsf{Adv}^{\text{ind-cca}}_{\mathsf{KEM}'}(\mathcal{A}) \leq q_H \cdot \mathsf{Adv}^{\text{ind-cpa}}_{\mathsf{PKE}}(\mathcal{B}) + q_D \cdot \delta\]

这一定理的证明思路可以概括为一个核心论点：解密预言机对攻击者毫无帮助。具体而言，归约算法 \(\mathcal{B}\) 在模拟解密预言机时，维护一张随机预言机 \(H\) 的查询表。当攻击者提交密文 \(c\) 请求解封装时，\(\mathcal{B}\) 遍历查询表中的每一条记录 \((m_i, r_i = H(m_i))\)，检查是否存在某个 \(m_i\) 使得 \(\mathsf{Enc}(pk, m_i; r_i) = c\)。如果找到，返回对应的密钥 \(K = \mathsf{KDF}(m_i)\)；否则返回一个伪随机值。这一模拟之所以正确，是因为在随机预言机模型下，攻击者构造有效密文的唯一途径是先查询 \(H\) 获取随机数——而这一查询会被 \(\mathcal{B}\) 记录下来。未查询 \(H\) 就”猜对”正确随机数的概率可忽略。

安全性损失因子 \(q_H\) 反映了归约的非紧致性——当 \(\mathcal{B}\) 需要将 IND-CPA 挑战嵌入到 FO 构造中时，它必须猜测攻击者会在哪一次 \(H\) 查询中提交与挑战密文对应的消息，而这一猜测的成功概率为 \(1/q_H\)。\(q_D \cdot \delta\) 项则来自解密失败的可能性：如果底层 PKE 有非零解密失败概率，攻击者可以利用解密失败事件区分正常与异常行为。这也是为什么 ML-KEM 等后量子方案特别强调将解密失败概率降至可忽略水平——ML-KEM-768 的解密失败概率约为 \(2^{-164}\)，确保 \(q_D \cdot \delta\) 项远小于安全性目标。

为使上述过程更加具体，考虑一个简化的例子。设底层方案为一个基于格的 IND-CPA 加密 \(\mathsf{LPE}\)，其加密需要一个随机向量 \(\mathbf{r}\)。未经 FO 变换时，攻击者可以将密文 \(\mathbf{c} = (\mathbf{c}_1, \mathbf{c}_2)\) 修改为 \((\mathbf{c}_1 + \Delta, \mathbf{c}_2)\) 并提交给解密预言机——由于格方案的近似线性性，解密结果可能泄露关于 \(\Delta\) 与明文的关系。施加 FO 变换后，加密改为 \(\mathbf{r} = H(m)\)、\(\mathbf{c} = \mathsf{LPE.Enc}(pk, m; \mathbf{r})\)。攻击者对密文的任何篡改都会导致解密后重新加密验证失败——因为 \(H(m')\)（其中 \(m'\) 是篡改后解出的错误消息）产生的随机数几乎必然与原始 \(\mathbf{r}\) 不同，使得重新加密的结果与收到的密文不匹配。攻击者要绕过这一检查，就必须事先查询 \(H(m')\) 以获得正确的随机数，但这意味着攻击者已经知道了 \(m'\)，解密预言机不再提供任何新信息。

Hofheinz、Hovelmanns 和 Kiltz(HHK)在 2017 年对 FO 变换进行了模块化分析，将其分解为若干独立的变换组件，并在量子随机预言机模型(Quantum Random Oracle Model, QROM)下给出了安全性证明。QROM 假设量子攻击者能够以量子叠加态查询随机预言机，这比经典 ROM 更为保守，也更适合后量子安全性分析。这一工作为后量子 KEM 的安全性论证提供了坚实的理论基础。

FO 变换的编译路径与安全性层级

HHK 的模块化分析将 FO 变换拆解为三个独立步骤，每个步骤对应一次安全性提升。理解这一编译路径有助于精确判断方案在不同攻击模型下的安全性：

编译路径：IND-CPA PKE → IND-CCA KEM

步骤 1: T 变换（去随机化）
  IND-CPA PKE → OW-PCA（单向性 + 明文检测攻击）PKE
  做法：将加密所用的随机数设为 r = H(m)，消除加密的概率性
  安全性依据：随机预言机的单向性

步骤 2: U 变换（隐式拒绝）
  OW-PCA PKE → IND-CCA KEM
  做法：解密后重新加密验证；验证失败时返回伪随机值而非 ⊥
  变体 U⊥：验证失败返回 ⊥（显式拒绝）
  变体 U⊬：验证失败返回 H'(s, c) 其中 s 为私钥种子（隐式拒绝）

步骤 3: 共享密钥派生
  从 m 和密文 c 派生共享密钥 K = KDF(m, c)

ML-KEM（FIPS 203）采用的具体编译路径是 T + U⊬，即使用隐式拒绝。选择隐式拒绝而非显式拒绝的原因是恒定时间实现——显式拒绝（返回 ⊥）会在控制流中引入一个可观察的分支，而隐式拒绝确保无论解封装成功还是失败，执行路径和时间开销都相同。以下是 ML-KEM 解封装的核心逻辑简化描述：

def ml_kem_decaps(sk, c):
    """ML-KEM 解封装（简化描述，展示 FO 隐式拒绝逻辑）"""
    # 步骤 1：使用私钥解密得到候选消息 m'
    m_prime = cpapke_decrypt(sk.dk, c)

    # 步骤 2：用 m' 重新派生随机数并重新加密
    K_bar, r = G(m_prime || H(sk.ek))  # G 是哈希函数
    c_prime = cpapke_encrypt(sk.ek, m_prime, r)

    # 步骤 3：恒定时间比较（关键！）
    # 如果 c == c_prime，共享密钥 K = KDF(K_bar || H(c))
    # 如果 c != c_prime，共享密钥 K = KDF(z || H(c))，z 是预存的随机种子
    # 注意：两个分支必须在恒定时间内完成，不可提前返回
    match = constant_time_compare(c, c_prime)
    K = KDF(select(match, K_bar, sk.z) || H(c))
    return K

这一设计的精妙之处在于：攻击者无法从解封装的输出中区分”合法密文”和”被篡改的密文”——两者都返回一个看似随机的共享密钥。这使得自适应选择密文攻击者从解密预言机中获得的信息为零。

五、Cramer-Shoup 加密

1998 年，Ronald Cramer 和 Victor Shoup 提出了第一个在标准模型下满足 IND-CCA2 安全的实用公钥加密方案。这一突破性成果的重要性在于它完全不依赖随机预言机假设，安全性直接归约到 DDH 假设和目标抗碰撞哈希函数(Target Collision Resistant Hash Function, TCR)的存在性上。

Cramer-Shoup 方案可以看作 ElGamal 加密的”加固”版本。其密钥生成过程如下：在群 \(G\) 中选取两个生成元 \(g_1, g_2\)，选取五个随机指数 \(x_1, x_2, y_1, y_2, z\)，计算 \(c = g_1^{x_1} g_2^{x_2}\)，\(d = g_1^{y_1} g_2^{y_2}\)，\(h = g_1^z\)。公钥为 \((g_1, g_2, c, d, h, \mathcal{H})\)，其中 \(\mathcal{H}\) 是一个 TCR 哈希函数族的密钥。私钥为 \((x_1, x_2, y_1, y_2, z)\)。

加密消息 \(m\) 时，选取随机数 \(r\)，计算：

\[u_1 = g_1^r, \quad u_2 = g_2^r, \quad e = h^r \cdot m, \quad \alpha = \mathcal{H}(u_1, u_2, e), \quad v = c^r \cdot d^{r\alpha}\]

密文为 \((u_1, u_2, e, v)\)。解密时，首先计算 \(\alpha = \mathcal{H}(u_1, u_2, e)\)，然后验证 \(u_1^{x_1 + y_1 \alpha} \cdot u_2^{x_2 + y_2 \alpha} = v\) 是否成立。如果验证失败，则拒绝解密。验证通过后，计算 \(m = e / u_1^z\)。

该方案的安全性证明核心思路如下。在 IND-CCA2 安全游戏中，归约算法需要模拟解密预言机。关键观察是：合法密文必然满足 \(u_1 = g_1^r\)，\(u_2 = g_2^r\)（即 \(u_1\) 和 \(u_2\) 使用了同一个随机数 \(r\)），而攻击者构造的恶意密文几乎不可能在不知道离散对数的情况下满足这一条件。验证值 \(v\) 的作用在于：它本质上是一个通用哈希函数在点 \((u_1, u_2)\) 上的值，攻击者如果使用不同的 \(r_1, r_2\)（即 \(u_1 = g_1^{r_1}, u_2 = g_2^{r_2}\)，\(r_1 \neq r_2\)），那么验证值 \(v\) 几乎必然不一致。通过这种方式，归约算法可以拒绝所有恶意密文的解密请求，而不需要知道私钥的全部信息。

以下是一个简化的 Python 演示，展示 Cramer-Shoup 密钥生成与加密的基本流程：

import hashlib
import secrets

def mod_exp(base, exp, mod):
    """模幂运算"""
    return pow(base, exp, mod)

def cramer_shoup_demo():
    # 使用一个安全素数 p，其中 q = (p-1)/2 也是素数
    # 此处为演示选取较小的参数，实际应用中 p 至少 2048 位
    q = 0xFFFFFFFFFFFFFFC5  # 一个 64 位素数(仅作演示)
    p = 2 * q + 1

    # 选取群 G 中阶为 q 的两个生成元
    g1 = mod_exp(2, 2, p)   # 确保在阶为 q 的子群中
    g2 = mod_exp(3, 2, p)

    # 密钥生成：选取五个随机指数
    x1 = secrets.randbelow(q)
    x2 = secrets.randbelow(q)
    y1 = secrets.randbelow(q)
    y2 = secrets.randbelow(q)
    z  = secrets.randbelow(q)

    c = (mod_exp(g1, x1, p) * mod_exp(g2, x2, p)) % p
    d = (mod_exp(g1, y1, p) * mod_exp(g2, y2, p)) % p
    h = mod_exp(g1, z, p)

    pk = (p, q, g1, g2, c, d, h)
    sk = (x1, x2, y1, y2, z)
    print("公钥(部分)：g1={}, g2={}, c={}, ...".format(g1, g2, c))
    print("私钥已生成(不显示)")

    # 加密
    m = 42  # 待加密的消息(须为群元素)
    r = secrets.randbelow(q)

    u1 = mod_exp(g1, r, p)
    u2 = mod_exp(g2, r, p)
    e  = (mod_exp(h, r, p) * m) % p

    # 计算哈希 alpha = H(u1, u2, e)
    hash_input = "{}||{}||{}".format(u1, u2, e).encode()
    alpha = int(hashlib.sha256(hash_input).hexdigest(), 16) % q

    v = (mod_exp(c, r, p) * mod_exp(d, r * alpha % q, p)) % p

    ciphertext = (u1, u2, e, v)
    print("密文(u1, u2, e, v)已生成")

    # 解密
    alpha_dec = int(hashlib.sha256(
        "{}||{}||{}".format(u1, u2, e).encode()
    ).hexdigest(), 16) % q

    # 验证
    v_check = (mod_exp(u1, (x1 + y1 * alpha_dec) % q, p)
               * mod_exp(u2, (x2 + y2 * alpha_dec) % q, p)) % p

    if v_check != v:
        print("验证失败——密文被篡改！")
        return None

    m_dec = (e * pow(mod_exp(u1, z, p), p - 2, p)) % p
    print("解密成功，明文 m = {}".format(m_dec))
    assert m_dec == m, "解密结果不一致！"
    return m_dec

if __name__ == "__main__":
    cramer_shoup_demo()

Cramer-Shoup 方案的密文比 ElGamal 增加了两个群元素(额外的 \(u_2\) 和验证值 \(v\))，加密和解密各需要约六次模幂运算，效率与 ElGamal 相当。尽管在实际部署中 RSA-OAEP 仍然更为广泛，Cramer-Shoup 方案的理论价值无可替代——它第一次证明了在标准模型下构造实用的 IND-CCA2 安全加密是可能的。

Cramer 和 Shoup 后续将这一构造推广为哈希证明系统(Hash Proof System, HPS)框架，也称为光滑投射哈希(Smooth Projective Hashing)。HPS 框架将 CCA2 安全加密的构造模块化：只要底层的群满足某种”子集成员问题”(Subset Membership Problem)的困难性假设，并且存在相应的光滑投射哈希函数族，就可以系统地构造 IND-CCA2 安全的加密方案。这一框架不仅统一了之前的 Cramer-Shoup 方案，还催生了基于二次剩余假设、基于 Paillier 假设、基于格假设等多种新的 CCA2 安全构造。

六、签名的可证明安全

签名方案的安全性定义与加密有所不同。标准的安全性目标是存在性不可伪造(Existential Unforgeability under Chosen Message Attack, EUF-CMA)：攻击者在获得多项式数量的消息-签名对之后，仍然无法对任何新消息产生有效签名。

EUF-CMA 安全性的层级与精确定义

签名方案的安全性定义也存在一个层级体系，理解这一层级对于选择合适的安全目标至关重要：

EUF-CMA 的安全游戏精确定义如下：

EUF-CMA 安全游戏 Sig-Forge_A,Π

1. 挑战者运行 (pk, sk) ← Gen(1^λ)，将 pk 发送给攻击者 A
2. A 可自适应地发起签名查询：
   - A 选择消息 m_i，挑战者返回 σ_i ← Sign(sk, m_i)
   - 查询可进行至多 q_s 次
3. A 输出伪造尝试 (m*, σ*)
4. A 赢得游戏当且仅当：
   - Verify(pk, m*, σ*) = 1（签名有效）
   - m* ∉ {m_1, m_2, ..., m_{q_s}}（消息未曾被查询过）

方案 Π 是 EUF-CMA 安全的，当且仅当对所有 PPT 攻击者 A：
  Adv^{euf-cma}_Π(A) = Pr[Sig-Forge_A,Π = 1] ≤ negl(λ)

SUF-CMA（强不可伪造性）的区别在于第 4 步的胜利条件放宽为：(m, σ) ∉ {(m_1, σ_1), …, (m_{q_s}, σ_{q_s})}——即攻击者即使对已签名过的消息 m_i 产生了一个不同于 σ_i 的新签名，也算伪造成功。对于确定性签名方案（如 Ed25519），EUF-CMA 和 SUF-CMA 等价，因为同一消息只有唯一的合法签名。但对于概率性签名方案，SUF-CMA 严格强于 EUF-CMA。

在实际协议设计中，SUF-CMA 通常是更安全的选择。例如，在 Encrypt-then-Sign 组合中，如果签名方案仅满足 EUF-CMA 而非 SUF-CMA，攻击者可能通过对已有密文-签名对产生新的有效签名来实施签名替换攻击（signature malleability attack）——这正是早期比特币交易延展性漏洞的根源。

全域哈希 RSA 签名(Full-Domain Hash, FDH)是 ROM 下签名可证明安全的经典例子。FDH-RSA 的签名过程极为简洁：对消息 \(m\) 计算签名 \(\sigma = H(m)^d \mod N\)，其中 \(H\) 是一个将消息映射到 \(\mathbb{Z}_N^*\) 的哈希函数，\(d\) 是 RSA 私钥。验证时检查 \(\sigma^e \mod N = H(m)\) 是否成立即可。Bellare 和 Rogaway 在 1993 年证明了 FDH-RSA 在随机预言机模型下的 EUF-CMA 安全性，归约到 RSA 假设。然而，归约的安全性损失为 \(q_H\)——哈希查询的次数，这意味着归约是非紧致的。Coron 在 2000 年改进了归约，将损失降低为 \(q_S\)——签名查询的次数，这是一个显著的改进，因为通常 \(q_S \ll q_H\)。

在标准模型下，构造可证明安全的签名方案更具挑战性。Waters 签名是 2005 年提出的第一个在标准模型下基于计算性 Diffie-Hellman(Computational Diffie-Hellman, CDH)假设可证明安全的签名方案，使用了双线性配对(Bilinear Pairing)。Waters 的核心技巧在于构造了一种”可编程哈希函数”(Programmable Hash Function)：公钥中包含一系列群元素 \(u_0, u_1, \ldots, u_n\)，消息 \(m = (m_1, \ldots, m_n)\) 的”哈希值”定义为 \(u_0 \cdot \prod_{i: m_i = 1} u_i\)。在安全性证明中，归约算法可以巧妙地设置这些 \(u_i\)，使得对于签名查询中的消息，它能计算签名(因为对应的离散对数具有特殊结构)；而对于攻击者伪造的消息，它不能计算签名，但可以利用伪造签名来求解 CDH 问题。

Boneh-Boyen 短签名是另一个重要的标准模型构造。该方案在强 Diffie-Hellman(Strong Diffie-Hellman, SDH)假设下是安全的，签名仅由一个群元素构成，因此得名”短签名”。其签名过程为：\(\sigma = g^{1/(x+m+yr)}\)，其中 \(x, y\) 是私钥，\(m\) 是消息，\(r\) 是随机数。Boneh-Boyen 短签名在区块链和零知识证明系统中有广泛应用。

七、紧致归约的重要性

在可证明安全的理论框架中，归约的紧致性(Tightness)是一个常被忽视但对实践影响深远的问题。一个归约是紧致的，意味着如果攻击者以优势 \(\epsilon\) 攻破方案，归约构造的算法可以以接近 \(\epsilon\) 的优势解决底层困难问题。一个归约是非紧致的，意味着归约过程中存在显著的安全性损失。

为什么紧致性如此重要？考虑一个具体的场景：我们希望方案达到 128 位安全性，即任何攻击者的优势不超过 \(2^{-128}\)。如果归约是紧致的，那么底层困难问题也需要达到 128 位安全性——对于 RSA，这意味着大约 3072 位的模数。但如果归约有 \(2^{30}\) 的安全性损失，那么底层问题实际上需要达到 158 位安全性，这可能要求更大的模数。在某些情况下，安全性损失可能与用户数量或会话数量相关，使得问题更加严峻。

多用户多挑战安全性(Multi-User Multi-Challenge Security)将紧致性问题推向了极致。在实际系统中，可能有数百万个用户同时使用同一个密码方案，每个用户可能进行数千次加密操作。Bader、Jager、Li 和 Schage 系统地研究了这一场景，发现许多在单用户设置下看起来安全的方案，在多用户设置下安全性会急剧下降——安全性损失可能与用户数量 \(n_u\) 和挑战次数 \(n_c\) 的乘积成正比。

Gjosteen 和 Jager 在 2018 年提出了具有紧致 CCA2 安全性归约的方案，其安全性损失与用户数量和挑战次数无关。他们的构造利用了基于格的技术和密钥同态性质。这类研究表明，紧致归约不仅是理论上的追求，更是实际安全参数选取的关键依据。

对于实践者而言，一个重要的教训是：仅仅知道一个方案”拥有可证明安全证明”是不够的——必须仔细审查归约的紧致性，才能正确选取安全参数。非紧致的归约可能导致两种风险：要么低估安全参数导致方案实际上不安全，要么高估安全参数导致不必要的效率损失。

八、Schnorr 签名的安全性争议

Schnorr 签名是实践中最重要的离散对数签名方案之一，广泛应用于 TLS、SSH、加密货币等领域(Ed25519 本质上是 Schnorr 签名的一个变体)。然而，Schnorr 签名的可证明安全性却是密码学界长期争论的话题。

Pointcheval 和 Stern 在 1996 年利用分叉引理(Forking Lemma)证明了 Schnorr 签名在随机预言机模型下的安全性，归约到离散对数问题。由于这一证明是签名可证明安全的经典范例，值得展开其归约过程。

Schnorr 签名方案：群 \(G\) 中，私钥为 \(x\)，公钥为 \(y = g^x\)。签名消息 \(m\) 时，选取随机数 \(k\)，计算承诺 \(R = g^k\)，挑战 \(e = H(R \| m)\)，响应 \(s = k - xe \mod q\)。签名为 \((e, s)\)。验证时检查 \(e \stackrel{?}{=} H(g^s y^e \| m)\)。

归约构造：假设攻击者 \(\mathcal{A}\) 能以优势 \(\epsilon\) 伪造签名。归约算法 \(\mathcal{B}\) 接收离散对数挑战 \((g, y = g^x)\)，将 \(y\) 作为公钥交给 \(\mathcal{A}\)，并模拟随机预言机 \(H\)。对于签名查询，\(\mathcal{B}\) 利用对 \(H\) 的控制权进行”编程”：先选取随机的 \(e_i, s_i\)，设置 \(R_i = g^{s_i} y^{e_i}\)，然后将 \(H(R_i \| m_i)\) 的值定义为 \(e_i\)。这样 \((e_i, s_i)\) 就是合法签名，尽管 \(\mathcal{B}\) 并不知道私钥 \(x\)。

分叉（重绕）步骤：

1. \(\mathcal{B}\) 运行 \(\mathcal{A}\)，使用随机带 \(\omega\) 和随机预言机回答序列 \(h_1, h_2, \ldots, h_{q_H}\)。设 \(\mathcal{A}\) 输出伪造签名 \((m^*, e^*, s^*)\)，其中 \(e^*\) 来自第 \(j\) 次 \(H\) 查询的回答。
2. \(\mathcal{B}\) 将 \(\mathcal{A}\) “倒回”到第 \(j\) 次 \(H\) 查询前，保持相同的随机带 \(\omega\) 和前 \(j-1\) 个回答不变，但对第 \(j\) 次及之后的查询使用全新的随机值 \(h'_j, h'_{j+1}, \ldots\)。
3. 再次运行 \(\mathcal{A}\)。由于前 \(j-1\) 步完全相同，\(\mathcal{A}\) 在第 \(j\) 次查询时提交相同的 \((R^* \| m^*)\)，但获得不同的挑战值 \(e^{**} = h'_j \neq e^* = h_j\)。若 \(\mathcal{A}\) 再次伪造成功，得到 \((m^*, e^{**}, s^{**})\)。
4. 两次伪造共享相同的承诺 \(R^* = g^k\)（因为 \(k\) 由前 \(j-1\) 步确定），因此 \(s^* = k - xe^*\) 且 \(s^{**} = k - xe^{**}\)。两式相减得 \(x = (s^{**} - s^*) / (e^* - e^{**}) \mod q\)。

安全性损失分析：归约的成功概率受两个因素制约。首先，\(\mathcal{B}\) 必须猜测伪造依赖于第 \(j\) 次查询，有 \(q_H\) 种可能，引入 \(1/q_H\) 的损失。其次，第二次运行时 \(\mathcal{A}\) 不一定再次成功，一般分叉引理给出的成功概率下界约为 \(\epsilon(\epsilon/q_H - 1/|G|)\)。综合来看，安全性损失约为 \(q_H\)。对于典型参数 \(q_H \approx 2^{60}\)，256 位椭圆曲线群在严格可证明安全意义下仅提供约 \(256/2 - 60 = 68\) 位安全性——这与实践中的 128 位安全性预期存在显著差距。实践者通常的解读是：这一差距来自归约技术的局限而非方案本身的弱点，因为数十年来无人给出优于 Pollard rho（\(O(\sqrt{q})\) 复杂度）的攻击。

Seurin 在 2012 年证明了 Schnorr 签名在随机预言机模型下不可能有紧致的归约到离散对数问题——至少在使用标准的”代数”归约技术时是如此。这一不可能性结果给密码学界带来了困扰：一方面，Schnorr 签名在实践中已经被广泛使用多年，没有任何已知攻击；另一方面，理论上我们无法给出紧致的安全性保证。

为了调和理论与实践之间的差距，Fuchsbauer、Kiltz 和 Loss 在 2018 年引入了代数群模型(Algebraic Group Model, AGM)。AGM 假设攻击者是”代数”的——它输出的每一个群元素都必须伴随一个关于已知群元素的线性表示。在 AGM + ROM 的联合模型下，他们成功证明了 Schnorr 签名具有紧致的安全性归约。AGM 的合理性在于，所有已知的离散对数问题的求解算法(如 Pollard rho、Pohlig-Hellman、数域筛法)确实都是代数的。然而，AGM 作为一个非标准模型假设，其可靠性仍有争议——它本质上排除了一类攻击者(非代数攻击者)，而我们无法保证这类攻击者在实际中不存在。

Fiat-Shamir 变换(从 Sigma 协议到签名方案)的安全性同样与随机预言机模型紧密关联。在标准模型下，Fiat-Shamir 变换甚至可能是不安全的——Goldwasser 和 Kalai 在 2003 年给出了反例。不过，这些反例都依赖于精心构造的”病理性”协议，对于 Schnorr 签名等自然构造的方案，Fiat-Shamir 变换的安全性在实践中似乎是成立的。这一差距——理论上的不安全可能性与实践中的安全表现——是可证明安全研究中最引人入胜的开放问题之一。

九、可证明安全的局限与前沿

可证明安全范式虽然是密码学的基石，但它本身也有深刻的局限性。理解这些局限，既有助于正确解读安全性证明，也能指引未来的研究方向。

不可能性结果与黑盒分离(Black-Box Separation)是理论密码学中的重要主题。Impagliazzo 和 Rudich 在 1989 年的经典工作表明，仅使用黑盒归约，不可能从单向函数(One-Way Function, OWF)构造密钥协商协议(Key Agreement Protocol)。换言之，公钥密码学的存在性不能仅从对称密码学原语的存在性推导出来——它需要更强的计算困难性假设。类似地，Gertner、Malkin 和 Myers 证明了不可能通过黑盒归约从陷门置换构造 CCA2 安全的加密方案。这些不可能性结果划定了黑盒归约技术的能力边界。

安全性证明中的隐含假设也值得关注。许多可证明安全的方案假设底层群是”通用群”(Generic Group)或者攻击者的行为满足某些结构性约束。此外，安全性证明通常只考虑单一的安全目标——例如一个方案可能被证明是 IND-CCA2 安全的，但这并不意味着它在密钥泄露、相关密钥攻击、侧信道攻击等场景下也是安全的。实际系统需要对安全性证明的适用范围保持清醒的认识。

从不可区分混淆(Indistinguishability Obfuscation, iO)到新范式是可证明安全的前沿方向。Sahai 和 Waters 在 2014 年基于 iO 构造了满足各种强安全性定义的密码方案，包括函数加密(Functional Encryption)和可否认加密(Deniable Encryption)。iO 的强大之处在于它几乎是一种”万能工具”——Garg、Gentry、Halevi 和 Rabin 证明了 iO 加上单向函数就足以构造几乎所有已知的密码学原语。然而，iO 的构造本身依赖于复杂的多线性映射或多线性抖动(Multilinear Jigsaw Puzzles)假设，其安全性基础尚不牢固。Jain、Lin 和 Sahai 在 2021 年取得了重要突破，基于四个”标准”假设(包括学习伴误差 LWE、DDH、以及两个关于格和配对的假设)构造了 iO。这一成果被视为密码学的里程碑——如果这些假设确实成立，那么 iO 就建立在了可接受的理论基础之上。

此外，量子计算对可证明安全范式提出了新的挑战。许多经典的归约证明依赖于”重绕”攻击者的技术，而量子攻击者的状态在测量后会坍缩，使得重绕变得不可行。Unruh 在 2012 年发展了量子重绕引理(Quantum Rewinding Lemma)，为在量子攻击者面前进行安全性归约提供了新工具。然而，量子安全性证明中仍存在许多开放问题，例如 QROM 下的紧致归约、量子 CCA2 安全性的定义等。

总结而言，可证明安全是现代密码学不可或缺的方法论。它将密码方案的安全性建立在精确的数学定义和严格的归约证明之上，使得我们能够量化地评估方案的安全强度。然而，安全性证明不是终点——它需要与密码分析、实现安全、协议设计等多个维度相结合，才能真正保障系统的整体安全。从 RSA-OAEP 的 ROM 证明到 Cramer-Shoup 的标准模型构造，从 Fujisaki-Okamoto 变换在后量子密码中的应用到 iO 带来的新范式，可证明安全的理论不断发展，继续引领着密码学的前进方向。

十、标准模型与随机预言机模型方案对照

在选择公钥密码方案时，安全性证明所依赖的模型——随机预言机模型（ROM）还是标准模型（Standard Model）——是一个核心考量维度。下表梳理了主要方案在两种模型下的安全性状况、效率代价与实际部署建议。

笔者认为，ROM 与标准模型之争远不止是学术圈内的审美偏好——它关乎安全性证明在现实世界中的可靠程度。ROM 的核心假设是：我们可以将 SHA-256 这样的哈希函数视为一个完全随机的函数。但哈希函数毕竟是确定性算法，具有内部结构。如果某一天研究者发现 SHA-256 的某种非随机特性恰好可以被攻击者利用，那么所有仅在 ROM 下被证明安全的方案，其安全性证明将同时失效——这不是”理论上可能”的风险，而是曾在实践中发生过的事情（Canetti、Goldreich 和 Halevi 在 1998 年就构造了在 ROM 下安全但在任何具体哈希函数实例化后不安全的人工方案）。标准模型方案（如 Cramer-Shoup）虽然效率略低，但其安全性不依赖于哈希函数的”类随机”行为，因此更不容易因单点突破而全线崩溃。值得注意的是，NIST 后量子标准中大量使用 FO 变换（ROM 证明），这是在效率与证明模型之间的务实取舍——但这也意味着，持续监控哈希函数的密码分析进展，对于后量子密码体系的长期安全至关重要。

密码学百科系列 · 第 52 篇

← 上一篇：对称密码的可证明安全 | 系列目录 | 下一篇：协议安全性分析 →