I have not seen this much in other sources so I thought I would write it up. It is actually not that important. Usually people only care about transitivity.

An equivalence relation is a relation on a set that has three properties. Colloquially, it is supposed to be like “equals”. You can think of a relation as a subset . The three properties are

  • reflexive: then
  • symmetric: and then , if and only if
  • transitive: and and then

We say a function is negligible if , where is the set of all polynomials. What this is saying is that for to be negligible, it must not only converge to zero, but it must do so faster than the reciprocal of any polynomial.

If is negligible, then there is some smallest degree and largest polynomial such that . If are both negligible, then there exist such that \begin{equation} \mu_1(n) + \mu_2(n) < n^{-d_1} + n^{-d_2} < n^{\min(d_1,d_2) - 1} \end{equation} This shows that the sum of two negligible functions must be negligible. This will help us prove transitivity later on.

A probability ensemble indexed by strings and integers . They are infinite sequences of random variables.

Given two probability ensembles, and , we say that is computationally indistinguishable from (written ) if for all non-uniform polynomial time distinguishers , every and large enough , there exists a negligible function such that

\begin{equation} |Pr[D(X(a,n)) = 1] - Pr[D(Y(a,n)) = 1]| < \mu(n) \end{equation} Here is any kind of algorithm, in an attempt to tell apart and . Now we show that is an equivalence relation.

Is it reflexive?

which is true! Is it symmetric?

So it is! Is it transitive? Given , and then

where the second step follows from the triangle inequality, and the third step from the fact that a sum of negligible functions is also negligible, which is something we proved earlier. From this we see it is also transitive.

Since computational indistinguishability has satisfied our three properties, we know it is an equivalence relation.