4
$\begingroup$

The statistical difference between two families of distributions of random variables:

Let $\mathrm{\mathbf{X}} = \{ X_{l} \}_{l}$ and $\mathrm{\mathbf{Y}} = \{ Y_{l} \}_{l}$ be two families of distributions of random variables, the statistical difference of $\mathrm{\mathbf{X}}$ and $\mathrm{\mathbf{Y}}$ is defined as $$d^{\mathrm{\mathbf{X}}, \mathrm{\mathbf{Y}}} ( l )= \frac{1}{2}\sum_{s} \left\vert \Pr[X_{l} = s] - \Pr[Y_{l} = s] \right\vert$$

The computational difference between two families of distributions of random variables:

Let $\mathrm{\mathbf{X}} = \{ X_{l} \}_{l}$ and $\mathrm{\mathbf{Y}} = \{ Y_{l} \}_{l}$ be two families of distributions of random variables, for any PPT algorithm $A$, the computational difference of $\mathrm{\mathbf{X}}$ and $\mathrm{\mathbf{Y}}$ is defined as $$d^{\mathrm{\mathbf{X}}, \mathrm{\mathbf{Y}}}_{A} ( l )=\left\vert \Pr[s \leftarrow X_{l} : A \left( 1^{l}, s \right) = 1] - \Pr[s \leftarrow Y_{l} : A \left( 1^{l}, s \right) = 1] \right\vert$$

This notion can be used to define the PRGs.

The computational difference between two families of distributions of functions:

Let $\mathrm{\mathbf{F}} = \{ F_{l} \}_{l}$ and $\mathrm{\mathbf{G}} = \{ G_{l} \}_{l}$ be two families of distributions of functions, for any PPT algorithm $A$, the computational difference of $\mathrm{\mathbf{F}}$ and $\mathrm{\mathbf{G}}$ is defined as $$d^{\mathrm{\mathbf{F}}, \mathrm{\mathbf{G}}}_{A} ( l )= \left\vert \Pr[f \leftarrow F_{l} : A^{f(\cdot)} \left( 1^{l} \right) = 1] - \Pr[g \leftarrow G_{l} : A^{g(\cdot)} \left( 1^{l} \right) = 1] \right\vert$$

This notion can be used to define the PRFs.

I am thinking that there should be a definition about the statistical difference between two families of distributions of functions. (It is denoted as $d^{\mathrm{\mathbf{F}}, \mathrm{\mathbf{G}}} ( l )$).

There is a possible way:

For every input $x \in \{\ 0,1 \,\}^{*}$, let $F_{l} \left( x \right)$ denotes the distribution of $f(x)$ where $f \leftarrow F_{l}$. Maybe one can use $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (\cdot)$ to define the statistical difference between $\mathrm{\mathbf{F}}$ and $\mathrm{\mathbf{G}}$, where $\mathrm{\mathbf{F}}(x) = \{ F_{l}(x) \}_{l}$ and $\mathrm{\mathbf{G}}(x) = \{ G_{l}(x) \}_{l}$.

However, $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (l)$ depends on both $x$ and $l$. Thus, there exists a problem, $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (l)$ may not be consistency for $x$. If I define $$d^{\mathrm{\mathbf{F}},\mathrm{\mathbf{G}}} (l) =\sup_{x \in \{\, 0,1 \,\}^{*}} d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (l) =\sup_{x \in \{\, 0,1 \,\}^{*}}\frac{1}{2}\sum_{s} \left\vert \Pr[F_{l}(x) = s] - \Pr[G_{l}(x) = s] \right\vert$$ Then $d^{\mathrm{\mathbf{F}},\mathrm{\mathbf{G}}} (\cdot)$ may be not negligible even if for every $x$, $d^{\mathrm{\mathbf{F}}(x),\mathrm{\mathbf{G}}(x)} (\cdot)$ is negligible.

$\endgroup$
3
  • $\begingroup$ I think your definition of statistical distance is missing a factor of $1/2$. $\endgroup$
    – Daniel
    Nov 15 '18 at 12:24
  • $\begingroup$ @ Daniel, you are right, let me correct. I thought the factor does not important here. $\endgroup$
    – Blanco
    Nov 16 '18 at 1:49
  • $\begingroup$ The space of functions with a finite domain is a finite space itself, so you don't need to invent any additional concepts for statistical distance. $\endgroup$ Apr 25 '19 at 13:16
1
$\begingroup$

It can be seen that statistical difference is equivalent to computational difference if a PPT algorithm is replaced by a computationally unbounded one, i.e. an arbitrary function. For distributions of random variables, if $A(1^l,s)=1$ when $\Pr[X_l=s]>\Pr[Y_l=s]$ and $A(1^l,s)=0$ otherwise, then $d_A^{\mathbf X,\mathbf Y}(l)=d^{\mathbf X,\mathbf Y}(l)$, and this is the maximum for any $A$.

For functions, a similar argument can be used: a computationally unbounded algorithm can return $1$ on an arbitrary subset of functions, so it seems that the best choice would be to return $1$ for such $f$ that $\Pr[F_l=f]>\Pr[G_l=f]$. Then, $$d^{\mathbf F,\mathbf G}(l)=d_A^{\mathbf F,\mathbf G}(l)=\frac12\sum\limits_f\lvert\Pr[F_l=f]-\Pr[G_l=f]\rvert.$$ Here, the sum is taken over all possible functions. This sum well-defined, because all summands are nonnegative.

$\endgroup$
2
  • $\begingroup$ You are right, but I think it is too weak. There exist $\mathrm{\mathbf{F}}$ and $\mathrm{\mathbf{G}}$ such that $d^{\mathrm{\mathbf{F}}, \mathrm{\mathbf{G}}}(l)=1$ even though they are computational indistinguishable. $\endgroup$
    – Blanco
    Nov 19 '18 at 5:48
  • $\begingroup$ @TeamBright The same is true for random variables (assuming "computationally indistinguishable" means that computational difference is negligible for any PPT algorithm). This is the difference between statistical difference and computational difference. $\endgroup$ Nov 19 '18 at 15:03

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.