In 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 { D n } n ∈ N {\displaystyle \scriptstyle \{D_{n}\}_{n\in \mathbb {N} }} and { E n } n ∈ N {\displaystyle \scriptstyle \{E_{n}\}_{n\in \mathbb {N} }} be two distribution ensembles indexed by a security parameter n (which usually refers to the length of the input); we say they are computationally indistinguishable if for any non-uniform probabilistic polynomial time algorithm A, the following quantity is a negligible function in n:
δ ( n ) = | Pr x ← D n [ A ( x ) = 1 ] − Pr x ← E n [ A ( x ) = 1 ] | . {\displaystyle \delta (n)=\left|\Pr _{x\gets D_{n}}[A(x)=1]-\Pr _{x\gets E_{n}}[A(x)=1]\right|.}denoted D n ≈ E n {\displaystyle D_{n}\approx E_{n}} .1 In other words, every efficient algorithm A's behavior does not significantly change when given samples according to Dn or En in the limit as n → ∞ {\displaystyle n\to \infty } . 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, A {\displaystyle A} , 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.2: 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.3: 108
External links
- 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
This article incorporates material from computationally indistinguishable on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.
References
Lecture 4 - Computational Indistinguishability, Pseudorandom Generators http://www.cs.princeton.edu/courses/archive/spr10/cos433/lec4.pdf ↩
Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press. /wiki/Oded_Goldreich ↩
Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press. /wiki/Oded_Goldreich ↩