NC0 PRG ⇒ NC1 PRG

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

Every PRG in is a PRG in , with the same stretch — folklore.

Sketch

Each output bit of is a function of at most input bits, so a fan-in-2 circuit of size and depth computes it; the output bits together take size and depth . The pseudorandomness game is the same.