不可区分性

不可区分性把“看起来一样”落实为两个候选世界：给区分器一个样本并要求判断来源，优势衡量其超出基线的能力。即使两个分布在数学上不同，只要任何现实可行的算法都看不出差别，它们就在计算安全意义下等价。辅助信息、查询接口、样本数量以及 uniform/nonuniform 对手选择会直接改变安全强度，必须与 PPT 限制一起陈述。

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

若两个分布完全相同，任何区分器成功率恰为 $1/2$。若一个总输出 0、另一个总输出 1，读取一 bit 即完全区分。伪随机生成器要求 $G(U_s)$ 与 $U_m$ 对多项式时间区分器不可区分，尽管前者支持集大小至多 $2^s<2^m$，无界枚举器原则上可区分；这正是计算层与统计层的边界。

只比较均值、方差或几张直方图不足以证明不可区分；攻击者可使用任意允许的高效算法。有限实验没有发现区分器也不是对所有 PPT 对手的渐近证明；比较归约界时还必须先统一上面的优势因子。

不可区分性是现代加密安全游戏、混合论证、零知识和伪随机性的共同语言。计算安全公理库计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。 用多项式攻击者量化，可忽略函数公理库可忽略函数Negligible function比任意逆多项式最终更小的非负函数。 规定允许优势；语义安全公理库语义安全Semantic security · Computational semantic security密文不让多项式时间攻击者显著获得明文任何可计算信息的安全性。 与 CPA 不可区分有等价关系，混合论证公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。 则是证明复杂分布不可区分的主要方法。