混合论证

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

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

例如比较 $q$ 个独立种子产生的 PRG 输出与 $q$ 个独立均匀串，可逐块替换。相邻两世界中的其余块由归约自行生成，剩余一块接入单次 PRG 挑战；若端点优势为 $ϵ$，某一步优势至少 $ϵ/q$。这依赖于独立种子；同一 PRF 输入的重复查询必须保持回答一致，不能当成新鲜独立随机值。

“存在一个好索引”本身还不是 uniform PPT 归约。如果相邻替换可由同一多项式时间模拟器接收索引后执行，可以让归约随机选择索引，而不为每个参数额外写入一份建议。具体地，对 $t\ge 1$，将 $t$ 步补到二的幂 $T<2t$，多出的混合保持终点不变，再均匀选取 $j\in \{1,\dots ,T\}$。若 $p_j$ 为同一最终判别器在第 $j$ 个混合中的接受概率，则这个统一归约的带符号优势为 $(p_0-p_t)/T$，因为相邻差望远镜求和。取绝对值后便得到端点优势的 $1/T$；这里只构造了一台依赖原判别器的统一对手，没有交换“对手”和“可忽略界”的量词。

相邻混合必须真的只改变归约能模拟的一部分；攻击者查询若自适应，模拟要保持一致性。指数多个混合会使可忽略误差累积失控，$ϵ/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 加密正文，解释正确性、选择密文安全的组合证明，以及认证绑定、nonce 与重放的不同职责。先替换封装密钥、再调用 DEM 保密与完整性；三者都必须逐步模拟对手的查询接口，而不是只比较静态输出。

两个在线子程序的完整替换证明公理库固定会话下的安全组合Fixed-session secure composition · Two-subroutine composition在明确隔离的两个在线子程序会话中构造统一模拟器，逐次替换并累加区分优势与资源预算。明确写出三种执行网络，第二个包装中保留已经替换的第一理想服务和模拟器，并把包装运行时间计入底层区分预算。