3
$\begingroup$

Statistical closeness implies computational indistinguishability.

Is there any (simple) relationship between negligible function that is used in definition of statistical closeness and negligible function that is used in definition of computational indistinguishability?

Can we say anything about the negligible function used in computational indistinguishability if we know how the negligible function in definition of statistical closeness looks like?

What about the special case: negligible function in definition of statistical closeness is zero?


Definitions from Goldreich, Foundations of Cryptography:

Ensemble = sequence of random variables, $\{X_i\}_{i \in \mathbb{N}}$

Computational indistinguishability:

Two ensembles $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ are computationally indistinguishable if for every probabilistic polynomial-time algorithm $D$, every positive polynomial $p$ and all sufficiently large $n$'s,

$ |P(D(X_n) = 1) - P(D(Y_n) = 1)| < \frac{1}{p(n)}. $

(this definition actually says that $|P(D(X_n) = 1) - P(D(Y_n) = 1)|$ is negligible function in $n$)

Statistical closeness:

Ensembles $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ are statistically close if their statistical difference $\triangle(n)$ is negligible.

$ \triangle(n) = \frac{1}{2} \sum_a |P(X_n = a) - P(Y_n = a)| $

$\endgroup$
3
$\begingroup$

Statistical distance between $X_n$ and $Y_n$ can be defined as the maximum, over all functions $D$, of $$ |P(D(X_n) = 1) - P(D(Y_n) = 1)|. $$

In particular, if the statistical distance between two sequences of distributions $\{X_i\}_{i \in \mathbb{N}}$ and $\{Y_i\}_{i \in \mathbb{N}}$ is negligible (eventually smaller than $1/p(n)$ for any polynomial $n$) then they are computationally indistinguishable. The other direction is not true, and this is what drives all of cryptography.

I leave it an exercise to show that if two sequences distributions have zero statistical distance (i.e., they are copies of the same random variables) then they are computationally indistinguishable.

$\endgroup$
  • $\begingroup$ I'm not sure this answers my question. $X_i$ are random variables, not distributions. If $X$ and $Y$ are distributions, then this inequality $\triangle (f(X), f(Y)) \leq \triangle (X, Y)$ holds for every probabilistic algorithm. However, I would like to have something similar for random variables. And $D$ is not function. $D$ is probabilistic algorithm and it can use random variables which are not independent from $X_i$ and $Y_i$. $\endgroup$ – Student20 Jul 22 '16 at 20:34
  • $\begingroup$ On the contrary, $D$ in the definition of statistical distance is an arbitrary function. It is a particular type of function only in the definition of computational indistinguishability. This is the point of the latter definition – it is the same as statistical distance, but for computationally bounded distinguishers. $\endgroup$ – Yuval Filmus Jul 22 '16 at 20:43
  • $\begingroup$ Any reference for definition of statistical distance that you're using? I'm probably missing something, but what about the following "counterexample". Assume $X$ and $Y$ are independent random variables, with uniform distribution over some set $S$. According to my definition of statistical distance the statistical distance between $X$ and $Y$ is 0. Define probabilistic algorithm $D(x) = \text{if $X=x$ return 1, otherwise return 0}$. Then $D(X)$ always returns 1, but $D(Y)$ doesn't. Statistical distance according to your definition is not 0. $\endgroup$ – Student20 Jul 22 '16 at 20:59
  • $\begingroup$ Your algorithm $D$ doesn't get access to $X$. It gets access to its input, and is allowed to be random, though the best algorithm is always deterministic, as a simple averaging argument shows. $\endgroup$ – Yuval Filmus Jul 22 '16 at 21:03
  • $\begingroup$ Why $D$ doesn't get access to $X$? $D$ can be thought as an deterministic algorithm that uses random tape $\omega$ as its extra argument. If random tape $\omega$ contains values for $X$ in $Y$, then $D$ can have access to $X$. I remember this logic from some papers. $\endgroup$ – Student20 Jul 22 '16 at 21:08

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.