混合论证

混合论证不直接跨越两个复杂世界，而是在两个难以比较的分布或游戏之间插入一串中间世界，每次只替换一个局部组件。若每一步都几乎看不出，整个变化也几乎看不出；反过来，若起点与终点可被显著区分，三角不等式保证至少有一对相邻混合也可被区分，再把这一区分器转成破坏底层原语的攻击。它把“大规模同时替换”拆为可归约的单步替换，代价通常是混合数量的线性优势损失。

证明多块密文安全时可逐块把真实加密替换为零消息加密。若总体区分优势明显，平均论证说明至少某一相邻步也明显，从而构造攻击者。

要证明 $q$ 个 PRF 输出与 $q$ 个独立随机值不可区分，可定义第 $i$ 个混合：前 $i$ 个查询用随机函数回答，后面用 PRF。若总区别优势为 $ϵ$，则某相邻对优势至少 $ϵ/q$，由此嵌入一个 PRF 挑战。

相邻混合必须真的只改变归约能模拟的一部分；攻击者查询若自适应，模拟要保持一致性。指数多个混合会使可忽略误差累积失控，$ϵ/q$ 也可能不再可用，所以步骤数条件不可省略，通常要求序列长度为多项式。

混合论证用于加密、PRG、零知识、随机预言机替换和复杂协议组合证明。不可区分性公理库不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。提供端点目标，计算安全公理库计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。控制攻击优势，可忽略函数公理库可忽略函数Negligible function比任意逆多项式最终更小的非负函数。在多项式次求和后仍可忽略。DDH公理库判定 Diffie–Hellman 假设Decisional Diffie–Hellman assumption · DDH assumption随机 Diffie–Hellman 三元组与以独立随机群元素结尾的三元组对高效判别器不可区分。证明把真实 DH tuple 换成随机 tuple，ROM公理库随机预言机模型Random oracle model · ROM把所有参与者共享的哈希接口理想化为可自适应查询且响应一致的真随机函数。证明替换或编程 oracle 响应，KEM–DEM 组合公理库KEM–DEM 混合加密KEM–DEM hybrid encryption · Hybrid public-key encryption以公钥 KEM 封装一次性会话密钥，再由认证 DEM 保护正文，并在匹配安全模型下组合成选择密文安全加密。先替换封装密钥、再调用 DEM 保密与完整性；三者都必须逐步模拟对手的查询接口，而不是只比较静态输出。