I have not seen this anywhere 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 $R \subset S \times S$. The three properties are

• reflexive: $\forall x \in S$ then $(x,x) \in R$
• symmetric: $\forall x,y \in S$ and then $(x,y) \in R$, if and only if $(y,x) \in R$
• transitive: $\forall x,y,z \in S$ and $(x,y)$ and $(y,z) \in R$ then $(x,z) \in R$

We say a function $\mu(n): \mathbb{N} \rightarrow \mathbb{N}$ is negligible if $\mu(n) < 1/\text{poly}(n)$, where $\text{poly}(n)$ is the set of all polynomials. What this is saying is that for $\mu(n)$ to be negligible, it must not only converge to zero, but it must do so faster than the reciprocal of any polynomial.

If $\mu(n)$ is negligible, then there is some smallest degree $d$ and largest polynomial $n^{-d}$ such that $\mu(n) < n^{-d}$. If $\mu_1(n), \mu_2(n)$ are both negligible, then there exist $d_1,d_2$ 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 written $\{X(a,n)\}$ is an infinite sequences of random variables, indexed by strings $a$ and integers $n$.

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

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

Is it reflexive?

which is true! Is it symmetric?

So it is! Is it transitive? Given $X \approx Y$, and $Y \approx Z$ 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.