不可区分性

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

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

若两个分布完全相同，任何区分器成功率恰为 $1/2$。若一个总输出 0、另一个总输出 1，读取一 bit 即完全区分。伪随机生成器要求 $G(U_s)$ 与 $U_m$ 对多项式时间区分器不可区分，尽管输出集合 $S=\{G(z):z\in \{0,1{\}}^s\}$ 至多有 $2^s$ 个点。无界判别器可以枚举种子并检查样本是否属于 $S$：生成器世界接受概率为 $1$，均匀世界至多为 $2^{s-m}$，故优势至少 $1-2^{s-m}$。当 $m=s+1$ 时已经至少为 $1/2$。安全所依赖的并非分布接近，而是这种成员判断不能被高效实现；支持很小本身也不证明计算安全。

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

不可区分性是加密安全游戏、零知识和伪随机性的共同语言。计算安全公理库计算安全Computational security仅要求任何资源受限攻击者的成功优势足够小的安全概念。限制攻击者资源，可忽略函数公理库可忽略函数Negligible function比任意逆多项式最终更小的非负函数。规定允许优势；混合论证公理库混合论证Hybrid argument在一串相邻实验间逐步替换组件并累加不可区分优势的证明方法。则把复杂分布比较拆成相邻两世界的比较。

语义安全公理库语义安全Semantic security · Computational semantic security密文不让多项式时间攻击者显著获得明文任何可计算信息的安全性。与加密不可区分性的等价，必须在同一私钥／公钥模型和同一攻击接口下陈述。私钥的窃听版本 SEM-EAV 对应 IND-EAV；允许选择明文查询的 SEM-CPA 才对应 IND-CPA。公钥模型中攻击者已能自行加密，但仍要固定消息选择、辅助信息和挑战规则，不能把未标攻击模型的“语义安全”直接当作所有 CPA 保证。