patternMinor
Negligible functions in definitions of statistical closeness and computational indistinguishability
Viewed 0 times
negligiblecomputationalstatisticalclosenessandfunctionsindistinguishabilitydefinitions
Problem
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)|
$
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)|
$
Solution
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.
$$ |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.
Context
StackExchange Computer Science Q#60867, answer score: 3
Revisions (0)
No revisions yet.