查看“︁计算不可区分性”︁的源代码

{{NoteTA|G1=IT}}
在[[算法分析]]和[[密码学]]中，如果没有高效的算法可以区分两个分布族之间的差异（或区分出两者的概率可以忽略），那么两个分布族被称为是'''计算不可区分'''（{{lang-en|'''computationally indistinguishable'''}}）的。

==正式定义==
令<math>\scriptstyle\{ D_n \}_{n \in \mathbb{N}}</math>和<math>\scriptstyle\{ E_n \}_{n \in \mathbb{N}}</math> 是两个{{link-en|分布集合|distribution ensemble}}，下标''n''（通常指输入的长度）是{{link-en|安全参数|security parameter}}。如果对于任意的{{link-en|均匀 (复杂度)|Uniformity (complexity)|非均匀}}概率[[多项式时间]][[算法]] ''A''，以下值是一个''n''上的[[可忽略函数]]，则我们说它们在计算上是不可区分的：

: <math>\delta(n) = \left| \Pr_{x \gets D_n}[ A(x) = 1] - \Pr_{x \gets E_n}[ A(x) = 1] \right|</math>

记为<math>D_n \approx E_n</math>。<ref>{{Cite web |url=http://www.cs.princeton.edu/courses/archive/spr10/cos433/lec4.pdf |title=Lecture 4 - Computational Indistinguishability, Pseudorandom Generators |access-date=2022-09-09 |archive-date=2022-09-09 |archive-url=https://web.archive.org/web/20220909050911/https://www.cs.princeton.edu/courses/archive/spr10/cos433/lec4.pdf |dead-url=no }}</ref> 换言之，在<math>n\to \infty</math>时，每个高效的算法''A''的行为在''D''<sub>''n''</sub>和''E''<sub>''n''</sub>上不会有明显变化。对计算不可区分性的另一种解释是，主动尝试区分这两个集合的多项式时间算法不能实现目标：任何这样的算法的表现与单纯猜测相比，优势可以忽略不计。

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

== 参考资料 ==
<references/>

==外部链接==
* [[Yehuda Lindell]]. [http://u.cs.biu.ac.il/~lindell/89-656/main-89-656.html Introduction to Cryptography] {{Wayback|url=http://u.cs.biu.ac.il/~lindell/89-656/main-89-656.html |date=20220703175249 }}
* Donald Beaver and [[Silvio Micali]] and [[Phillip Rogaway]], The Round Complexity of Secure Protocols (Extended Abstract), 1990, pp.&nbsp;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 (computer scientist)|Jonathan Katz]], [[Yehuda Lindell]], "Introduction to Modern Cryptography: Principles and Protocols," Chapman & Hall/CRC, 2007


{{PlanetMath attribution|id=3457|title=computationally indistinguishable}}

[[Category:算法信息论]]