Zero-bit PRC ⇒ Trapdoor pseudorandom generators

Standard model · folklore

Statement

A zero-bit PRC $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ is a pseudorandom trapdoor PRG with the PRC key as trapdoor $t$, the encoder’s coins as key $k$, $\mathsf{Eval}(t,k)$ running ${\mathsf{Enc}}_t$ on coins $k$, and $\mathsf{Invert}(t,r)=[{\mathsf{Dec}}_t(r)\ne \perp ]$. It is $(1-\nu )$-complete and $(1-\nu )$-sound for a negligible $\nu$, and if the PRC is $\epsilon$-robust, $\mathrm{Pr}[\mathsf{Invert}(t,\mathcal{E}(\mathsf{Eval}(t,k)))=1]\ge 1-\nu$ for every $\epsilon$-bounded channel $\mathcal{E}$ — folklore.

Sketch

The trapdoor-PRG oracle ${\mathcal{O}}_t$ is exactly ${\mathsf{Enc}}_t$, so PRC pseudorandomness gives pseudorandomness, and robustness (at zero noise, or against the channel) gives completeness. PRC soundness bounds ${\mathrm{Pr}}_t[{\mathsf{Dec}}_t(r)\ne \perp ]$ by a negligible $\nu$ for every fixed $r$, hence also for $r\stackrel{\$}{\leftarrow }\mathcal{R}$.