安全实验、对手与优势函数

形式陈述 ​

安全实验是由安全参数公理库安全参数Security parameter共同索引密码算法族、资源规模与失败概率的渐近尺度。 $\lambda$ 索引的随机交互过程 ${\mathsf{Exp}}^A(1^{\lambda })$。挑战者依规格生成密钥、实例或隐藏随机量，向对手 $A$ 提供公开输入与约定的查询接口；对手可根据此前响应自适应地选择后续消息，最终实验输出一位 $0$ 或 $1$。完整定义必须给出对手可见的信息、查询的次数与次序、禁止条件、运行时间度量以及所有终止规则。

实验的概率空间包含挑战者、对手和被调用随机算法公理库随机化算法Randomized algorithm把随机比特作为额外输入并分析输出正确率或运行时间分布的算法。使用的全部随机币，以及实验另行采样的输入。成功概率可以写成 $\text{Pr}[{\mathsf{Exp}}^A(1^{\lambda })=1]$。比较两个世界时，常用区分优势

$${\mathrm{Adv}}_A^{\mathsf{dist}}(\lambda )=|\text{Pr}[A_0(1^{\lambda })=1]-\text{Pr}[A_1(1^{\lambda })=1]|.$$

若实验均匀采样隐藏位 $b\in \{0,1\}$，对手输出猜测 $b^{\prime }$，也常写

$${\mathrm{Adv}}_A(\lambda )=|2\text{Pr}[b^{\prime }=b]-1|.$$

在对应设定下两种写法表达同一偏离随机猜测的能力；有些文献省略因子 $2$ 或用带符号差，比较定理前必须先核对归一化。

直觉 ​

“攻击者学不到信息”之所以含糊，是因为没有说明攻击者拿到什么、能问什么、何时必须作答，也没有说明“学到”如何测量。安全实验把这些隐含条件变成一场双方都能执行的小游戏：挑战者搭建现实世界或理想世界，对手在限定接口内互动，最后用一个事件或一个输出位把目标压缩成概率。

优势不是单纯的成功率，而是超出基线的部分。猜均匀隐藏位时，$1/2$ 的成功率没有信息价值；只有偏离 $1/2$ 的量才反映区分能力。把资源写进对手接口同样关键：不限制时间与查询的实验，描述的是信息论能力；加入时间公理库时间复杂度Time complexity · Running time在固定计算模型与输入编码后，算法运行步骤数随输入规模增长的量级。和查询预算后，才形成计算攻击模型的原料。

例子与边界 ​

IND-CPA 实验的骨架如下：挑战者生成密钥并允许对手查询加密；对手提交等长消息 $m_0,m_1$；挑战者均匀采样 $b$，返回 $m_b$ 的挑战密文；对手可按定义继续查询，最后输出 $b^{\prime }$。等长要求防止密文长度直接泄漏隐藏位；查询是否自适应、挑战后是否继续开放，以及使用公钥接口还是加密 oracle，都必须由具体方案类型写清。实验最终记录 $b^{\prime }=b$，优势衡量其相对随机猜测提升了多少。

这个骨架还不是“方案安全”的完整结论。单个固定对手可能优势很小，不能推出其他对手也小；单个固定参数上的概率也不能推出渐近性质。把“对所有允许的高效对手，优势随 $\lambda$ 可忽略”加上去，才进入计算安全公理库计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。的量词层。

成功概率与区分优势也不能随意互换。例如伪造实验可能没有自然的 $1/2$ 猜测基线，直接用成功概率更清楚；两个世界若先验不均匀，上面的等价式也需修改。遗漏挑战者或对手自身的随机性，会把本来随机的事件误当作固定结果；只画消息流程而不写查询上限、禁止查询和输出事件，则无法支持严谨证明。

推论与应用 ​

选择明文、选择密文、不可伪造性、伪随机性与哈希碰撞抗性都可由“挑战者—对手—输出事件”统一组织。不可区分性公理库不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。关注两个世界输出分布的差异，混合论证则在一串相邻实验之间逐步界定优势损失。归约证明把能够赢得目标实验的对手包装成另一个实验的对手，因此接口是否匹配、模拟是否保持分布、资源增加多少，都是证明主体而非记号细节。

实验定义只覆盖它赋予对手的能力。没有侧信道接口的 IND-CPA 结论不能自动抵抗计时泄漏，没有解密查询的实验不能代表选择密文攻击。安全主张应始终带着实验名称、资源约束和优势归一化一起阅读。

参考资料

• Dan Boneh and Victor Shoup, A Graduate Course in Applied Cryptography, version 0.6, 2023，Chs. 2–3，security games, adversaries, and advantage measures。
• Mihir Bellare and Phillip Rogaway, “Introduction to Modern Cryptography,” course notes, 2005，game-based definitions and concrete security conventions。