计算不可区分性

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

正式定义

令$\{D_n{\}}_{n\in \mathbb{N}}$和$\{E_n{\}}_{n\in \mathbb{N}}$ 是两个Template:Link-en，下标n（通常指输入的长度）是Template:Link-en。如果对于任意的Template:Link-en概率多项式时间算法 A，以下值是一个n上的可忽略函数，则我们说它们在计算上是不可区分的：

$\delta (n)=|\underset{x\leftarrow D_n}{\mathrm{Pr}}[A(x)=1]-\underset{x\leftarrow E_n}{\mathrm{Pr}}[A(x)=1]|$

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

相关概念

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

外部链接

• Yehuda Lindell. Introduction to Cryptography Template:Wayback
• 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

Template:PlanetMath attribution