统计不可区分性

形式陈述 ​

设 $X_{\lambda }$ 与 $Y_{\lambda }$ 是由同一安全参数公理库安全参数Security parameter共同索引密码算法族、资源规模与失败概率的渐近尺度。 $\lambda$ 索引、取值于共同样本空间 ${\mathrm{\Omega }}_{\lambda }$ 的分布族。本库采用概率距离约定

$$\mathrm{\Delta }(X_{\lambda },Y_{\lambda })=\frac{1}{2}\sum _{\omega \in {\mathrm{\Omega }}_{\lambda }}|\text{Pr}[X_{\lambda }=\omega ]-\text{Pr}[Y_{\lambda }=\omega ]|.$$

若存在可忽略函数 $\mu$，使充分大的 $\lambda$ 都满足 $\mathrm{\Delta }(X_{\lambda },Y_{\lambda })\le \mu (\lambda )$，则称两族统计不可区分，记作 $X{\approx }_{s}Y$。若每个 $\lambda$ 上的距离都为 $0$，两分布便完全相同，称为完美不可区分。这里的结论针对整个 ensemble；单个固定参数下距离很小，不足以给出渐近安全性。

总变差距离的事件刻画给出

$$\mathrm{\Delta }(X_{\lambda },Y_{\lambda })=\underset{T\subseteq {\mathrm{\Omega }}_{\lambda }}{sup}|\text{Pr}[X_{\lambda }\in T]-\text{Pr}[Y_{\lambda }\in T]|.$$

因此，即使允许判别器拥有无限计算能力，最佳接受概率差仍恰为 $\mathrm{\Delta }$。若实验均匀选择隐藏位 $b$，在 $b=0$ 时给出 $X_{\lambda }$ 样本、在 $b=1$ 时给出 $Y_{\lambda }$ 样本，并把优势归一化为 $|2\text{Pr}[b^{\prime }=b]-1|$，最优优势同样等于 $\mathrm{\Delta }$；若改用 $|\text{Pr}[b^{\prime }=b]-1/2|$，数值则是 $\mathrm{\Delta }/2$。引用安全界时必须连同这项归一化一起说明。

统计不可区分允许任意事件测试，因而蕴含计算不可区分性公理库不可区分性Computational indistinguishability任意高效判别器区分两个分布族的优势都是可忽略量。：PPT 判别器只是所有判别器的一小类。反向一般不成立，因为计算受限的观察者可能无法识别一个数学上很显著、却难以高效描述或搜索的事件。

直觉 ​

统计不可区分不是“若干统计量相近”，而是任何观察规则都找不到明显差异。把两个分布想成两只装有标签的袋子：判别器可以事先或根据样本挑选最有利的事件，甚至穷举整个空间；总变差距离直接给出它最多能把两个世界的接受概率拉开多少。

这一概念仍允许极罕见的差别。只要全部差异质量随 $\lambda$ 可忽略，无界观察者虽然知道应检查哪个事件，也只能以可忽略优势遇到它。完美不可区分更强：不是差别难遇到，而是两个世界在每个事件上都给出完全相同的概率。

例子与边界 ​

一次一密展示完美情形。固定任意等长消息 $m$，均匀密钥 $K\leftarrow \{0,1{\}}^n$ 产生密文 $C=K\oplus m$。映射 $K\mapsto K\oplus m$ 是双射，所以对任意两个固定消息 $m_0,m_1$，相应密文都在 $\{0,1{\}}^n$ 上均匀分布，距离严格为 $0$；这不是依赖攻击者算力的结论。

再令 $X_{\lambda }$ 恒为 $0$，而 $Y_{\lambda }$ 以概率 $2^{-\lambda }$ 输出 $1$、其余时候输出 $0$。事件 $T=\{1\}$ 是最优测试，故 $\mathrm{\Delta }(X_{\lambda },Y_{\lambda })=2^{-\lambda }$。两族并不完全同分布，却统计不可区分；差异集中在一个已知但可忽略地发生的事件上。

伪随机生成器给出反向不成立的典型边界。若 $G:\{0,1{\}}^s\to \{0,1{\}}^m$ 且 $m>s$，则 $G(U_s)$ 的支持集至多有 $2^s$ 个点。无界判别器可以枚举该支持集，并将它与 $U_m$ 显著区分；安全 PRG 只保证高效判别器做不到。均值、方差、经验直方图乃至有限次抽样都不能证明总变差上界，因为未检查的事件仍可能承载全部差异。

若攻击者获得 $q(\lambda )$ 个独立样本，联合分布的距离至多为 $q(\lambda )\mathrm{\Delta }(X_{\lambda },Y_{\lambda })$；多项式个样本仍保持可忽略差距，但指数个样本可能放大稀有事件。样本是否独立、数量是否受限，必须属于安全实验的一部分，而不能从单样本定义中默默推断。

推论与应用 ​

统计不可区分为信息论安全提供统一语言。完美保密公理库完美保密Perfect secrecy · Information-theoretic security对每种消息先验，观察密文都不改变消息分布的无条件安全定义。对应距离为零的极端情形；统计零知识、统计隐藏承诺和秘密共享则允许可忽略的分布误差。由于结论覆盖无界判别器，它不依赖某个计算困难假设，却仍依赖安全参数、泄露接口与样本数量的准确建模。

总变差还支持安全误差的组合：经过任意随机后处理，距离不会增大；按混合路径逐步替换分布时，三角不等式允许累加各步误差。这些性质解释了为什么统计模拟得到的近似视图可以安全地送入后续协议，同时也提醒人们记录累积次数，避免把许多可忽略项无条件地视为一个可忽略项。

参考资料

• Oded Goldreich, Foundations of Cryptography, Vol. 1, Cambridge University Press, 2001，computational and statistical indistinguishability。
• Jonathan Katz and Yehuda Lindell, Introduction to Modern Cryptography, 3rd ed., CRC Press, 2020，security definitions and statistical distance。
• David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov Chains and Mixing Times, 2nd ed., AMS, 2017，§4.1, standard characterizations of total variation。