1
$\begingroup$

In constructing a SHVZK simulator for a sigma protocol I am working on I have encountered some fairly basic questions, but ones which are not often discussed in textbooks and papers - consider the two following probability distributions:

  1. $X_n$ - The uniform distribution on $\{1, \dots n\}=[n]$
  2. $Y_n$ - The uniform distribution on $[n] \backslash \{a\}$, for some fixed integer $a \in [n]$.

The distributions are not perfectly indistinguishable because an unbounded distinguisher could keep sampling elements from each distribution until it is clear which element is missing from the second distribution.

The distributions are statistically indistinguishable with statistical distance \begin{align*} \Delta(X_n,Y_n) &= \frac{1}{2}\sum_{x \in [n]}{|\Pr[X_n=x] - \Pr[Y_n = x] |} \\ &= \frac{1}{2}(\sum_{x \in [n]\backslash\{a\}}{\bigg|\frac{1}{n} - \frac{1}{n-1}\bigg|}) + \frac{1}{2}(\frac{1}{n} - 0)\\ &= \frac{1}{2}(n-1)\frac{1}{n(n-1)} + \frac{1}{2n}\\ &= \frac{1}{n} \end{align*} If $n = \exp(\lambda)$, the distributions are statistically indistinguishable since $\frac{1}{\exp(\lambda)} \leq \text{negl}(\lambda)$.

Now, the question, which I feel I've somewhat answered already (see answer below), but was not that clear to me from my readings:

Q: Intuitively, I've heard statistical indistinguishability been described as the following: "An unbounded distinguisher cannot distinguish the two distributions" (For example, this post), but this seems false in the example above?

$\endgroup$

1 Answer 1

1
$\begingroup$

Statistical indistinguishability implies computational indistinguishability, and in fact this describes a tight upper bound on any distinguishers advantage, unbounded or not. So a distinguisher may distinguish the two probabilities with an advantage at most the statistical distance of the two distributions. (See here)

Hence the claim that an unbounded distinguisher cannot distinguish the two distributions is incomplete. What this really means is that an unbounded distinguisher cannot distinguish the two distributions with more than a neglible advantage.

I appreciate any thoughts or corrections to this post!

$\endgroup$
3
  • 2
    $\begingroup$ This is correct! "Cannot" usually implies "with more than a negligible advantage". Note that an unbounded receiver gets a sample from either distribution, but this does not mean that they can keep sampling from the distribution: they have unbounded runtime given a single sample. $\endgroup$ Sep 5, 2023 at 9:56
  • $\begingroup$ I see, but you also need to consider a distinguisher that knows the probability distributions, correct? So for example, if you removed all but one element from the uniform distribution on $[n]$, then the distributions are not statistically indistinguishable, and a distinguisher's strategy would need to know which element is not removed the sample space. $\endgroup$
    – Lev
    Sep 5, 2023 at 21:38
  • 1
    $\begingroup$ Yes, but this is implied by the standard definition: "two distributions are indistinguishable if for every PPT/unbounded adversary...". Here, since we consider all (PPT or unbounded) adversaries, we have to consider in particular those who have arbitrary information about the distributions hard-coded. $\endgroup$ Sep 6, 2023 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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