PRG ⇒ Average-case hardness of NP

Free reduction · standard model · folklore · security loss: one call to the algorithm: error $\delta$ under the sampler gives PRG advantage at least $1/2-2\delta$

Statement

If a PRG $G:\mathcal{S}\to \mathcal{R}$ with $|\mathcal{R}|\ge 2|\mathcal{S}|$ exists, as for seeds and outputs that are bit strings, $\mathbf{NP}$ is hard on average over samplable distributions: the language $L=\{(1^{\lambda },r):\exists s\in \mathcal{S},G(s)=r\}$ is in $\mathbf{NP}$, and under the sampler $D(1^{\lambda })$ that outputs $(1^{\lambda },G(s))$ for $s\stackrel{\$}{\leftarrow }\mathcal{S}$ or $(1^{\lambda },r)$ for $r\stackrel{\$}{\leftarrow }\mathcal{R}$, each with probability $1/2$, every efficient algorithm errs with probability at least $1/4-\mathrm{negl}(\lambda )$, so the definition holds with $p=5$ — folklore.

Sketch

Let $\mathcal{A}$ err with probability $e_0$ on $G(s)$ and $e_1$ on uniform $r$, so its error under $D$ is $\delta =(e_0+e_1)/2$. Since $|\mathcal{R}|\ge 2|\mathcal{S}|$, a uniform $r$ lies in $L$ with probability at most $1/2$, so $\mathrm{Pr}[\mathcal{A}(1^{\lambda },r)=1]\le 1/2+e_1$, while $\mathrm{Pr}[\mathcal{A}(1^{\lambda },G(s))=1]=1-e_0$. The distinguisher $\mathcal{B}$ that outputs $b^{\prime }=0$ exactly when $\mathcal{A}$ accepts therefore has ${\mathbf{Adv}}_{G,\mathcal{B}}^{\mathrm{prg}}(\lambda )\ge 1/2-2\delta$, so $\delta \ge 1/4-{\mathbf{Adv}}_{G,\mathcal{B}}^{\mathrm{prg}}(\lambda )/2$.

Notes

• With OWF ⇒ PRG — HILL99, one-way functions make $\mathbf{NP}$ hard on average over a samplable distribution, so neither Algorithmica nor Heuristica, Impagliazzo’s worlds in which $\mathbf{NP}$ is easy on average over samplable distributions, has one-way functions — Imp95.