Editing Computational indistinguishability

{{Short description|In computer science, relationship between two families of distributions}}
In [[Analysis of algorithms|computational complexity]] and [[cryptography]], two families of distributions are '''computationally indistinguishable''' if no efficient algorithm can tell the difference between them except with negligible probability.

==Formal definition==
Let <math>\scriptstyle\{ D_n \}_{n \in \mathbb{N}}</math> and <math>\scriptstyle\{ E_n \}_{n \in \mathbb{N}}</math> be two [[distribution ensemble]]s indexed by a [[security parameter]] ''n'' (which usually refers to the length of the input); we say they are computationally indistinguishable if for any [[Uniformity (complexity)|non-uniform]] probabilistic [[polynomial time]] [[algorithm]] ''A'', the following quantity is a [[negligible function (cryptography)|negligible function]] in ''n'':

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

denoted <math>D_n \approx E_n</math>.<ref>[http://www.cs.princeton.edu/courses/archive/spr10/cos433/lec4.pdf Lecture 4 - Computational Indistinguishability, Pseudorandom Generators]</ref> In other words, every efficient algorithm ''A'''s behavior does not significantly change when given samples according to ''D''<sub>''n''</sub> or ''E''<sub>''n''</sub> in the limit as <math>n\to \infty</math>. Another interpretation of computational indistinguishability, is that polynomial-time algorithms actively trying to distinguish between the two ensembles cannot do so: that any such algorithm will only perform negligibly better than if one were to just guess.

==Related notions==
Implicit in the definition is the condition that the algorithm, <math>A</math>, must decide based on a single sample from one of the distributions. One might conceive of a situation in which the algorithm trying to distinguish between two distributions, could access as many samples as it needed. Hence two ensembles that cannot be distinguished by polynomial-time algorithms looking at multiple samples are deemed '''indistinguishable by polynomial-time sampling'''.<ref name=Goldreich>[[Oded Goldreich|Goldreich, O.]] (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press.</ref>{{rp|107}} If the polynomial-time algorithm can generate samples in polynomial time, or has access to a [[random oracle]] that generates samples for it, then indistinguishability by polynomial-time sampling is equivalent to computational indistinguishability.<ref name=Goldreich />{{rp|108}}

== References ==
<references/>

==External links==
* [[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.&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:Algorithmic information theory]]