Computational indistinguishability for any distribution using a Chernoff bound

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)$$?

1 Answer

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$$.