1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Can you define what a PPT algorithm is? $\endgroup$ – kodlu May 17 '15 at 6:44
  • $\begingroup$ @kodlu That's probabilistic polynomial-time. $\endgroup$ – Vadym Fedyukovych May 17 '15 at 9:21
7
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ First off, thanks for the answer. I'm wondering whether the follwong statement is correct. Let $X_n$ and $Y_n$ be two random variables that can take on any value,$v_n$ where $0 \leq v_n \leq n$, then the probability ensembels $X=\{X_n\}_{n \in N}$ and $Y=\{Y_n\}_{n \in N}$ are computationally indistinguishable. $\endgroup$ – user153465 May 17 '15 at 13:50
  • 1
    $\begingroup$ You have not specified the probability distributions of $X_n$ and $Y_n$. If they are both uniformly distributed, then yes, the probability ensembles are trivially indistinguishable, since they are identical. $\endgroup$ – fkraiem May 17 '15 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.