Cryptography

The traditional definition of pseudorandom number generators involves a bunch of statistical tests (see Knuth's "The Art of Computer Programming Vol. 2"), but this is insufficient for cryptographic purposes.

For example, a linear congruential generator: pick a prime $p$, pick $a,b\in {\mathbb{Z}}_p$, pick random seed $s\in {\mathbb{Z}}_p$, and iterate with $s\leftarrow as+b\mathrm{mod}p$ and output $\mathrm{LSB}(s)$ is considered a PRNG under the traditional definition, but is completely predictable, because given $\lg p$ bits one can recover the seed efficiently.

Instead, we require the pseudo-random number generator to fool any statistical test.

Definition (fixed security parameter version): A $(t,\epsilon )$-PRNG is a function $G:{\mathrm{0,1}}^n\to {\mathrm{0,1}}^m(m\gg n)$ such that

• $G$ is efficiently computable by a deterministic algorithm.

• $G$ "$\epsilon$-fools" all $t$-time statistical tests, that is, for all $t$-time algorithms $A$

$$\mathrm{Pr}[A(G(S))\text{accepts}\mid S\leftarrow \{\mathrm{0,1}{\}}^m]-\mathrm{Pr}[A(R)\mid R\leftarrow \{\mathrm{0,1}{\}}^m]<\epsilon$$

We say that the uniform distribution on ${\mathrm{0,1}}^m$ is $(t,\epsilon )$-indistinguishable from distributions $\{G(S)\mid S\leftarrow \{\mathrm{0,1}{\}}^n\}$.

We derive an equivalent characterization of PRNG's to that of Yao that is easier to work with. For $R\in \{\mathrm{0,1}{\}}^m$, denote the $i$th bit of $R$ by $R{\mid }_i$ and the first $i$ bits of $R$ by $R{\mid }_{1,...,i}$.

We say $G:\{\mathrm{0,1}{\}}^n\to \{\mathrm{0,1}{\}}^m$ $(t,\epsilon )$ passes the next bit test if for all $0\le i<m$ no $t$-time algorithm can predict $G(S){\mid }_{i+1}$ from $G(S){\mid }_{1,...,i}$, that is, for all $t$-time algorithms $M$ and for all $0\le i<m$

$$\mid \mathrm{Pr}[M(G(S){\mid }_{1,...,i})=G(S){\mid }_{i+1}]\mid S\leftarrow \{\mathrm{0,1}{\}}^m]-1/2\mid <\epsilon$$

Theorem: [Yao '82]

Suppose $G:\{\mathrm{0,1}{\}}^n\to \{\mathrm{0,1}{\}}^m$ $(t/m,\epsilon )$ passes the next bit test. Then $G$ is a $(t,\epsilon )$-PRNG. ("The next bit test is universal.")

Proof: Suppose we have a $(t,\epsilon )$-algorithm $A$ for $G$. Then we shall build a $(t,\epsilon /m)$-next bit predictor for $G$, by using a "hybrid argument":

Define the following collection of distributions ${𝒫}_0,...,{𝒫}_m$ as follows: the first $i$ bits of a member of ${𝒫}_i$ are found by picking a random $S\leftarrow \{\mathrm{0,1}{\}}^n$ and setting them to $G(S){\mid }_{1,...,i}$. The last $m-i$ bits are generated at random from $\{\mathrm{0,1}{\}}^{m-i}$. Then

$$\mathrm{Pr}[A(R)\mathrm{accepts}\mid R\leftarrow {𝒫}_0]=\mathrm{Pr}[A(R)\mathrm{accepts}\mid R\leftarrow \{\mathrm{0,1}{\}}^m]$$

and

$$\mathrm{Pr}[A(R)\mathrm{accepts}\mid R\leftarrow {𝒫}_m]=\mathrm{Pr}[A(R)\mathrm{accepts}\mid S\leftarrow \{\mathrm{0,1}{\}}^n,R\leftarrow G(S)]$$

Hence

$$\begin{array}{ccc}\epsilon & \le & \mid \mathrm{Pr}[A(R)\mid R\leftarrow {𝒫}_0]-\mathrm{Pr}[A(R)\mid R\leftarrow {𝒫}_m]\mid \\ & =& \mid \sum _{i=0}^{m-1}\mathrm{Pr}[A(R)\mid R\leftarrow {𝒫}_i]-\mathrm{Pr}[A(R)\mid R\leftarrow {𝒫}_{i+1}]\mid \\ & \le & \sum _{i=0}^{m-1}\mid \mathrm{Pr}[A(R)\mid R\leftarrow {𝒫}_i]-\mathrm{Pr}[A(R)\mid R\leftarrow {𝒫}_{i+1}]\mid \end{array}$$

Thus there exists $0\le i<m$ with

$$\mid \mathrm{Pr}[A(R)\mid R\leftarrow {𝒫}_i]-\mathrm{Pr}[A(R)\mid R\leftarrow {𝒫}_{i+1}]\mid \ge \epsilon /m$$

We can use $A$ to build a next bit predictor for $R{\mid }_{i+1}$.

The "hybrid argument" is quite useful: in general, suppose experiment (game) $E_0$ is distinguishable from experiment $E_m$. Then build experiments $E_1,...,E_{m-1}$, and then it can be shown that there exists $0\le i<m$ such that $E_i$ is distinguishable from $E_{i+1}$, which can be used to solve a challenge problem.

Hardcore bits can be used to construct PRNGs using a method due to Blum and Micali.