【密码学百科】可证明安全：安全定义、博弈与模拟范式

密码学方案的安全性绝非一个凭直觉就能回答的问题。历史上大量看似精巧的加密方案在部署数年后才被发现存在致命漏洞，而这些漏洞的根源往往在于设计者对”安全”二字缺乏严格的数学定义。可证明安全（provable security）正是为解决这一困境而生的方法论：它要求我们首先给出精确的安全定义，然后在明确的计算假设下，以数学定理的形式证明一个具体的密码方案满足该定义。这套方法论奠定了现代密码学的理论根基，使得我们能够在信任某些基础困难问题（如大整数分解、离散对数等）的前提下，对方案的安全性做出可量化的承诺。

本文是密码学百科系列的第 50 篇。在前一篇关于密码学与隐私的讨论基础上，本文将系统讲解可证明安全的核心框架：从形式化安全定义的动机出发，逐一介绍加密方案的语义安全与不可区分性定义、签名方案的存在不可伪造性定义，进而深入博弈序列证明技术和模拟范式两大证明方法论，最后讨论随机预言机模型与标准模型下的证明策略，以及从理论到实践的具体安全参数选取问题。

一、为什么需要形式化安全定义

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

graph TD
    A[安全定义] --> B[攻击游戏]
    B --> C[归约]
    C --> D[困难假设]
    D --> E[具体安全]

在可证明安全的框架建立之前，密码学方案的安全性评估主要依赖两种方式：一是设计者的个人经验与直觉，二是公开挑战——如果一个方案在公开若干年后没有人能攻破它，就被认为是安全的。这种”经验安全”（ad-hoc security）的评估方式存在根本性的缺陷。首先，它无法区分”没有人能攻破”和”没有人尝试去攻破”——一个不够引人注目的方案可能只是没有被充分分析过。其次，即使许多人尝试攻击但都失败了，也不能排除一种全新的攻击思路的存在。更重要的是，缺乏形式化的安全定义意味着不同人对”攻破”的理解可能完全不同：有人认为恢复完整的密钥才算攻破，有人认为能够区分密文对应的两条不同消息就足够了。

历史上不乏因安全定义模糊而导致灾难性后果的案例。经典的 Wired Equivalent Privacy（WEP）协议是无线网络安全的早期标准，其设计者声称它提供了”等价于有线网络”的安全性，但从未对这一声称给出精确的数学表述。结果，WEP 协议被发现存在多种严重的密钥恢复攻击——RC4 流密码的初始化向量（initialization vector, IV）重用、CRC-32 校验和的线性性质、以及弱密钥问题等多个漏洞相互叠加，使得攻击者仅需截获数万个数据包就能完整恢复密钥。如果 WEP 的设计者在开发之初就采用了形式化的安全定义，许多这类结构性缺陷本可以在设计阶段被发现。

可证明安全的思想萌芽于 1976 年 Diffie 和 Hellman 的开创性论文，但真正的理论框架是由 Goldwasser 和 Micali 在 1982 年建立的。他们在那篇里程碑式的论文《Probabilistic Encryption》中首次提出了语义安全（semantic security）的概念，并证明了它等价于一个更易于操作的”不可区分性”定义。这一工作的重大意义在于：它第一次将”加密方案安全”这一模糊的直觉转化为一个精确的数学命题，从而使得严格的安全性证明成为可能。此后，Goldreich、Micali、Rackoff、Bellare、Rogaway 等人在这一框架上不断扩展和深化，逐步建立了涵盖加密、签名、密钥交换、安全多方计算等各类密码原语的完整安全定义体系。

可证明安全的基本范式可以概括为三个步骤。第一步是定义安全目标：精确描述攻击者的能力（如能否获取选择明文的密文、能否发起选择密文查询等）以及攻击者被认为”成功”的条件（如能否区分两段密文、能否伪造合法签名等）。第二步是陈述计算假设：选择一个被广泛研究的困难问题作为安全性的基础，如判定性 Diffie-Hellman（decisional Diffie-Hellman, DDH）假设、学习带误差（learning with errors, LWE）假设等。第三步是构造归约（reduction）：证明如果存在一个能够攻破方案安全性的高效攻击者，则可以利用该攻击者构造一个求解底层困难问题的高效算法，从而导出矛盾。归约的紧致程度（tightness）——即攻击者优势与归约算法求解困难问题的成功概率之间的损失——直接影响着方案的具体安全参数选取。

为了让读者在进入具体定义之前建立全局视野，下面的证明地图概括了从安全目标到安全定理的完整推导链条：

可证明安全的完整证明地图

  安全目标                 形式化定义                计算假设
 (我要保护什么？)      (用博弈精确描述)         (我信任什么难题？)
      │                      │                      │
      v                      v                      v
 ┌──────────┐         ┌─────────────┐        ┌─────────────┐
 │ 机密性   │         │ IND-CPA 博弈 │        │   DDH 假设   │
 │ 不可伪造 │  ──>    │ IND-CCA 博弈 │        │   LWE 假设   │
 │ 不可关联 │         │ EUF-CMA 博弈 │        │   RSA 假设   │
 └──────────┘         └──────┬──────┘        └──────┬──────┘
                             │                      │
                             v                      v
                    ┌────────────────────────────────────┐
                    │          归约（Reduction）           │
                    │                                    │
                    │  假设存在攻击者 A 能攻破方案        │
                    │          ↓                         │
                    │  构造求解器 B 利用 A 求解难题       │
                    │          ↓                         │
                    │  B 的成功概率 ≥ f(A 的优势)        │
                    │          ↓                         │
                    │  矛盾：难题不可解 → A 不存在       │
                    └────────────────┬───────────────────┘
                                    │
                                    v
                         ┌─────────────────┐
                         │   安全定理       │
                         │                 │
                         │ "若 DDH 假设成立 │
                         │  则方案是        │
                         │  IND-CPA 安全的  │
                         │  优势损失 ≤ ε"   │
                         └─────────────────┘

个人观察： 「可证明安全」是密码学中最容易被误读的术语——没有之一。这三个字给人一种「安全性已被数学证明」的错觉，但它实际表达的意思远比大多数人理解的要弱：它说的是「如果这个假设成立，并且这个安全模型忠实地反映了现实，那么方案是安全的」。这里有两层条件假设，每一层都可能出问题。假设层面：DDH、LWE 等困难假设至今没有被证明——它们只是「目前没人能解」。如果某天有人找到了高效的 DDH 求解算法，所有基于 DDH 的「可证明安全」方案将一夜之间变得不安全。模型层面的问题更为隐蔽：IND-CPA 博弈假设攻击者只能获取选择明文的密文，但现实中的攻击者可能通过侧信道（时间、功耗、电磁辐射）获取远超模型假设的信息。Padding Oracle Attack 就是一个经典案例——AES-CBC 方案在 IND-CPA 模型下是安全的，但一个不恰当的错误消息就能将其击溃。因此，读者在看到「provably secure」时，正确的心智模型不是「绝对安全」，而是「安全性已被清晰地归约到明确的假设上，我们可以精确地知道自己在信任什么」。这本身已经是巨大的进步——它把安全性从模糊的直觉变成了可审计的数学声明。

二、语义安全与 IND-CPA

语义安全是加密方案最基本的安全要求。直觉上，一个加密方案是语义安全的，如果攻击者在看到密文之后，关于明文所能计算出的任何信息，都不比他在完全不看到密文的情况下能计算出的信息更多。换言之，密文不泄露明文的任何部分信息——无论是明文的第一个比特、明文的长度（在允许长度泄露的标准定义下除外）、还是明文是否满足某个特定的谓词。

然而，语义安全的原始定义涉及对”关于明文的所有可计算函数”的量化，这使得直接用它来证明具体方案的安全性变得极为困难。Goldwasser 和 Micali 的一个关键贡献是证明了语义安全等价于一个结构上简洁得多的定义——选择明文攻击下的不可区分性（indistinguishability under chosen-plaintext attack, IND-CPA）。IND-CPA 通过一个挑战者（challenger）和攻击者（adversary）之间的交互博弈来定义：

IND-CPA 博弈的流程如下。挑战者生成公钥和私钥对 (pk, sk)，将 pk 发送给攻击者。攻击者可以在自己持有 pk 的情况下对任意明文进行加密（因为加密是公钥操作），经过若干次这样的操作后，攻击者选择两条等长的消息 m_0 和 m_1，提交给挑战者。挑战者随机选择一个比特 b ∈ {0, 1}，计算挑战密文 c* = Enc(pk, m_b)，将 c* 发送给攻击者。攻击者在获得 c* 后，可以继续进行加密操作，最终输出对 b 的猜测 b’。如果 b’ = b，攻击者获胜。

攻击者的优势（advantage）定义为：

Adv_IND-CPA(A) = |Pr[b’ = b] - 1/2|

一个加密方案在 IND-CPA 意义下是安全的，如果对于所有多项式时间的攻击者 A，其优势 Adv_IND-CPA(A) 都是可忽略的（negligible），即对于任何多项式 p(·)，当安全参数 λ 足够大时，Adv_IND-CPA(A) < 1/p(λ)。

IND-CPA 安全性的一个直接推论是：加密方案必须是概率性的。如果加密算法是确定性的，攻击者只需分别计算 Enc(pk, m_0) 和 Enc(pk, m_1)，与挑战密文 c* 进行比较即可完美地确定 b，因此确定性加密不可能是 IND-CPA 安全的。这解释了为什么现代公钥加密方案（如 ElGamal 加密、Paillier 加密）都引入了随机性。

以下 Python 代码模拟了一个 IND-CPA 博弈，演示如何通过大量重复实验来度量攻击者的优势：

import os
import secrets
from collections import Counter

def xor_bytes(a: bytes, b: bytes) -> bytes:
    """逐字节异或两段等长的字节串。"""
    return bytes(x ^ y for x, y in zip(a, b))

# --------------- 一个"玩具级"对称加密方案 ---------------
# 使用一次性密钥流进行异或加密，密钥长度等于消息长度。
# 这里仅用于演示博弈框架，不代表实际公钥方案。

class ToyEncryptionScheme:
    """IND-CPA 安全的玩具加密方案：每次加密使用独立随机密钥流。"""

    def __init__(self, key: bytes):
        self.key = key  # 主密钥（此玩具方案中未实际使用）

    def encrypt(self, plaintext: bytes) -> bytes:
        """加密：生成随机一次性密钥流与明文异或，附加密钥流作为密文前缀。"""
        pad = os.urandom(len(plaintext))
        ciphertext = pad + xor_bytes(plaintext, pad)
        return ciphertext

    def decrypt(self, ciphertext: bytes) -> bytes:
        """解密：从密文中提取密钥流并还原明文。"""
        half = len(ciphertext) // 2
        pad = ciphertext[:half]
        masked = ciphertext[half:]
        return xor_bytes(masked, pad)

class WeakEncryptionScheme:
    """IND-CPA 不安全的方案：确定性加密（ECB 风格异或）。"""

    def __init__(self, key: bytes):
        self.key = key

    def encrypt(self, plaintext: bytes) -> bytes:
        """确定性加密：直接用固定密钥异或明文。"""
        extended_key = (self.key * (len(plaintext) // len(self.key) + 1))[:len(plaintext)]
        return xor_bytes(plaintext, extended_key)

    def decrypt(self, ciphertext: bytes) -> bytes:
        return self.encrypt(ciphertext)  # 异或的对合性

# --------------- IND-CPA 博弈模拟器 ---------------

def ind_cpa_game(scheme, adversary_strategy, num_trials: int = 10000) -> float:
    """
    模拟 IND-CPA 博弈并返回攻击者的优势。

    参数：
        scheme             -- 加密方案实例（需提供 encrypt 方法）
        adversary_strategy -- 攻击者策略函数，接收挑战密文和方案实例，
                              返回对 b 的猜测（0 或 1）
        num_trials         -- 重复博弈的次数
    返回：
        攻击者优势 |Pr[b' = b] - 1/2|
    """
    correct = 0
    for _ in range(num_trials):
        # 攻击者选择两条等长消息
        m0 = b"attack at dawn!!"  # 16 字节
        m1 = b"retreat at dusk!"  # 16 字节

        # 挑战者随机选择 b 并加密 m_b
        b = secrets.randbelow(2)
        challenge_ct = scheme.encrypt(m0 if b == 0 else m1)

        # 攻击者根据策略猜测 b
        guess = adversary_strategy(challenge_ct, scheme)
        if guess == b:
            correct += 1

    win_prob = correct / num_trials
    advantage = abs(win_prob - 0.5)
    return advantage

# --------------- 攻击者策略 ---------------

def random_adversary(challenge_ct: bytes, scheme) -> int:
    """随机猜测的攻击者——优势应接近 0。"""
    return secrets.randbelow(2)

def deterministic_distinguisher(challenge_ct: bytes, scheme) -> int:
    """
    针对确定性加密的攻击者：加密 m0 并与挑战密文比较。
    若方案是确定性的，密文一致则 b=0，否则 b=1。
    """
    m0 = b"attack at dawn!!"
    ct0 = scheme.encrypt(m0)
    return 0 if ct0 == challenge_ct else 1

# --------------- 运行实验 ---------------

if __name__ == "__main__":
    key = os.urandom(16)
    num_trials = 20000

    # 实验 1：IND-CPA 安全方案 + 随机攻击者
    secure_scheme = ToyEncryptionScheme(key)
    adv1 = ind_cpa_game(secure_scheme, random_adversary, num_trials)
    print(f"安全方案 + 随机攻击者  ：优势 = {adv1:.4f}  （期望 ≈ 0）")

    # 实验 2：IND-CPA 安全方案 + 确定性区分攻击者
    adv2 = ind_cpa_game(secure_scheme, deterministic_distinguisher, num_trials)
    print(f"安全方案 + 区分攻击者  ：优势 = {adv2:.4f}  （期望 ≈ 0，因为加密是概率性的）")

    # 实验 3：不安全方案 + 确定性区分攻击者
    weak_scheme = WeakEncryptionScheme(key)
    adv3 = ind_cpa_game(weak_scheme, deterministic_distinguisher, num_trials)
    print(f"不安全方案 + 区分攻击者：优势 = {adv3:.4f}  （期望 ≈ 0.5，完美区分）")

    # 实验 4：不安全方案 + 随机攻击者
    adv4 = ind_cpa_game(weak_scheme, random_adversary, num_trials)
    print(f"不安全方案 + 随机攻击者：优势 = {adv4:.4f}  （期望 ≈ 0，攻击者未利用弱点）")

运行上述代码可以清晰地观察到：对于 IND-CPA 安全的概率性加密方案，即使攻击者采用确定性区分策略，优势也趋近于零；而对于确定性加密方案，知道利用其弱点的攻击者能获得接近 0.5 的最大优势。这正是 IND-CPA 安全性所要排除的情形。

三、IND-CCA 与自适应选择密文安全

IND-CPA 虽然排除了仅凭观察密文就能提取信息的攻击，但它没有考虑攻击者能够利用解密能力的场景。在实际系统中，攻击者往往可以通过各种侧信道获得部分解密信息——例如，向服务器提交精心构造的密文并观察服务器的错误响应。这催生了更强的安全定义：选择密文攻击下的不可区分性（indistinguishability under chosen-ciphertext attack, IND-CCA）。

IND-CCA 安全性分为两个层次。IND-CCA1（又称”午餐攻击”安全）允许攻击者在收到挑战密文之前访问解密预言机（decryption oracle），但在收到挑战密文之后不再允许解密查询。IND-CCA2（自适应选择密文安全）则更强：攻击者在收到挑战密文之后仍然可以继续向解密预言机提交查询，唯一的限制是不能直接提交挑战密文本身进行解密。IND-CCA2 是公钥加密方案事实上的标准安全目标。

IND-CCA2 安全定义的动机源于一系列真实攻击。最著名的例子是 Bleichenbacher 在 1998 年提出的针对 RSA PKCS#1 v1.5 填充方案的自适应选择密文攻击。该攻击利用的是一个看似无害的信息泄露：当 SSL 服务器收到一个密文并尝试用 RSA 私钥解密后，如果解密结果不符合 PKCS#1 v1.5 的填充格式，服务器会返回一个特定的错误消息。Bleichenbacher 发现，攻击者可以精心构造大量密文，通过观察服务器对每个密文的”格式正确”或”格式错误”的二元响应，逐步缩小目标明文的取值范围，最终完整地恢复明文。整个攻击通常只需要约一百万次查询——对于网络攻击而言这是完全可行的。

更广义地说，填充预言机攻击（padding oracle attack）是 IND-CCA 安全性关注的核心威胁模型。Vaudenay 在 2002 年展示了针对 CBC 模式加密的类似攻击：如果服务器在解密后检查填充格式并返回不同的错误消息（“填充正确”vs”填充错误”），攻击者可以逐字节地恢复完整的明文。这类攻击在实践中影响深远——2014 年的 POODLE 攻击和 2016 年的 DROWN 攻击都属于填充预言机攻击的变种。

满足 IND-CCA2 安全性的方案需要具备密文完整性（ciphertext integrity）的性质：攻击者无法在不被检测到的情况下修改一个合法密文使其解密为不同的明文。Cramer 和 Shoup 在 1998 年给出了第一个在标准模型下可证明 IND-CCA2 安全的高效公钥加密方案，其核心思路是将哈希证明系统（hash proof system）与目标碰撞抗性哈希函数相结合，为每个密文附加一个一致性检验值。Fujisaki-Okamoto 变换则提供了另一条通用路径：将任何 IND-CPA 安全的公钥加密方案转化为 IND-CCA 安全的方案，其代价是引入随机预言机假设。在后量子密码标准化进程中，Kyber（现已更名为 ML-KEM）等格基方案正是使用了 Fujisaki-Okamoto 变换的变种来实现 IND-CCA2 安全。

四、签名安全性：EUF-CMA

与加密方案保护消息的机密性不同，数字签名方案保护消息的真实性和完整性。签名方案的安全性要求攻击者即使能够获取任意消息的合法签名，也无法伪造出一个新的合法签名。这一要求被形式化为选择消息攻击下的存在不可伪造性（existential unforgeability under chosen message attack, EUF-CMA）。

EUF-CMA 博弈的流程如下。挑战者生成签名密钥对 (vk, sk)，将验证密钥 vk 发送给攻击者。攻击者可以自适应地选择任意消息 m_1, m_2, …, m_q，并获得每条消息的合法签名 σ_1, σ_2, …, σ_q（通过向挑战者查询签名预言机）。最终，攻击者输出一对 (m, σ)。如果 Verify(vk, m, σ) = 1 且 m* 不属于之前查询过的消息集合 {m_1, …, m_q}，则攻击者获胜。

EUF-CMA 的定义中有两个关键点。第一，“存在性”（existential）意味着攻击者只需要伪造任意一条新消息的签名即可——攻击者不需要伪造某条特定消息的签名（后者称为选择性伪造，selective forgery，是更弱的攻击目标）。第二，“选择消息攻击”（chosen message attack）意味着攻击者可以自适应地选择要签名的消息，每次选择可以依赖于之前获得的签名。这是最强的签名查询模型，也是实践中最为合理的模型——在实际系统中，攻击者通常可以通过各种方式诱使合法签名者对攻击者选择的消息进行签名。

EUF-CMA 的一个加强版本是强存在不可伪造性（strong existential unforgeability under chosen message attack, sEUF-CMA）。在 sEUF-CMA 中，攻击者的获胜条件更为宽松：输出的 (m, σ) 对只要不属于之前查询-响应对的集合 {(m_1, σ_1), …, (m_q, σ_q)} 即可——即使 m* 是之前查询过的消息，只要 σ* 不同于之前获得的签名，攻击就被视为成功。sEUF-CMA 比 EUF-CMA 更强，因为它还排除了攻击者对已有消息找到第二个合法签名的可能性。sEUF-CMA 在构造认证加密方案、签名加密方案等高层协议时尤为重要，因为这些构造的安全证明往往依赖于签名的唯一性。

五、博弈序列证明技术

在定义了安全目标之后，下一步是证明具体方案满足该定义。博弈序列（game sequence）或称博弈跳转（game hopping）是当前最主流的安全证明技术，由 Shoup 在 2004 年进行了系统的方法论总结。

博弈序列证明的核心思想是：构造一系列博弈 Game_0, Game_1, …, Game_n，其中 Game_0 是原始的安全博弈（如 IND-CPA 博弈），Game_n 是一个攻击者优势显然为零的理想化博弈。然后逐步论证相邻博弈之间的差异足够小——即对于任何攻击者 A，|Pr[A 赢得 Game_i] - Pr[A 赢得 Game_{i+1}]| 是可忽略的。通过三角不等式，攻击者在原始博弈中的优势不超过所有相邻差异之和加上攻击者在最终博弈中的优势。

博弈之间的跳转通常分为三类。第一类是基于不可区分性的跳转（indistinguishability-based transition）：将博弈中的某个组件替换为一个计算上不可区分的组件。例如，用伪随机函数（pseudorandom function, PRF）的输出替换真随机值——如果攻击者能够区分这两个博弈，则可以构造一个区分 PRF 和真随机函数的高效算法，与 PRF 的安全假设矛盾。第二类是基于失败事件的跳转（failure event transition）：两个博弈在某个”坏事件”不发生时完全相同，因此它们之间的差异最多等于该坏事件的发生概率。例如，在证明中可能需要论证某个哈希碰撞不会发生——两个博弈除了碰撞发生时的行为不同之外完全一致，因此优势差异由碰撞概率上界所限。第三类是纯粹的概念重构（bridging step）：两个博弈在概率分布上完全相同，只是对某些变量的计算方式或延迟赋值时机做了调整。这类跳转不引入任何优势损失，其目的纯粹是使证明的下一步更容易进行。

混合论证（hybrid argument）是博弈序列证明中最经典的具体技术之一。它特别适用于以下场景：方案中包含 n 个独立的随机组件，需要论证将所有这些组件从”真实”替换为”理想”后攻击者的优势仍然可忽略。混合论证构造 n+1 个混合博弈 H_0, H_1, …, H_n，其中 H_0 中所有组件都是”真实”的，H_n 中所有组件都是”理想”的，而 H_i 中前 i 个组件是”理想”的、其余是”真实”的。如果攻击者在 H_0 和 H_n 之间的优势为 ε，则存在某个相邻对 (H_j, H_{j+1}) 使得攻击者的优势至少为 ε/n。对于这单个组件的替换，可以归约到底层困难假设。混合论证的代价是引入一个 n 倍的安全损失因子——这在 n 较大时可能导致显著的具体安全性退化，因此紧致归约（tight reduction）的研究一直是可证明安全领域的核心课题之一。

混合证明模板

为帮助读者在实际证明工作中快速应用混合论证，下面给出一个通用的混合证明模板。假设方案中包含 n 个 PRF 实例 F_{k_1}, F_{k_2}, …, F_{k_n}，需证明将它们全部替换为真随机函数后攻击者的优势可忽略。

混合证明模板（n 个 PRF 实例 → 真随机函数）

定义混合博弈序列：
  Game_0（真实博弈）：所有 n 个实例均使用 PRF F_{k_i}
  Game_i（混合博弈）：前 i 个实例使用真随机函数 f_j，
                       后 n-i 个实例使用 PRF F_{k_j}
  Game_n（理想博弈）：所有 n 个实例均使用真随机函数

安全性归约步骤：
  对于每对相邻博弈 (Game_{i-1}, Game_i)：
    1. 构造归约算法 B_i：
       · B_i 接收一个预言机 O（可能是 F_k 或真随机函数 f）
       · B_i 自行采样 f_1, ..., f_{i-1}（前 i-1 个真随机函数）
       · B_i 自行采样 k_{i+1}, ..., k_n（后 n-i 个 PRF 密钥）
       · B_i 将第 i 个实例的查询转发给预言机 O
       · B_i 运行攻击者 A，输出 A 的判断

    2. 优势关系：
       |Pr[A 赢 Game_{i-1}] - Pr[A 赢 Game_i]|
         = Adv^{prf}_F(B_i)

  三角不等式汇总：
    Adv(A) = |Pr[A 赢 Game_0] - Pr[A 赢 Game_n]|
           ≤ Σ_{i=1}^{n} Adv^{prf}_F(B_i)
           ≤ n · max_i Adv^{prf}_F(B_i)

  安全损失因子 = n（混合博弈的数量）

这一模板的核心价值在于它的机械性——一旦确定了需要替换的组件类型和数量，证明的结构就完全确定了。实际应用中，最关键的步骤是验证归约算法 B_i 确实能够完美模拟除第 i 个组件之外的所有博弈环境。如果模拟过程中 B_i 需要获取某些它不具备的信息（例如私钥），则说明归约存在问题，需要调整博弈序列的设计。

具体实例：ElGamal 加密的 IND-CPA 证明

为将上述模板落到实处，下面以 ElGamal 加密为例，完整展示一个基于 DDH 假设的 IND-CPA 安全性证明。

回顾 ElGamal 加密方案。设 G 为阶为素数 p 的循环群，g 为生成元。密钥生成：随机选择 x ← Z_p，公钥 pk = (G, g, h = g^x)，私钥 sk = x。加密消息 m ∈ G：随机选择 r ← Z_p，输出密文 (c_1, c_2) = (g^r, m · h^r)。解密：计算 m = c_2 / c_1^x。

判定性 Diffie-Hellman（DDH）假设断言：对于随机的 a, b ← Z_p，以下两个分布在计算上不可区分：

DDH 假设
  真实分布：(g, g^a, g^b, g^{ab})
  随机分布：(g, g^a, g^b, g^c)    其中 c ← Z_p 独立随机选取

现在构造博弈序列并推导优势不等式：

ElGamal IND-CPA 证明：博弈序列与优势推导

Game 0（原始 IND-CPA 博弈）：
  挑战者生成 pk = (g, h = g^x)，攻击者提交 (m_0, m_1)
  挑战者选择 b ← {0,1}，随机选择 r ← Z_p
  挑战密文 c* = (g^r, m_b · g^{xr})
  攻击者输出猜测 b'；定义 Pr[A 赢 Game 0] = Pr[b' = b]

Game 1（嵌入 DDH 挑战）：
  挑战者收到 DDH 挑战 (g, g^a, g^b, T)，设 pk = (g, g^a)
  挑战密文 c* = (g^b, m_b · T)
  · 若 T = g^{ab}：与 Game 0 分布相同
  · 若 T = g^c（随机）：m_b · g^c 是均匀随机的，与 b 信息论独立
    因此 Pr[A 赢 | T=g^c] = 1/2

优势推导：
  Adv_{IND-CPA}(A) = |Pr[A 赢 Game 0] - 1/2|
    = |Pr[A 赢 | T=g^{ab}] - Pr[A 赢 | T=g^c]|
    = Adv_{DDH}(B)

  其中 B 是利用 A 构造的 DDH 区分器：
    B 收到 (g, g^a, g^b, T)，设 pk=(g,g^a)，挑战密文=(g^b, m_b·T)
    若 A 猜对则 B 输出"真实"，否则输出"随机"

  结论：Adv_{IND-CPA}(A) = Adv_{DDH}(B)  安全损失因子 = 1（紧致归约）

这个证明之所以紧致，是因为 ElGamal 方案的代数结构恰好允许将一个 DDH 实例完整地嵌入到单个 IND-CPA 挑战中，无需混合论证、无需猜测攻击者的行为。紧致归约意味着：若 DDH 假设在群 G 上提供 128 比特安全性，则 ElGamal 在该群上也直接提供 128 比特的 IND-CPA 安全性，无需额外放大参数。与后文将讨论的 Schnorr 签名的非紧致归约形成鲜明对比。

六、模拟范式

博弈序列证明技术适用于”基于博弈”（game-based）的安全定义，而密码学中另一类重要的安全定义——特别是在安全多方计算和零知识证明领域——则采用”基于模拟”（simulation-based）的范式。模拟范式的核心思想可以用”理想世界/现实世界”（ideal world / real world）的二分法来概括。

在现实世界中，参与方运行一个具体的密码协议 π，攻击者可以控制部分参与方（腐化）、窃听通信、甚至修改消息。在理想世界中，不存在具体的协议——参与方将自己的输入提交给一个可信的理想功能（ideal functionality）F，由 F 直接计算并返回正确的输出。理想世界中存在一个模拟器（simulator）S，它扮演被腐化参与方的角色，但除了通过 F 的接口获取信息外，无法直接访问诚实参与方的输入。

如果对于现实世界中的任何高效攻击者 A，都存在理想世界中的一个高效模拟器 S，使得任何高效的环境（environment）Z 都无法区分它是在与现实世界中的 (π, A) 交互还是在与理想世界中的 (F, S) 交互，则称协议 π 安全地实现了理想功能 F。

零知识证明是模拟范式最经典的应用。一个交互式证明系统 (P, V) 对于语言 L 是零知识的，如果对于任何高效的验证者 V*，都存在一个高效的模拟器 S，使得 S 在不与证明者交互的情况下能够生成与真实交互记录在计算上不可区分的假交互记录。直觉上，如果模拟器能够在完全不知道证人（witness）的情况下”伪造”出看似合法的交互记录，那么验证者从真实交互中也不可能获取到关于证人的任何额外知识——因为他看到的东西都可以自行生成。

模拟范式最为完善的形式化是 Canetti 在 2001 年提出的通用可组合性框架（universally composable framework, UC framework）。UC 框架引入了环境 Z 的概念——Z 可以任意地向参与方提供输入、读取参与方的输出，并且可以与攻击者进行任意通信。UC 安全性要求：对于任何现实世界攻击者 A，都存在理想世界模拟器 S，使得对于所有环境 Z，Z 在现实世界执行中的输出分布与其在理想世界执行中的输出分布在计算上不可区分。

UC 安全性的核心价值在于其可组合性定理（composition theorem）：如果协议 π 在 UC 意义下安全地实现了功能 F，则 π 可以安全地嵌入到任何更大的协议环境中，替换其中对 F 的理想调用，而不损害整个系统的安全性。这一性质对于分析复杂系统至关重要——实践中的密码系统通常由多个子协议并发地、交错地执行，传统的独立安全定义无法保证组合后仍然安全，而 UC 框架则从设计上就确保了这种可组合性。然而，UC 安全性也极为严格：许多在独立模型下被认为安全的方案在 UC 框架下并不安全，需要额外的设置假设（如公共参考串 common reference string、可信初始化等）才能实现 UC 安全性。

UC 框架与博弈范式的边界：何时选择哪种模型

理解 UC 框架与博弈范式各自的适用边界，对于密码方案的设计者和评估者至关重要。下表从多个维度对两种范式进行系统比较：

一个常见的工程决策场景是：当设计一个将被多个应用层协议调用的密钥交换子协议时，是否需要追求 UC 安全？答案取决于调用方式——如果密钥交换与上层协议之间的接口是严格隔离的（密钥材料仅通过明确定义的接口传递），则博弈范式下的密钥交换安全性（如 BR 模型）通常足够。但如果密钥交换的内部状态可能被上层协议观察到（例如通过侧信道或错误处理路径），则 UC 安全性提供的组合保证变得不可替代。TLS 1.3 的形式化验证同时采用了两种范式——Tamarin 在符号模型下验证协议逻辑，CryptoVerif 在博弈范式下给出计算安全性证明——正是这种务实的分层策略的体现。

UC 框架的不可能性结果与设置假设

UC 框架的严格性不仅是工程层面的挑战，更导致了一系列基础性的不可能性定理（impossibility results），这些定理划定了 UC 安全性的理论边界。

最核心的不可能性结果来自 Canetti 和 Fischlin（2001）：在没有任何设置假设（setup assumption）的”朴素模型”（plain model）中，不存在 UC 安全的承诺方案（commitment scheme）。直觉上，UC 安全要求对于任何环境 Z 都存在模拟器 S，但承诺协议的绑定性（binding）要求发送者一旦承诺就无法改变值，而模拟器为了模拟被腐化的发送者又必须能够”打开”承诺为任意值——这两个需求在朴素模型中不可调和。类似地，Canetti 等人证明了在朴素模型中，许多自然的两方计算功能（如不经意传输 OT、零知识证明）也无法 UC 安全地实现。

这些不可能性结果促使研究者引入各类设置假设来绕过障碍。公共参考串（CRS）可实现 UC 承诺、UC OT 和 UC 零知识（Canetti-Fischlin 2001）；可信初始化可实现 UC 密钥交换（Canetti-Krawczyk 2002）；随机预言机可实现几乎所有功能（Canetti 2001）；防篡改硬件（tamper-proof hardware）甚至可以在无 CRS 的条件下实现 UC 安全（Katz 2007）。需要注意的是，设置假设本身需要信任——CRS 要求一个可信第三方诚实地生成参考串，这在去中心化场景中可能是不可接受的。

这意味着在评估一个声称”UC 安全”的协议时，必须追问其依赖的设置假设是否在目标部署环境中可以被信任。区块链场景中难以找到生成 CRS 的可信方，因此许多区块链协议转向使用”透明设置”（transparent setup）或可验证随机函数来弱化对 CRS 的信任需求。

从工程实践来看，模拟范式与博弈范式之间的选择反映了密码学理论中一个深层的哲学分歧。模拟范式捕获的是「理想功能」这一直觉——它告诉你「协议的行为等价于一个可信第三方做了所有事情」，这在概念上非常清晰，但在实操中极难运用：构造模拟器通常是安全证明中最具创造性也最容易出错的环节，而 UC 框架的严格性更是让许多自然的协议无法满足要求。博弈范式则更加务实——它把安全性分解为若干独立的「博弈」（如 IND-CPA、EUF-CMA），每个博弈定义一种具体的攻击能力和成功条件，证明结构更加模块化且更容易机械化检验。但博弈范式的风险在于「遗漏」——如果你的博弈集合没有覆盖到某种攻击模式，你的方案可能在所有博弈中都是安全的，却在现实中被一种「介于两个博弈之间」的攻击击溃。笔者认为，这种张力在短期内不会消解，但长期趋势是两种范式的融合——用模拟范式定义顶层安全目标，用博弈范式分解和证明具体的归约步骤。

七、随机预言机模型的证明

在许多可证明安全的工作中，哈希函数被建模为一个随机预言机（random oracle, RO）——即一个所有参与方（包括攻击者）都可以查询的理想化随机函数，它对每个新的输入返回一个均匀随机的输出，对于重复的输入返回相同的输出。随机预言机模型（random oracle model, ROM）最早由 Bellare 和 Rogaway 在 1993 年系统地提出和推广，它极大地简化了安全证明的复杂性。

在 ROM 下进行安全证明的核心技术是”编程随机预言机”（programming the random oracle）。由于随机预言机的输出是完全随机的，归约算法在模拟随机预言机时可以自由选择某些查询的输出值，使其满足特定的代数关系，从而嵌入困难问题的实例。例如，在 RSA-FDH（Full Domain Hash）签名方案的安全证明中，归约算法在回答攻击者的哈希查询时，将部分查询的输出设置为与 RSA 挑战值相关的值。当攻击者最终伪造签名时，如果伪造恰好发生在被”编程”过的哈希值上，归约算法就可以从伪造签名中提取出 RSA 问题的解。

随机预言机模型的另一个常用技术是重卷（rewinding）。在某些证明中（特别是 Fiat-Shamir 变换的安全证明），归约算法需要让攻击者运行两次，使用相同的随机预言机回答但在关键位置给出不同的挑战值。通过比较攻击者在两次运行中的输出，归约算法可以提取出底层困难问题的解。分叉引理（forking lemma）将这一技术形式化，给出了提取成功概率的下界。

然而，随机预言机模型也受到重要的理论批评。Canetti、Goldreich 和 Halevi 在 1998 年构造了一个人为的方案，它在随机预言机模型下是可证明安全的，但在用任何具体的哈希函数实例化后都是不安全的。这一结果表明，随机预言机模型中的安全证明并不能自动转化为标准模型下的安全证明——随机预言机是一个不可实例化的理想化对象，现实中的哈希函数只是在某些性质上近似于随机预言机。

尽管存在理论局限性，随机预言机模型在实践中仍然极为有用。绝大多数实际部署的密码方案——包括 RSA-OAEP、ECDSA、Schnorr 签名等——的安全证明都依赖于随机预言机模型。在后量子密码标准化中，NIST 选定的所有方案（ML-KEM、ML-DSA、SLH-DSA）也都在 ROM 或量子随机预言机模型（quantum random oracle model, QROM）下获得了安全证明。实践社区的共识是：ROM 证明虽然不是绝对的安全保证，但它排除了所有”结构性”攻击（即不利用哈希函数具体实现细节的攻击），因此仍然是方案设计中极为重要的参考依据。

一个经常被忽视的观点是：ROM 证明与标准模型证明之间的差距不仅是理论上的「纯粹性」差异，而是在实践中具有可量化的安全含义。ROM 证明的安全保证建立在「你的哈希函数表现得像一个完全随机的函数」这一假设之上。一旦哈希函数暴露出意外的代数结构——比如 MD5 被发现存在实用的碰撞攻击、SHA-1 的碰撞抗性被打破——所有基于这些哈希函数在 ROM 下的安全证明就失去了理论基础。相比之下，标准模型证明仅依赖于哈希函数的特定性质（如抗碰撞性、伪随机性），即使哈希函数在某些其他方面表现出非随机行为，只要被证明依赖的那些性质仍然成立，安全保证就仍然有效。这就是为什么从 MD5 到 SHA-1 到 SHA-3 的每一次哈希函数迁移，都会让基于 ROM 的方案设计者紧张，而基于标准模型的方案设计者则相对从容。笔者认为，在选择具体的密码方案时，ROM 证明和标准模型证明之间的差异应当被纳入风险评估——对于需要抵御数十年攻击的长寿命系统（如证书基础设施、数字档案签名），标准模型证明的额外保障值得为之付出性能代价。

八、标准模型的证明

标准模型（standard model）下的安全证明不依赖于随机预言机假设——所有密码组件都被视为具体的算法，安全性直接归约到计算困难假设。标准模型证明被认为提供了更强的理论保证，但通常也意味着更复杂的方案设计和更精巧的证明技术。

标准模型下的公钥加密方案设计中，有两项代表性的技术贡献。第一项是 Peikert 和 Waters 在 2008 年提出的损失陷门函数（lossy trapdoor function, LTF）框架。损失陷门函数是这样一类函数族：它有两种模式——正常模式和损失模式。在正常模式下，函数具有陷门，可以高效求逆；在损失模式下，函数的值域远小于定义域，因此丢失了输入的大量信息。关键的安全假设是这两种模式在计算上不可区分。基于 LTF，可以构造在标准模型下 IND-CCA 安全的加密方案：正常模式用于实际的加密和解密，而在安全证明中，归约算法将方案切换到损失模式，使得密文在信息论意义上隐藏了明文。

第二项是 Waters 在 2009 年提出的对偶系统加密（dual system encryption）技术。对偶系统加密在身份基加密（identity-based encryption, IBE）和属性基加密（attribute-based encryption, ABE）等高级加密原语的标准模型安全证明中发挥了关键作用。其核心思想是为密文和密钥各引入一种”半功能”（semi-functional）模式——半功能密文在外观上与正常密文不可区分，半功能密钥在外观上也与正常密钥不可区分，但半功能密钥无法正确解密半功能密文。安全证明通过一系列博弈跳转，逐步将所有密文和密钥切换到半功能模式，在最终的博弈中，挑战密文在信息论意义上独立于被加密的消息。

标准模型证明的另一个重要方向是从格基假设出发的构造。Regev 在 2005 年基于 LWE 问题构造的加密方案、Gentry-Peikert-Vaikuntanathan（GPV）在 2008 年基于 SIS 问题构造的签名方案等，都在标准模型下获得了严格的安全归约。格基密码方案的一个显著优势是其归约通常具有量子抗性——安全性基于的格问题被认为对量子计算机也是困难的。此外，格基方案的归约往往具有较好的紧致性，这对于实际参数选取意义重大。

在签名方案领域，标准模型下最经典的构造包括 Waters 签名（基于计算性 Diffie-Hellman 假设）和 Boneh-Boyen 短签名（基于 strong Diffie-Hellman 假设）。这些方案的证明技巧各有特色：Waters 签名使用一种巧妙的”人为中止”（artificial abort）技术来修正模拟器的输出分布，而 Boneh-Boyen 签名则利用 q-type 假设（安全性取决于攻击者的查询次数 q）来实现紧凑的签名长度。

九、从理论到实践

可证明安全的理论框架为密码方案的设计和评估提供了严谨的数学工具，但将理论证明转化为实际系统的安全保证需要跨越若干重要的鸿沟。

首先是渐近安全性与具体安全性（concrete security）之间的鸿沟。传统的可证明安全分析采用渐近分析：当安全参数 λ 趋向无穷时，攻击者的优势是可忽略的。然而，实际系统必须选择一个具体的 λ 值（例如 λ = 128 或 λ = 256），并需要确保在该具体参数下方案确实安全。Bellare 和 Rogaway 在 1996 年倡导的”具体安全性”分析方法关注的正是这一问题：它要求精确跟踪归约中的安全损失因子，给出形如”如果存在运行时间为 t、发起 q 次查询、优势为 ε 的攻击者，则存在运行时间为 t’、求解困难问题的成功概率为 ε’ 的算法”的定量语句。归约越紧致（t’/t 和 ε’/ε 的比值越接近 1），方案在实际部署中所需的安全参数越小，效率也越高。

安全损失如何直接决定参数选取

为了让读者直观感受安全损失的工程影响，考虑以下具体计算。假设我们的目标安全级别是 128 比特，即要求任何攻击者的优势不超过 2^{-128}。

场景一：紧致归约。 如果方案的安全性可以紧致地归约到 DDH 假设（即 ε’ ≈ ε），则只需要 DDH 假设本身达到 128 比特安全性。对于 256 比特的椭圆曲线群（如 Curve25519），最优已知攻击是 Pollard rho 算法，复杂度约为 2^{128}，恰好满足要求。因此，使用 256 比特曲线即可。

场景二：损失因子为 q_H 的非紧致归约。 许多 ROM 证明（如 Schnorr 签名的 Pointcheval-Stern 证明）引入了 q_H 倍的安全损失，其中 q_H 是哈希查询次数。假设 q_H = 2^{60}（一个合理的上界），则 DDH 假设需要达到 128 + 60 = 188 比特安全性。要在椭圆曲线上实现 188 比特安全性，需要使用约 376 比特的曲线——这比紧致归约下所需的 256 比特大了 47%。

场景三：多用户损失。 在 n = 2^{30}（约十亿用户）的多用户场景中，简单归约引入 n 倍损失。若叠加 q_H 的损失，DDH 假设需要达到 128 + 60 + 30 = 218 比特安全性，对应约 436 比特的椭圆曲线。

Schnorr 签名：紧致与非紧致归约的典型案例

Schnorr 签名是理解安全损失实际影响的最佳案例，因为它同时拥有非紧致的经典证明和近年来逐步推进的紧致化工作。

Schnorr 签名方案：签名者持有私钥 x，公钥 Y = g^x。签名消息 m 时，随机选择 k ← Z_p，计算 R = g^k，e = H(R || m)，s = k - xe mod p，输出签名 (e, s)。验证：检查 e = H(g^s · Y^e || m)。

Pointcheval 和 Stern（1996/2000）给出的经典 EUF-CMA 安全证明使用了分叉引理（forking lemma）：将攻击者运行两次，在同一个随机预言机查询点给出不同的哈希值，从两次伪造中提取出离散对数。归约的安全损失分析如下：

Schnorr 签名安全损失分析（Pointcheval-Stern 归约）

归约结构：
  给定 DL 挑战 (g, Y = g^x)，构造归约 B：
  1. B 模拟签名预言机（编程随机预言机）
  2. 等待 A 输出伪造 (m*, e*, s*)
  3. 重卷 A 到产生 e* 的查询点，给出不同哈希值 e*'
  4. 获得第二个伪造 (m*, e*', s*')
  5. 提取：x = (s*' - s*) / (e* - e*') mod p

安全损失：
  分叉引理概率损失：Adv_{DL}(B) ≥ acc(A)^2 / q_H
  其中 q_H 是哈希查询次数
  若 q_H = 2^{64}，要达到 128 位 EUF-CMA 安全
  需要 DL 假设提供 128 + 64 = 192 位安全性（线性损失版本）

对比紧致归约的情形。Fuchsbauer、Plouviez 和 Seurin（2020）在代数群模型（AGM）+ ROM 下证明了 Schnorr 签名具有紧致的 EUF-CMA 安全性。以下表格以 2^{64} 次查询为基准，对比不同归约策略下的参数需求：

这一对比揭示了紧致归约研究的核心实践意义：在非紧致归约下，Schnorr 签名若要在互联网规模（2^{64} 次查询）下提供 128 比特安全性，需要 384 位椭圆曲线——性能开销相比 256 位曲线增加约 3.4 倍（群运算成本与曲线位数的三次方近似成正比）。紧致归约将需求拉回 256 位曲线，直接决定了实际部署中的计算成本和带宽消耗。

需要强调的是，AGM 模型（代数群模型）假设攻击者在群上的每次运算都是”可解释的”——即攻击者输出的每个群元素都是已知群元素的线性组合。这比标准模型更强，比 ROM 的理想化程度更低，是目前分析 Schnorr 类签名安全性时的务实折中。以下表格从更一般的角度总结不同安全损失场景下的参数需求：

这一分析清晰地表明：安全损失不是一个纯粹的理论概念，而是直接驱动参数选取的工程因素。当安全损失达到 2^{90} 时，所需的 RSA 模数膨胀到 15360 位——这在实践中几乎不可接受，意味着该方案的安全性证明对实际参数选择已丧失了指导意义。这正是为什么紧致归约的研究具有如此重要的实践价值。

其次是单用户安全性与多用户安全性（multi-user security）之间的差距。经典的安全定义通常在单一密钥对的场景下形式化——只有一个挑战者持有一个密钥对。但在实际系统中，数以亿计的用户同时使用同一方案的不同密钥对，攻击者只需攻破其中任意一个用户就算成功。从单用户安全到多用户安全的简单归约通常引入用户数量 n 的倍数损失——如果方案在单用户设置下具有 ε 的安全性，在 n 个用户的设置下安全性退化到 nε。对于 n = 2^{30} 的规模（十亿级用户），这意味着需要额外的 30 比特安全参数。紧致的多用户安全归约可以消除或减小这一损失，这是近年来研究的热点之一。例如，Bader 等人证明了在理想密码模型下，许多常用的对称加密方案天然具有紧致的多用户安全性。

最后是实际参数选取中需要考虑的综合因素。除了安全归约的紧致程度外，还需要考虑底层困难问题的最佳已知攻击算法的复杂度、安全边际（security margin）的选取、以及实现中的侧信道抵抗等问题。以 NIST 后量子密码标准 ML-KEM 为例，其参数选取不仅考虑了 LWE 问题在经典和量子计算机上的最佳已知攻击复杂度，还留出了足够的安全边际以应对未来算法的进步。在安全级别的划分上，NIST 采用了相对于 AES 和 SHA-3 的安全强度来锚定——例如 NIST Level 1 要求至少等价于 AES-128 的强度，Level 5 要求至少等价于 AES-256。

可证明安全理论的另一个实践启示是：安全定义的选择应当匹配实际的部署场景。如果一个加密方案仅在 IND-CPA 意义下被证明安全，但部署环境中攻击者可能获得解密预言机的访问（哪怕是通过侧信道），则该方案在实践中可能是不安全的。反过来，如果部署环境能够严格排除选择密文攻击的可能性（例如在某些特定的广播加密场景中），则 IND-CPA 安全性可能已经足够。安全工程师的职责不仅在于选择一个”足够强”的方案，更在于准确地分析实际威胁模型，选择与之匹配的安全定义。

总而言之，可证明安全是现代密码学的方法论基石。它将密码方案的安全性从模糊的直觉和经验判断提升为精确的数学命题，使得安全性可以被定义、被证明、被量化。从 Goldwasser-Micali 的语义安全到 Canetti 的 UC 框架，从 Bellare-Rogaway 的随机预言机模型到 Waters 的对偶系统加密，可证明安全的理论不断发展和深化，持续指引着密码方案从设计到部署的每一个环节。理解可证明安全的方法论，不仅是密码学研究者的基本素养，更是每一个需要做出密码方案选型决策的安全从业者的必修课。

密码学百科系列 · 第 50 篇

← 上一篇：密码学与隐私 | 系列目录 | 下一篇：对称密码的可证明安全 →