Computational indistinguishability

From Wikipedia, the free encyclopedia

 This article does not cite any references or sources. (December 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

In computational complexity, if \scriptstyle\{ D_n \}_{n \in \mathbb{N}} and \scriptstyle\{ E_n \}_{n \in \mathbb{N}} are two distribution ensembles indexed by a security parameter n, then we say they are computationally indistinguishable if for any nonuniform probabilistic polynomial time algorithm A, the following quantity is a negligible function in n:

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

In other words, for every efficient algorithm A, its behavior does not significantly change when given samples according to Dn or En.

This article incorporates material from computationally indistinguishable on PlanetMath, which is licensed under the GFDL.

 This mathematics-related article is a stub. You can help Wikipedia by expanding it.
 This cryptography-related article is a stub. You can help Wikipedia by expanding it.