PRG in NC1 ⇒ PRG in NC0 (AIK)

Free reduction · standard model · AIK06 · security loss: none: a distinguisher for the encoding is a distinguisher for G after applying the simulator

Statement

Every PRG $G$ computable in ${\mathrm{NC}}^1$, and more generally in $\oplus \mathrm{L}/\mathrm{poly}$, can be compiled into a PRG in ${\mathrm{NC}}^0$ in which each output bit depends on at most four input bits — AIK06. The compiled generator has a polynomially longer seed and the same additive stretch as $G$, so its stretch is sublinear in its seed length.

Sketch

The compiled generator is a perfect randomized encoding $\hat{G}(x,r)$ of $G$ with locality four: there is an efficient simulator $\mathcal{S}$ with $\hat{G}(x,r)\equiv \mathcal{S}(G(x))$ for uniform $r$, and the encoding is balanced and stretch-preserving, so $\mathcal{S}$ maps a uniform input to a uniform output with the same additive stretch. Hence $\hat{G}(U)\equiv \mathcal{S}(G(U))$ is indistinguishable from $\mathcal{S}(U)\equiv U$ — AIK06.

Notes

• The same compiler applies to one-way functions, one-way permutations, encryption, signatures, commitments and collision-resistant hashing computable in ${\mathrm{NC}}^1$, and most number-theoretic and lattice assumptions give such primitives — AIK06.
• The compiled generator’s stretch is too small for the applications of polynomial-stretch local PRGs, such as JLS21’s indistinguishability obfuscation, which assume a polynomial-stretch PRG in ${\mathrm{NC}}^0$ directly — JLS21.