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 }}$.

Other results

• Conditional on the claimed algorithm of Ope26 (see ETH): for every fixed $d$, every $G:\{0,1{\}}^n\to \{0,1{\}}^m$ whose output bits each depend on at most $d$ input bits can be inverted on every point of its image, and $|G^{-1}(y)|$ computed exactly, in deterministic time $(n+m{)}^{O_d(1)}{2}^{O_d(n(\log \log n{)}^2/\sqrt{\log n})}$ and space $(n+m{)}^{O_d(1)}$ — Ope26 (Corollary C.2). For $m>n$, testing $|G^{-1}(y)|>0$ distinguishes $G(x)$ from uniform $y$ with advantage at least $1-2^{n-m}\ge 1/2$, so no PRG in ${\mathrm{NC}}^0$ is secure against distinguishers running in time $2^{\epsilon n}$ for a constant $\epsilon >0$. The running time is $2^{n^{1-o(1)}}$, so sub-exponential security as defined above is unaffected.

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)