在算法分析和密码学中，如果没有高效的算法可以区分两个分布族之间的差异（或区分出两者的概率可以忽略），那么两个分布族被称为是计算不可区分（）的。
正式定义
令\scriptstyle\{ D_n \}_{n \in \mathbb{N}}和\scriptstyle\{ E_n \}_{n \in \mathbb{N}} 是两个，下标n（通常指输入的长度）是。如果对于任意的概率多项式时间算法 A，以下值是一个n上的可忽略函数，则我们说它们在计算上是不可区分的：
: \delta(n) = \left| \Pr_{x \gets D_n}[ A(x) = 1] - \Pr_{x \gets E_n}[ A(x) = 1] \right|
记为D_n \approx E_n。 换言之，在n\to \infty时，每个高效的算法A的行为在Dn和En上不会有明显变化。对计算不可区分性的另一种解释是，主动尝试区分这两个集合的多项式时间算法不能实现目标：任何这样的算法的表现与单纯猜测相比，优势可以忽略不计。
相关概念
定义中隐含的条件是算法A必须根据其中一个分布的单个样本中决定。有人可能会设想这样一种情况，即算法为了区分两个分布，可以根据需要访问尽可能多的样本。因此，两个分布无法由多项式时间算法通过观察多个样本区分的情形，被称为无法通过多项式时间采样区分（）。 如果多项式时间算法可以在多项式时间内生成样本，或者可以访问为其生成样本的隨機預言機，那么多项式时间采样的不可区分性等同于计算不可区分性。
参考资料
外部链接
- Yehuda Lindell. [http://u.cs.biu.ac.il/~lindell/89-656/main-89-656.html Introduction to Cryptography]
- Donald Beaver and Silvio Micali and Phillip Rogaway, The Round Complexity of Secure Protocols (Extended Abstract), 1990, pp. 503–513
- Shafi Goldwasser and Silvio Micali. Probabilistic Encryption. JCSS, 28(2):270–299, 1984
- Oded Goldreich. Foundations of Cryptography: Volume 2 – Basic Applications. Cambridge University Press, 2004.
- Jonathan Katz, Yehuda Lindell, "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007
评论 (0)