Computational indistinguishability for any distribution using a Chernoff bound

Question

I had a question about a general statement regarding finding a computationally indistinguishable distribution given any distribution, observed (in the third paragraph of Section 11, page 31) here. This is the statement:

For any distribution $D$ over $\{0,1\}^{n}$, there exists a distribution $D'$ such that $D$ and $D'$ are $\epsilon$ indistinguishable with respect to any classical distinguisher of size $n^{k}$.

Let me restate the proof.

Let $D$ be any distribution over $\{0,1\}^{n}$. Then choose $w$ elements independently with replacement from $D$, and let $D′$ be the uniform distribution over the resulting multiset (so in particular, $H(D′) \leq \log_{2} n$). Certainly $D′$ can be sampled by a circuit of size $\mathcal{O}(nw)$: just hardwire the elements. Now, by a Chernoff bound, for any fixed circuit $C$, clearly $D$ and $D′$ are $\epsilon$-indistinguishable with respect to $C$, with probability at least $1 − e^{-\epsilon^{2} w}$ over the choice of $D′$. But there are “only” $n^{\mathcal{O}(n^{k})}$ Boolean circuits of size at most $n^k$. So by the union bound, by simply choosing $w = \Omega\left(\frac{n^{k} \log n}{\epsilon^2}\right)$, we can ensure that $D$ and $D′$ are $ε$-indistinguishable with respect to all circuits of size at most $n^{k}$, with high probability over $D′$.

I do not understand how the Chernoff bound is applied. How do we know the action of the circuit $C$? I also don't understand why $w = \Omega\left(\frac{n^{k} \log n}{\epsilon^2}\right)$ in the union bound. Since we need to "protect against" $n^{\mathcal{O}(n^{k})}$ Boolean circuits, shouldn't $w$ be something like $w = \Omega\left(\frac{n^{\mathcal{O}(n^k)} \log n}{\epsilon^2}\right)$?

Answer 1

How the Chernoff bound is applied

What does it mean for $D$ and $D'$ to be indistignuishable by a circuit $C$? It means that $$ |\Pr_{x \in D}[C(x) = 1] - \Pr_{x \in D'}[C(x) = 1]| \leq \epsilon. $$ Let $x_1,\ldots,x_w$ be the sampled elements. Then $$ \Pr_{x \in D'}[C(x) = 1] = \frac{X_1 + \cdots + X_w}{w}, $$ where $X_i$ is the indicator of $C(x_i) = 1$. If we sample $x_1,\ldots,x_w$ at random, then $X_1,\ldots,X_w$ are independent Bernoulli random variables whose expectation is $\Pr_{x \in D}[C(x) = 1]$. Chernoff's bound shows that their average is concentrated around their expectation.

Applying the union bound

The probability that a choice of $x_1,\ldots,x_w$ is bad for a specific circuit $C$ is $e^{-\epsilon^2 w}$. The probability that a choice of $x_1,\ldots,x_w$ is bad for one of $N$ different circuits is at most $Ne^{-\epsilon^2 w}$. Hence if $Ne^{-\epsilon^2 w} < 1$, the probability that a choice of $x_1,\ldots,x_w$ is good to all $N$ circuits is positive, hence there exists such a choice which is good to all $N$ circuits.

Since $w$ is in the exponent, the minimal $w$ needed to satisfy $Ne^{-\epsilon^2 w} < 1$ scales only logarithmically in $N$.