Computational indistinguishability
From CRYPTUTOR
←Older revision | Newer revision→
Two (ensembles of) probability distributions are computationally indistinguishable if no efficient computation shows significantly different behavior when provided inputs sampled according to one distribution or the other.
Definition
Two ensembles of probability distributions, 
and 
, indexed by a security parameter 
, are said to be computationally indistinguishable if for all non-uniform PPT machines A, the following difference is negligible (in k):
![\Pr_{x\leftarrow \mathcal{T}_k}[A(x)=1] - \Pr_{x\leftarrow \mathcal{V}_k}[A(x)=1]](/wiki/images/uploaded/math/5/5/e/55e61f6093e2d45157ade777dd55170e.png)
.
A weaker variant of this definition is to consider only uniform adversaries.
The distributions 
and 
are generally over 
for some polynomial 
. When the ensembles and security parameter are understood, we often state that and are computationally indistinguishable.
Transitivity
Computational indistinguishability is transitive when applied on a polynomial (in the security parameter) sequence of distributions.
Suppose the distribution ensembles 
and 
are computationally indistinguishable, for 
, where t is a polynomial. Then the extreme distributions 
and 
are also computationally indistinguishable.
This is true because if the two extreme distributions could be distinguished with probability 
, then by the pigeonhole principle, some adjacent pair of distributions could be distinguished with probability at least 
. By our assumption about adjacent pairs of distributions, this probability is negligible in k. Since a polynomial times a negligible function remains negligible, is negligible.
This transitivity property a fact commonly used in proofs which use a hybrid argument.
Pseudorandom Distribution
An ensemble of distributions over is said to be pseudorandom if it is computationally indistinguishable from the uniform distribution over .
As above, when the ensemble and security parameter are understood, we often state that is a pseudorandom distribution.
