$$

We show the intuitive fact: “if you can distinguish something from random, you can guess it better than random chance”.

Let $b:{\{\pm 1\}}^n\to \{\pm 1\}$ be some supposedly hard function. If there is an algorithm $A$ that, knowing $x$, can distinguish $b(x)$ from a random bit with some advantage, then there is some algorithm $A^{\prime }$ that guesses $b(x)$ from $x$ with better than random chance. More precisely, if

$$|\underset{x\in {\{\pm 1\}}^n}{\mathrm{Pr}}[A(x,b(x))=1]-\underset{x\in {\{\pm 1\}}^n,b^{\prime }\in \{\pm 1\}}{\mathrm{Pr}}[A(x,b^{\prime })=1]|\ge ϵ,$$

then $max(|\mathrm{E}[A(x,1)\cdot b(x)]|,|\mathrm{E}[A(x,-1)\cdot b(x)]|)\ge 2ϵ$: that is, either $A^{\prime }(x):=A(x,1)$ or $A^{\prime }(x):=A(x,-1)$ has a correlation of at least $2ϵ$ with $b(x)$.

This trick is useful when proving the existence of pseudorandom generators from hard-core bits: it shows that if some $b(x)$ is hard to guess (in the sense that no fast algorithm correlates with it much), then $b(x)$ must look random to any fast algorithm that knows only $x$.

Note that depending on the context, we might only want to give $A$ restricted access to $x$. In this case, we can replace $A(x,\cdot )$ by $A(f(x),\cdot )$ for some function $f$, and $A^{\prime }$ becomes either $A(f(x),1)$ or $A(f(x),-1)$.

Proof

We will show that, in fact,

$$\mathrm{Pr}[A(x,b(x))=1]-\mathrm{Pr}[A(x,b^{\prime })=1]=\frac{\mathrm{E}[A(x,1)\cdot b(x)]-\mathrm{E}[A(x,-1)\cdot b(x)]}{4}.$$

So if the absolute value of the LHS is at least $ϵ$, then at least one of the terms in the RHS has to have absolute value $\ge 2ϵ$.

First,

$$\begin{array}{rl}\mathrm{Pr}[A(f(x),b(x))=1]-\mathrm{Pr}[A(f(x),b^{\prime })=1]& =\frac{\mathrm{E}[A(f(x),b(x))]-\mathrm{E}[A(f(x),b^{\prime })]}{2}\\ & =\frac{\mathrm{E}[A(f(x),b(x))]-\frac{\mathrm{E}[A(f(x),b(x))]+\mathrm{E}[A(f(x),-b(x))]}{2}}{2}\\ & =\frac{\mathrm{E}[A(f(x),b(x))]-\mathrm{E}[A(f(x),-b(x))]}{4}.\end{array}$$

Then, we can observe that

$$\begin{array}{rl}\mathrm{E}[A(f(x),b(x))]-\mathrm{E}[A(f(x),-b(x))]& =\mathrm{E}[A(f(x),b(x))-A(f(x),-b(x))]\\ & =\mathrm{E}[A(f(x),1)\cdot b(x)-A(f(x),-1)\cdot b(x)]\\ & =\mathrm{E}[A(f(x),1)\cdot b(x)]-\mathrm{E}[A(f(x),-1)\cdot b(x)]\end{array}$$

where the second equality holds pointwise (just check both possible values of $b(x)$).