公理与理论库定义

不可区分性

Computational indistinguishability

任意高效判别器区分两个分布族的优势都是可忽略量。

形式陈述

两个按安全参数 $n$ $n$ 索引的分布族 $X_n,Y_n$ $X_{n}, Y_{n}$ 计算不可区分，若对任意概率多项式时间判别器 $D$ $D$ ，优势

$$ \left|\Pr[D(X_n)=1]-\Pr[D(Y_n)=1]\right| $$

| Pr [D (X_{n}) = 1] - Pr [D (Y_{n}) = 1] |

作为 $n$ $n$ 的函数是可忽略的。量词顺序很关键：对每个固定的高效判别器 $D$ $D$ ，可以有依赖于 $D$ $D$ 的可忽略界 $\mu_D$ $μ_{D}$ ；定义并不要求先选出一个同时支配所有判别器的全局可忽略函数。信息论不可区分则以统计距离为零或可忽略来约束，不限制判别器算力。

直觉

即使两个实验在数学上不同，只要任何现实可行的算法都看不出差别，它们在计算安全意义下等价。

例子与边界

伪随机生成器输出应与等长均匀串不可区分。若存在某个多项式时间统计测试保持常数优势，就已否定不可区分性。单个有限参数下“没测出来”不是渐近证明；判别器还可非均匀或带辅助输入，具体定义必须说明。

推论与应用

不可区分性是现代加密安全游戏、混合论证、零知识和伪随机性的共同语言。

参考资料

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。