Computational indistinguishability with Example

Question

Based on computational indistinguishability definition no PPT algorithm can distinguish $X$ from $Y$, where $X=\{X_n\}_{n \in N}$ and $Y=\{Y_n\}_{n \in N}$ are ensembles of probability distributions and $X_n$, $Y_n$ are probability distributions over $\{0,1\}^{p(n)}$ for some polynomial $p(.)$.

The above definition is not clear to me. Can anyone explain that with a clear example (e.g. roll a die or flip a coin). As the examples for the pevious posts about the same topic are not very clear.

Side note: I believe there is a lack of clear explanation and examples in the literature about this topic. So any good example would help the other learners too!

Answer 1

For any $n \in \mathbf{N}$, let $X_n$ be a random variable which always equals $n$, and $Y_n$ be a random variable which equals $n$ or $n+1$ each with probability $1/2$. Then the probability ensembles $X = \{X_n\}_{n\in \mathbf{N}}$ and $Y = \{Y_n\}_{n\in \mathbf{N}}$ are not computationally indisinguishable. A possible distinguisher is an algorithm $D$ which, on input $(y, 1^n)$, outputs $1$ if $y = n$ and $0$ otherwise. We then have $\mathsf{Pr}[D(X_n, 1^n) = 1] = 1$ for all $n$ because $X_n$ always equals $n$. On the other hand, we have $\mathsf{Pr}[D(Y_n, 1^n) = 1] = 1/2$, hence $$\left| \mathsf{Pr}\left[D\left(X_n, 1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n, 1^n\right) = 1\right]\right| = \frac{1}{2},$$ which is constant and thus not negligible. I can't think of any simple example of probability ensembles which are computationally indistinguishable, except trivially if they are identical or just assumed to be indistinguishable. Indeed, constructing probability ensembles which are non-trivially computationally indistinguishable is in a way what cryptography is all about...

---

Actually, here's an example (although it could reasonably be considered trivial as well). As above, $X_n$ always equals $1^n$. $Y_n$ is the output of the following algorithm on input $1^n$:

1. Throw $n$ coins.
2. If the coins are all $0$, output $0^n$. Otherwise output $1^n$.

Thus $Y_n$ equals $0^n$ with probability $2^{-n}$ and $1^n$ with probability $1-2^{-n}$. I claim that they are computationally indistinguishable. Intuitively, $X_n$ and $Y_n$ are identical except when $Y_n = 0^n$, but because this happens with negligible probability, no algorithm is able to distinguish them with non-negligible probability. (Note that this applies to all algorithms, not just PPT ones.)

Let $D$ be any algorithm, we want to estimate $$\left|\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right]\right|.$$ We remark that, conditioned on $Y_n \ne 0^n$, $(X_n,1^n)$ and $(Y_n,1^n)$ are identically distributed: they always equal $(1^n,1^n)$. Hence, $$\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\middle|Y_n \ne 0^n\right] = \mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right].$$ Using this, we obtain $$ \begin{align*} \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right] &= \underbrace{\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n = 0^n\right]}_{\ge 0} + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\ &\ge \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\ &\ge \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \middle| Y_n \ne 0^n\right] \cdot \mathsf{Pr}\left[Y_n \ne 0^n\right] \\ &\ge \mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] \cdot \left(1-2^{-n}\right), \\ \end{align*} $$ hence $$\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right] \le \underbrace{\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right]}_{\le 1}\cdot 2^{-n} \le 2^{-n}.$$ On the other hand, $$ \begin{align*} \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right] &= \underbrace{\mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n = 0^n\right]}_{\le \mathsf{Pr}\left[Y_n = 0^n\right]} + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\ &\le \mathsf{Pr}\left[Y_n = 0^n\right] + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \wedge Y_n \ne 0^n\right] \\ &\le \mathsf{Pr}\left[Y_n = 0^n\right] + \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1 \middle| Y_n \ne 0^n\right] \cdot \mathsf{Pr}\left[Y_n \ne 0^n\right] \\ &\le 2^{-n} + \mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] \cdot \left(1-2^{-n}\right), \\ \end{align*} $$ hence $$\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right] - \mathsf{Pr}\left[D\left(Y_n,1^n\right) = 1\right] \ge \underbrace{\mathsf{Pr}\left[D\left(X_n,1^n\right) = 1\right]}_{\ge 0}\cdot 2^{-n} - 2^{-n} \ge -2^{-n}.$$

(For those studying the book of Katz-Lindell, this is similar to Exercise 7.1.)