Computational indistinguishability is a relation between indexed families of statistical distributions that formalizes indistinguishability by efficient randomized
algorithms. Let 
and 
be statistical distributions
on strings, indexed by 
in an infinite set 
of binary strings, and let 
be the length of 
. For a test 
running in polynomial time
in 
,
define its distinguishing advantage by
![delta_D(x)=|Pr[D(x,X_x)=1]-Pr[D(x,Y_x)=1]|.](/images/equations/ComputationalIndistinguishability/NumberedEquation1.svg) |
Each probability includes the sampled string and the test's randomness. The families are computationally indistinguishable iff, for every such test 
and every constant 
, the bound 
holds for all sufficiently long 
(Goldwasser et al. 1989, Goldreich et al. 1991).
The total variation distance bounds the distinguishing advantage of every test, regardless of its computation time. Computational indistinguishability restricts attention to efficient tests. In a zero-knowledge proof, the compared statistical distributions are a verifier's view and a simulated view.
