# Computational indistinguishability

(Redirected from Computationally indistinguishable)
Jump to: navigation, search

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 (which usually refers to the length of the input), then 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:

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

denoted $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\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.

Implicit in the definition is the condition that the algorithm, $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. It turns out that if the polynomial-time algorithm can generate samples in polynomial time, or has access to random oracle that generates samples for it, then indistinguishable by polynomial-time sampling is equivalent to computational indistinguishability[2]:108.

## References

1. ^ Lecture 4 - Computational Indistinguishability, Pseudorandom Generators
2. ^ a b Goldreich, O. (2003). Foundations of cryptography. Cambridge, UK: Cambridge University Press.