Pseudorandom generator

A Pseudorandom Generator (PRG) …

Syntax

A PRG $G$ is an pair of efficient algorithms $(\mathsf{Gen},\mathsf{Eval})$ using sets $\mathcal{K}$ and $\mathcal{R}$ with the syntax and intended usage:

• $\mathsf{Gen}(1^{\lambda })\to k,$ takes a security parameter $\lambda$ and outputs a key $k\in calK$
• $\mathsf{Eval}(k)\to r,$ takes a key $k\in \mathcal{K}$ and outputs a generated value $r\in \mathcal{R}.$

Properties

Pseudorandomness

Variations

Trapdoor pseudorandom generators

A trapdoor PRG is 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 calK$,
• $\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.