计算不可区分性

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

正式定义

令$\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的行为在D_n和E_n上不会有明显变化。对计算不可区分性的另一种解释是，主动尝试区分这两个集合的多项式时间算法不能实现目标：任何这样的算法的表现与单纯猜测相比，优势可以忽略不计。

相关概念

定义中隐含的条件是算法$A$必须根据其中一个分布的单个样本中决定。有人可能会设想这样一种情况，即算法为了区分两个分布，可以根据需要访问尽可能多的样本。因此，两个分布无法由多项式时间算法通过观察多个样本区分的情形，被称为无法通过多项式时间采样区分（英语：indistinguishable by polynomial-time sampling）。 如果多项式时间算法可以在多项式时间内生成样本，或者可以访问为其生成样本的随机预言机，那么多项式时间采样的不可区分性等同于计算不可区分性。

外部链接

• 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

本条目含有来自PlanetMath《computationally indistinguishable》的内容，著作权遵守知识共享协议：署名-相同方式共享协议。