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

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

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

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

要证明一个方案安全，首先必须严格定义”安全”意味着什么。公钥加密的安全性定义经历了从直觉到形式化的漫长过程，最终形成了以不可区分性(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 证明仍然具有巨大的实用价值——几十年的实践经验表明，对于”自然”构造的方案(而非人为构造的反例)，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}\)，其中解密失败时不返回错误符号，而是返回一个伪随机值。这种处理方式避免了解密失败信息可能导致的侧信道攻击。

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

五、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)：攻击者在获得多项式数量的消息-签名对之后，仍然无法对任何新消息产生有效签名。

全域哈希 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 签名在随机预言机模型下的安全性，归约到离散对数问题。分叉引理的核心思想是：如果攻击者可以伪造签名，那么通过”重绕”(Rewinding)攻击者并在同一随机预言机查询点给出不同的回答，可以获得两个不同的伪造签名，从而提取出离散对数。然而，这种归约是非紧致的——安全性损失约为 \(q_H\)，即随机预言机的查询次数。对于典型参数，\(q_H\) 可能达到 \(2^{60}\) 或更大，这意味着 256 位的椭圆曲线群可能无法提供 128 位安全性(在严格的可证明安全意义下)。

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 篇

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