Low-complexity pseudorandom generator

A low-complexity PRG is a pseudorandom generator in ${\mathrm{NC}}^0$: each output bit depends on a constant number of input bits. For PRGs computable in ${\mathrm{NC}}^1$, see PRG in ${\mathrm{NC}}^1$. The existence of a Boolean PRG in ${\mathrm{NC}}^0$ (not ${\mathrm{NC}}^1$) with stretch $n^{1+\tau }$ for a constant $\tau >0$ is one of the four sub-exponentially hard assumptions from which JLS21 builds indistinguishability obfuscation.

TODO: syntax and security definition.

Variations

Polynomial-stretch PRG in NC0

A polynomial-stretch PRG in ${\mathrm{NC}}^0$ is a PRG $G:\{0,1{\}}^n\to \{0,1{\}}^{m(n)}$ in ${\mathrm{NC}}^0$ with $m(n)=n^{1+\tau }$ for a constant $\tau >0$.

Sub-exponential security

A polynomial-stretch PRG in ${\mathrm{NC}}^0$ is sub-exponentially secure if there is a constant $\epsilon >0$ such that for all sufficiently large $n$ every distinguisher of size at most $2^{n^{\epsilon }}$ has advantage at most $2^{-n^{\epsilon }}$.

Participates in

Builds on Low-complexity pseudorandom generator

• Sub-exponential SXDH + LWE + LPN + NC0-PRG ⇒ iO (via Sub-exponential security)
• Sub-exponentially secure NC0 PRG ⇒ NC0 PRG (via Sub-exponential security)

Produces Low-complexity pseudorandom generator

• PRG in NC1 ⇒ PRG in NC0 (AIK)
• Sub-exponentially secure NC0 PRG ⇒ NC0 PRG (via Polynomial-stretch PRG in NC0)