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


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.