Pseudorandom generator

A Pseudorandom Generator (PRG) stretches a short, uniformly random seed into a longer string that is computationally indistinguishable from a truly random string of the same length. Any efficient algorithm that sees only the output cannot tell whether it came from a PRG or from a truly random source.

Syntax

A PRG $G$ is an efficient deterministic function with respect to seed space $\mathcal{S}$ and output space $\mathcal{R},$ where $|\mathcal{R}|>|\mathcal{S}|:$

• $G:\mathcal{S}\to \mathcal{R},$ takes a seed $s\in \mathcal{S}$ and outputs a string $r\in \mathcal{R}.$

The ratio $\ell =|r|/|s|$ is called the stretch of the PRG. A PRG with stretch $\ell (\lambda )$ expands a $\lambda$-bit seed to $\ell (\lambda )\cdot \lambda$ output bits.

Properties

Pseudorandomness

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{prg}}_{G,\calA}(\secpar)$}
\begin{algorithmic}
\State $s \getsr \calS$; $b \getsr \{0,1\}$
\State $r_0 \gets G(s)$; $r_1 \getsr \calR$
\State $b' \gets \calA(1^\secpar, r_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

A PRG $G$ is pseudorandom if for all efficient $\mathcal{A},$

$${\mathbf{Adv}}_{G,\mathcal{A}}^{\mathrm{prg}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{G,\mathcal{A}}^{\mathrm{prg}}(\lambda )=1\right]-1\right|$$

is negligible.

Variations

Keyed PRG

A keyed PRG is a pair of efficient algorithms $(\mathsf{Gen},\mathsf{Eval})$ where $\mathsf{Gen}(1^{\lambda })\to k$ samples a key and $\mathsf{Eval}(k)\to r$ produces the output. This models a PRG whose parameters (seed length, output length) are determined by a key generation algorithm. The security definition is the same as above, but now the adversary sees $r_0=\mathsf{Eval}(k)$ for a fresh key $k\leftarrow \mathsf{Gen}(1^{\lambda }).$

Trapdoor pseudorandom generators

A trapdoor PRG is a tuple $G$ of efficient algorithms $(\mathsf{Gen},\mathsf{Eval},\mathsf{Invert})$ such that

• $\mathsf{Gen}(1^{\lambda })\to (t,k),$ takes a security parameter $\lambda$ and outputs a trapdoor $t\in \mathcal{T}$ and a key $k\in \mathcal{K}$,
• $\mathsf{Eval}(t,k)\to r,$ takes a trapdoor $t\in \mathcal{T}$ and key $k\in \mathcal{K}$, and outputs a value $r\in \mathcal{R}$,
• $\mathsf{Invert}(t,r)\to b,$ takes as input a trapdoor $t\in \mathcal{T}$ and a value $r\in \mathcal{R}$ and outputs a bit $b\in \{0,1\}$ indicating whether the value was generated pseudorandomly or not.

The pseudorandomness of a trapdoor PRG is equivalent to the pseudorandomness of $(\mathsf{Gen},\mathsf{Eval})$ treated as a PRG with keyspace $(\mathcal{K}\times \mathcal{T}).$ Beyond that, a trapdoor PRG should be

• $(1-\epsilon )$-complete: meaning $k\in \mathcal{K},$ $$\mathrm{Pr}[\mathsf{Invert}(t,\mathsf{Eval}(t,k))=1:(t,k)\stackrel{\$}{\leftarrow }\mathsf{Gen}(1^{\lambda })]\ge 1-\epsilon ,$$
• $(1-\delta )$-sound: for all $t\in \mathcal{T},$ $$\mathrm{Pr}[\mathsf{Invert}(t,r)=0:r\stackrel{\$}{\leftarrow }\mathcal{R}]\ge 1-\delta .$$

Note that a zero-bit Pseudorandom Code can be viewed as a trapdoor pseudorandom generator with the additional property that its completeness is actually robust to noise.

Other results

• OWFs imply PRGs, via the Goldreich-Levin hard-core predicate — HILL99, GL89
  • Conversely, any PRG is a one-way function (the seed is a preimage of the output), so OWF $\iff$ PRG
• The first PRG from a concrete assumption: discrete-log hardness implies a PRG — BM84
• A length-doubling PRG implies PRFs via the GGM binary-tree construction — GGM86
• PRG implies CPA-secure SKE: the stream cipher $\mathsf{Enc}(k,m)=G(k)\oplus m$ is CPA-secure whenever $G$ is a PRG with stretch $|m|$