Computational indistinguishability Contents Formal definition Related notions References External links Navigation menuLecture 4 - Computational Indistinguishability, Pseudorandom GeneratorsIntroduction to Cryptography
Algorithmic information theory
computational complexitycryptographydistribution ensemblessecurity parameternon-uniformpolynomial timealgorithmnegligible functionrandom oracle
In computational complexity and cryptography, two families of distributions are computationally indistinguishable if no efficient algorithm can tell the difference between them except with small probability.
Contents
1 Formal definition
2 Related notions
3 References
4 External links
Formal definition
Let Dnn∈Ndisplaystyle scriptstyle D_n_nin mathbb N and Enn∈Ndisplaystyle scriptstyle E_n_nin 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)=|Prx←Dn[A(x)=1]−Prx←En[A(x)=1]|.displaystyle delta (n)=left
![delta (n)=left|Pr _xgets D_n[A(x)=1]-Pr _xgets E_n[A(x)=1]right|.](https://wikimedia.org/api/rest_v1/media/math/render/svg/b99a343c7928f598b4ca610241e0492bb2c56781)
denoted Dn≈Endisplaystyle D_napprox 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 nto 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, Adisplaystyle 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.[2]:108
References
^ Lecture 4 - Computational Indistinguishability, Pseudorandom Generators
^ ab Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press.
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.
Algorithmic information theoryUncategorized
