计算不可区分性

在算法分析和密码学中，如果没有高效的算法可以区分两个分布族之间的差异（或区分出两者的概率可以忽略），那么两个分布族被称为是计算不可区分（）的。

正式定义
令和 是两个，下标n（通常指输入的长度）是。如果对于任意的概率多项式时间算法 A，以下值是一个n上的可忽略函数，则我们说它们在计算上是不可区分的：



记为。 换言之，在时，每个高效的算法A的行为在Dn和En上不会有明显变化。对计算不可区分性的另一种解释是，主动尝试区分这两个集合的多项式时间算法不能实现目标：任何这样的算法的表现与单纯猜测相比，优势可以忽略不计。

相关概念
定义中隐含的条件是算法必须根据其中一个分布的单个样本中决定。有人可能会设想这样一种情况，即算法为了区分两个分布，可以根据需要访问尽可能多的样本。因此，两个分布无法由多项式时间算法通过观察多个样本区分的情形，被称为无法通过多项式时间采样区分（）。Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press. 如果多项式时间算法可以在多项式时间内生成样本，或者可以访问为其生成样本的隨機預言機，那么多项式时间采样的不可区分性等同于计算不可区分性。

 参考资料 

外部链接
 Yehuda Lindell. 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

Category:算法信息论