Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. We are not given an explicit description of $D$: we are only given black-box access, ie, we are only given a sampling device that can sample from $D$. Consider a sample $z \in \{0, 1\}^{n}$, taken from either $D$ or $U$. We want to know which one is the case, and to do that, we consider polynomial-time algorithms that use the sampling device.

Let the best distinguisher algorithm use the black-box sampling device a polynomial number of times (at most) and get samples $z_{1}, z_{2}, \ldots, z_{k}$ from $D$, for some polynomial $k$. My intuition is that, if this best algorithm decides that $z$ indeed came from $D$, then it must be true that $z_{i} = z$ for at least one $i \in [k]$. In other words, since we know nothing about $D$ or its support, we have to "see" $z$ at least once in the samples we collect from $D$ to ascertain that $z$ indeed came from $D$. How do I mathematically formalize this statement?

Also, does this same intuition hold if we are given a polynomial number of samples as input (taken from either $D$ or $U$) instead of just one and are also given access to a black-box sampler for $D$?


1 Answer 1


You can't. Your intuition is wrong. I will give an explicit counter-example. Actually, I'll give you two: two for the price of one.

Suppose $n=1$, the distribution $D$ always outputs 1, and $U$ is uniform on $\{0,1\}$. The following algorithm is an optimal distinguisher:

  • Never use the black box. If the input $z$ is 0, guess that it came from $U$, otherwise guess that $z$ came from $D$.

Suppose we run this algorithm on an input $z$ and it guesses that $z$ came from $D$. Then it's not true that $z$ must be equal to one of the queries to the black box; the algorithm didn't make any queries to the black box.

If you're not happy with that, you can obtain another explicit counterexample by considering the following algorithm, with $U$ being the uniform distribution and $D$ a distribution that outputs $1$ with probability $3/4$ and $0$ with probability $1/4$:

  • If the input $z$ is 0, get a sample $z_1$ from the black box, ignore $z_1$, and guess that $z$ came from $U$.
  • Otherwise, get a sample $z_1$ from the black box, ignore $z_1$, and guess that $z$ came from $D$.

Notice that if this algorithm guesses that $z$ came from $D$, it is not necessarily true that $z=z_1$ (it can happen that $z=1$ but $z_1=0$), so your claim is not true about this algorithm either; yet this algorithm is an optimal distinguisher.

It's often useful to test your intuition on some simple examples.

I suspect what you're missing is that the adversary is assumed to know the distributions $D,U$ in advance and then choose an algorithm based on knowledge of $D,U$ -- a different distinguisher algorithm for each different $D$. There's no requirement to choose a single algorithm that works for all $D,U$.

  • $\begingroup$ I still don't follow. The distribution $D$ always outputs $1$. What does it mean to say "make a query $z_{1}=0$"? $\endgroup$
    – Sid Meier
    Commented Nov 21, 2020 at 9:21
  • $\begingroup$ @BlackHat18, you're right, the second example was buggy. See revised answer, where I have fixed the bug; now the second example should be valid. The first example remains valid. All it takes is one counterexample to disprove a statement. $\endgroup$
    – D.W.
    Commented Nov 21, 2020 at 18:26
  • $\begingroup$ What if we don't have prior knowledge of $D$? That is what I had in mind when I asked - a single algorithm that works on all distributions with high probability. $\endgroup$
    – Sid Meier
    Commented Nov 21, 2020 at 18:50
  • $\begingroup$ If we are talking about a single optimal algorithm that work for all distributions, the counterexamples do not work right? For simplicity, assume that the distributions $D$ and $U$ are far apart. $\endgroup$
    – Sid Meier
    Commented Nov 21, 2020 at 18:58
  • $\begingroup$ @BlackHat18, Perhaps it would be best to ask a new question where you include that information? Make sure to define what "optimal" means in that context. It's important to make sure the problem statement and requirements are clear from the start so people are answering the question that you want answered. $\endgroup$
    – D.W.
    Commented Nov 21, 2020 at 19:24

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.