形式陈述

混合论证构造实验序列 $H_0,H_1,\ldots,H_t$$H_0,H_1,\dots ,H_t$，每对相邻实验只改变一个组件。若第 $i$$i$ 个相邻对的判别优势至多 $\varepsilon_i(n)$${\epsilon }_i(n)$，由三角不等式总优势至多 $\sum_{i=1}^{t(n)}\varepsilon_i(n)$$\sum _{i=1}^{t(n)}{\epsilon }_i(n)$。当 $t(n)$$t(n)$ 为多项式，并存在一个对所有相关 $i$$i$ 统一成立的可忽略函数 $\mu(n)$$\mu (n)$ 使 $\varepsilon_i(n)\le\mu(n)$${\epsilon }_i(n)\le \mu (n)$ 时，总和仍可忽略。仅仅对每个随 $n$$n$ 变化的索引分别声称“可忽略”而没有统一界并不足够。相邻替换必须精确归约到已知假设。

直觉

不直接跨越两个复杂世界，而是一次替换一块；若每一步都几乎看不出，整个变化也几乎看不出。

例子与边界

证明多块密文安全时可逐块把真实加密替换为零消息加密。若总体区分优势明显，平均论证说明至少某一相邻步也明显，从而构造攻击者。指数多个混合会使可忽略误差累积失控，因此步骤数条件不可省略。

推论与应用

混合论证用于加密、PRG、零知识、随机预言机替换和复杂协议组合证明。

参考资料

• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，Chs. 2–12。
• Oded Goldreich, Foundations of Cryptography, Vol. 1, Cambridge University Press, 2001，Chs. 1–4。