Editing Computational indistinguishability (section)

==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.