Pseudorandom Generators (PRG)

In cryptographic applications, we need randomness. A lot of randomness. But true randomness is a rare commodity. That's where (cryptographic) pseudorandom generators (PRGs) enter the scene. They are deterministic algorithms than expand a seed of truly random bits into a much larger sequence of bits that are not truly random, but that look random. A PRG is good enough for cryptographic purposes, if its output is computationally indistinguishable from white noise, a.k.a. a random uniform distribution, to every probabilistic polynomial time (PPT) bounded distinguisher. This definition is the "cryptographic Turing test". An equivalent definition is next-bit unpredictability. We'll show that both definitions are equivalent, using a widely used proof technique: the hybrid argument. Finally, we'll show how to construct PRGs with one-way predicates, by making use of OWF's hardcore bits.

True Randomness Is A Rare Commodity

Classical computers are inherently deterministic machines. They can't create randomness on their own. But the real world has a lot of randomness to offer: Brownian motion, radioactive decay, the time delay between keystrokes and interrupts of the network adapter cards. There's a whole theory on true random number generators a.k.a TRNGs[SMS07], and how to design them[F14]. Current CPUs even come with a hardware random number generator which measures tiny deviations between two internal oscillators due to thermal noise[INTEL14, K09] and one can even implement them on an FPGA[TLL07]!  The point here is that we can import this randomness into the deterministic computer.

Theoretically, importing true randomness into a deterministic machine is equivalent to providing a Turing machine with an additional input tape preloaded with truly random bits.

So we could simply use this source of true randomness, right? Wrong!

For one, the randomness obtained from those sources is biased, and certainly not uniformly distributed. It is not white noise. This is already bad enough. But for this, we have a cure since 1951, due to John von Neumann[N51]: just collect the random bits pairwise, and output a 0 if we collected 10, and output a 1 if we collected 01. If we got 00 or 11, don't output anything. The resulting sequence will be as good as white noise[M02].

Why is the postprocessed sequence of bits like white noise? The analysis is quite involved, but the main argument goes like this: assume than 0 comes with probability \(p\) and 1 comes with probability \(q = 1 - p\). Then, the probability that we get 01 is \(pq\), and the probability that we get 10 is \(qp\). But, of course, \(pq = qp\). Isn't that beautiful? Iterating this procedure requires some care[P92], but you got the idea. Extracting randomness from biased sources is a huge area of reseach called the Theory of Randomness Extractors[V12, Chapter 6].

So we're now good and could use this output? Not really. The output may be qualitatively great, but the randomness sensors have a limited speed. In other words, we won't get random bits as fast as we need them. Say, our sensors and postprocessing could generate 100 random bits per second, a realistic assumption. Recall RSA? How many random bits are currently secure keys supposed to have? 2048 is barely enough, 4096 would be better. Are we really willing to wait 20 or 40 seconds for the entropy pool to fill up to generate one key? And it's worse than that with RSA: we need two random primes \(p\) and \(q\), which we multiply to get \(N\). But due to the nature of primality tests, we will have to randomly pick many candidates for \(p\) and \(q\) until we get lucky to find a prime. That's a lot more than 2048 or 4096 random bits that we need.

It even gets worse than this. In this series, we'll cover probabilistic encryption. For reasons that will become clear there, each time we encrypt something, we'll need random bits. A lot of them.

Clearly, using truly random bits from real world sensors (or from the auxillary tape with random numbers in the case of a Turing machine) isn't practical. We need a better solution.

PRGs are Randomness Expanders

Informally, a pseudorandom generator \(G\) is a deterministic program, which expands a small string of hopefully truly random bits (called the seed) into a huge string of bits, which look "random enough". By "huge", we mean string lengths polynomial in the size of the seed (i.e. \(|G(s)| = \operatorname{poly}(|s|)\), where \(\operatorname{poly}\) is any polynomial). For example, \(G\) could expand a 128-bit long seed into a string of \(128^{1000000}\) bits.

By "random enough", we mean that anyone with bounded computational resources observing the generated bits, can't tell the difference between them and truly random bits. We'll come back to this below.

This is a formal definition[FOC, Volume 1, Definition 3.3.1]:

Definition (Pseudorandom Generator, Standard Definition): A pseudorandom generator is a deterministic polynomial-time algorithm \(G\) satisfying the following two conditions:

  1. Expansion: There exists a function \(\ell \colon \mathbb N \rightarrow \mathbb N\) such that \(\ell(n) \gt n\) for all \(n \in \mathbb N\), and \(|G(s)| = \ell(|s|)\) for all \(s \in \{0,1\}^*\)
  2. Pseudorandomness: The ensemble \(\{G(U_n)\}_{n \in \mathbb N}\) is pseudorandom.

To fully understand this definition, we also need:

Definition (Probability Ensemble): Let \(I\) be a countable index set. An ensemble indexed by \(I\) is a sequence of random variables indexed by \(I\). Namely, for any \(X = \{X_i\}_{i \in I}\), where each \(X_i\) is a random variable, is an ensemble indexed by \(I\).

In general, we denote by \(U_n\) a random variable uniformly distributed over the set of strings of length \(n\). This means than \(\operatorname{Pr}[U_n = \alpha]\) equals \(2^{-n}\) if \(\alpha \in \{0,1\}^n\), and equals zero otherwise [FOC, Volume 1, 1.2.1. page 9].

Now, we still need to define the term "pseudorandom".

Indistinguishability From White Noise (The Cryptographic Turing Test)

In the past, designers of pseudorandom generators used ad hoc approaches. They invented some scheme, and applied a battery of statistical tests[DIEHARDER] on it to ensure that the generated pseudorandom numbers looked random enough. If the scheme passed all those tests, it was "good enough". There's a whole literature on this kind of traditional PRGs, e.g. [K81, Chapter 3: Random Numbers].

Unfortunatly, this approach isn't sufficient for cryptographic secure pseudorandom generators (CSPRNG). Why? Because the designers can't predict all statistical tests that a sophisticated attacker can apply, now or in the future. To be on the safe side, a PRG needs to be immune against all possible (efficient) distinguishers, no matter what kind of strategy they may employ.

We therefore define "pseudorandomness" in PRGs using the general notion of indistinguishability:

Definition (Pseudorandom Generator, Indistinguishability): A deterministic polynomial time computable function \(G \colon \{0,1\}^n \rightarrow \{0,1\}^m\) is a PRG if

  1. Expansion: \(m \gt n\)
  2. Indistinguishability: for every PPT algorithm \(D\), there exists a negligible function \(\operatorname{negl} \colon \mathbb N \rightarrow \mathbb R\) such that:
    \[ | \operatorname{Pr}[ D(G(U_n)) = 1 ] - \operatorname{Pr}[ D(U_m) = 1 ] | = \operatorname{negl}(n) \]

As before, \(U_n\) (resp. \(U_m\)) denotes the uniform random distribution of \(n\)-bit strings \(\{0,1\}^n\) (resp. \(\{0,1\}^m\)). The algorithm \(D\) is called a distinguisher. It is supposed to return 0 if it deems its input to be pseudorandom, and to return 1 if it deems its input to be truly random.

Recall that a negligible function \(f\) is a function \(f \colon \mathbb N \rightarrow \mathbb R\), such that for every polynomial \(p \colon \mathbb N \rightarrow \mathbb N\), there exists an \(m \in \mathbb N\), so that for all \(n \gt m\) we have \(f(n) \lt \frac{1}{p(n)}\).

This PRG definition using computational indistinguishability is colloquially called the cryptographic Turing test, because just like in the Turing test, if a distinguisher can't tell the difference between an intelligent human and an intelligent program, we assume that both are intelligent, here we don't care what strategy the distinguisher uses. If it can't distinguish pseudorandomness from true randomness, then for all practical purposes, they are equal. Or, in other words: If it looks like a duck, swims like a duck, and quacks like a duck, then it probably is a duck (the Duck Test).

It should be stressed that the Indistiguishability definition restricts the distinguishers to probabilistic polynomial time. This means that a computationally unbounded distinguisher could very well tell the difference between a pseudorandom distribution and a truly random distribution. But for all practical purposes, i.e. for every real world distinguisher, the output of a good PRG would be as good as truly random, even though it isn't truly random.

Next-bit Unpredictability

An alternative definition for pseudorandomness is next-bit unpredictability:

Definition (Pseudorandom Generator, Next-bit Unpredictability): A deterministic polynomial time computable function \(G \colon \{0,1\}^n \rightarrow \{0,1\}^m\) is a pseudorandom generator if

  1. Expansion: \(m \gt n\)
  2. Next-bit Unpredictability: for every next-bit predictor PPT algorithm \(\operatorname{PRED}\) and for every \(i \in [m] := \{1, 2, \dots, m\}\), there exists a negligible function \(\operatorname{negl} \colon \mathbb N \rightarrow \mathbb R\), such that:
    \[ | \operatorname{Pr}[ y \leftarrow G(U_n) \colon \operatorname{PRED}(y_1 y_2 \dots y_{i-1}) = y_i] - \frac{1}{2} | = \operatorname{negl}(n) \]

where \(y_i\) denotes the \(i\)-th bit of \(y\), and \(y_{1 \dots i}\) denotes the first \(i\) bits of \(y\).

This means that a PRG is good enough, if any probabilistic polynomial time predictor, given \(i-1\) bits of the PRG's output, can't distinguish the next bit output by the PRG with more than \(\frac{1}{2}\) probability, i.e. with more than pure guessing.

In other words, no matter the stragegy used, a next-bit predictor has no advantage predicting the next bit of a pseudorandom sequence compared to predicting (guessing with probability \(\frac{1}{2}\)) the next bit of a truly random sequence.

Again, it must be stressed that this only applies to polynomial time bounded predictors. Next-bit predictors with superpolynomial time may very well be able to tell the difference, but for all practical purposes, since we equated efficient algorithms with PPT algorithms, we only care for ppt next-bit predictors.

Corollary: a PRG can't expand \(n\) superpolynomially and still be good enough, i.e. \(m\) can't be superpolynomial in \(n\). In other words, \(m = \operatorname{poly}(n)\) for some polynomial \(\operatorname{poly}\).

Indistinguishability and Next-bit Unpredictability Are Equivalent

Even though they look very different, both definitions are equivalent[FOC, Volume 1, Theorem 3.3.7 Pseudorandomness versus Unpredictability]:

Theorem (equivalence of indistinguishability and next-bit unpredictability): For all pseudorandom generators \(G\), the following are equivalent:

  1. \(G\) satisfies the Indistinguishability definition
  2. \(G\) satisfies the Next-bit unpredictability definition

Proof (idea):

\(1 \implies 2\): This is the easy direction. Proof by contradiction: If there exists a ppt next-bit predictor which can guess the next bit with probability non-negligibly more than \(1/2\), then we can use this next-bit predictor as a subroutine in a distinguisher that well tell the difference between a pseudorandom distribution and a truly random distribution with more than negligible probability.

More concretely:

  • the distinguisher \(D\) will (say randomly) pick \(i - 1\) consecutive bits \(y_1 y_2 \dots y_i\) from the output of \(G\).
  • \(D\) feeds \(y_1 y_2 \dots y_{i-1}\) to the next-bit predictor \(\operatorname{PRED}\).
  • if \(\operatorname{PRED}(y_1 y_2 \dots y_{i-1}) = y_i\), then \(D\) outputs 1 for "this is pseudorandom", else \(D\) outputs 0 for "this is truly random".

It is obvious that if the next-bit predictor can predict bit \(y_i\) with more than \(1/2\) probability, then the distinguisher \(D\) can distinguish between pseudorandom and truly random with more than negligible probability.

\(2 \implies 1\): This is the hard direction. We need the hybrid technique for this, which we cover next. We'll return to the proof sketch after that. A quick preview is that we proceed again by contradiction, and we'll need two steps here:

  • the hybrid technique
  • moving from distinguishing (general) to next-bit predicting (special).

By "general" vs. "special" we mean that the distinguisher can only tell the difference in a general sense, considering the whole output. But we need to move from this general distinguisher to a very specific statistical test, i.e. the next-bit predictor. It is not clear at this point how this can be done. But it will once we've understood the hybrid technique. \(\Box\)

The Hybrid Technique

For lack of time, I won't explain the hybrid technique at this point. Interested readers may watch Vinod's lecture (see below), or consult [FOC, Volume 1, 3.2.3. Indistinguishability by Repeated Experiments] which introduces the Hybrid Technique in a proof.

(... section to be expanded)

Resuming the Proof of the Equivalence Theorem

Here too, for lack of time, I won't show the direction \(2 \implies 1\). Again, interested readers can watch the proof in Vinod's lecture, or read it with all its gory details in [FOC, Volume 1, Theorem 3.3.7 (Pseudorandomness versus Unpredictability), Proof for the "Opposite" Direction].

(... section to be expanded)

Constructing PRGs from One-way Permutations

(... to be written)

PRGs imply OWF

(... to be written)

Sources

The material covered here is pretty stardard in Theoretical Cryptography. [FOC, Chapter 3] covers pseudorandom generators in depth, using a rigorous formalism. The original paper showing how to generate cryptographically strong sequences of pseudorandom bits is [BM82]. The Hybrid Technique was introduced in [GM84].

(... to do: add original papers)

Vinod Vaikuntanathan gave a lecture on PRGs in "L6: Pseudorandom Generators" of an advanced course. The definition about indistinguishability (the "cryptographic Turing test") starts at 18:51, next-bit unpredictability starts at 22:09, that both definitions are equivalent is proven at 24:06. The extremely useful hybrid argument technique is explained at 31:13. Finally, at 56:55, the construction of pseudorandom generators from one-way functions is shown.

To test the quality of pseudorandom generators, one can use the diehard battery of statistical tests. An implementation is the tool dieharder[DIEHARDER], a more recent one is the TestU01 library[TestU01], and the very popular NIST Statistical Test Suite[NISTSTSIMPROVED]. These tools and libraries can also be used as a distinguisher for all kinds of cryptographic algorithm outputs that are supposed to look like white noise (e.g. the output of randomized encryption). But remember, this is merely a subset of possible statistical tests.

Literature