Pseudorandom Generators

One-time pad is not a particularly useful encryption scheme. Among other problems, the key must be as long as the plaintext, which presents a kind of chicken-and-egg situation: I can't privately send you $n$ bits of information unless we already privately share $n$ bits of information. This chapter is about overcoming this limitation of OTP:

5.1. Defining pseudorandomness

OTP encrypts its plaintexts using the xor operation, which requires its two arguments to have the same length. So if we want an encryption method similar to OTP, but with a key that is shorter than the plaintext, we need some way to expand the key into a longer string:

What would need to be true about this mysterious “key expansion” method?

• It would need to be deterministic, so that both the sender and receiver can expand their key in the same way.

• Its output distribution would need to be uniform, since that is a crucial property for the security of OTP.

Unfortunately, it's not possible to achieve both of these properties simultaneously. Suppose the expansion method is a deterministic function $G: \bits^n \to \bits^{n+\ell}$, so its outputs are $\ell$ bits longer than its inputs. Then there are $2^{n+\ell}$ strings of length $n+\ell$, but only (at most) $2^n$ possible outputs of $G$. So the outputs of $G$ can never induce a uniform distribution.

But let's not give up hope just because our goal is impossible!

We want a deterministic function, with outputs that are longer than its inputs, and whose outputs can induce a uniform distribution. This is impossible, but perhaps it is possible to have a function with an output distribution that is merely indistinguishable from uniform.

A pseudorandom generator is the missing piece that enables us to encrypt long plaintexts with a short key.

Let's first understand the attack scenario that this definition formalizes.

• A victim (or the $\lib{prg-real}$ library) samples a seed uniformly from $\bits^\secpar$ and uses it as input to $G$.

• Since the only input to the PRG is its seed, which is chosen and managed by the victim, there are no inputs left for the adversary to control. Thus, the subroutines in the $\lib{prg-*}$ libraries take no arguments.

• The adversary sees the output of $G$, which is supposed to be indistinguishable from the uniform distribution.

• The victim uses a seed only once. If the adversary calls $\prgsamp$ more than once, a fresh seed is chosen each time.

The $\lib{prg-real}$ library generates outputs according to the distribution illustrated below on the left, the $\lib{prg-rand}$ library according to the distribution illustrated on the right.

This picture presents a global view of a PRG, which can lead to some confusion. Suppose the PRG has input length $\secpar=128$ and stretch $\ell = 128$, and therefore output length 256. Then only $2^{128}/2^{256} = 1/2^{128}$ fraction of strings are possible outputs of the PRG—these correspond to the dots in the left picture. You might wonder how the two distributions could possibly be indistinguishable if one includes only a $1/2^{128}$ fraction of the possible outcomes.

But an adversary doesn't have a global view of this PRG picture—it has only a tiny glimpse. In our concrete example, an ambitious adversary might observe $2^{64}$ PRG outputs, which is still only a $1/2^{64}$ fraction of the pseudorandom distribution! More generally, an adversary can observe only polynomially many samples from these exponentially large distributions: a negligible fraction of both the pseudorandom and uniform distributions. A more accurate depiction of the adversary's perspective looks like this:

The adversary observes only a small number of samples from the two distributions, illustrated here as the darkly shaded dots.

Things to remember about the PRG security definition: First, the libraries in definition 5.1.2 give the PRG output directly to the adversary. Remember, when an attack scenario allows the adversary to see a value, we are saying that we want security to hold no matter how that value is used elsewhere. So the PRG security definition says (when the seed value is managed appropriately), “PRG output is a safe substitute for truly uniform randomness, in any situation.”

Second, a PRG is only as good as the quality of its seed. Security rests on the fact that the seed is sampled uniformly from $\bits^\secpar$; how to do this effectively on a real computer is an important question, out of scope from the perspective of the PRG security definition. Security also rests on the seed remaining secret and not being reused.

5.2. Do PRGs exist?

I can't give any example of a PRG whose security can be proven in the same way that we can prove the security of OTP. If such a PRG existed, it would resolve the most famous unsolved question in computer science (see exercise 5.3). The P vs NP question is about what problems a polynomial-time algorithm can/can't solve, and the PRG security definition is about what a polynomial-time adversary can/can't do. So we cannot prove security from “first principles”; we can only conjecture about the security of any particular PRG.

Although we deal in conjectures, these conjectures don't have to be frivolous; they can be informed by strong circumstantial evidence. For example, we can sometimes prove that a PRG resists certain special types of attacks. We can expose a PRG to intense public scrutiny; if no attacks are found despite serious attempts, we gain more confidence about its security.

PRGs are only the first of many primitives and security goals that we'll study. Each of these primitives suffers from the same P vs NP barrier: We can't prove from “first principles” that any particular algorithm achieves any of these security goals. For each primitive, we can identify promising candidate algorithms and conjecture that they are secure.

But cryptography is not a large collection of unconnected, ad hoc conjectures about security. One of the pillars of provable security is that we can use mathematical proofs to reduce the number of conjectures.

Using provably secure constructions of this kind, we can minimize the number of assumptions. Ideally, we would conjecture about just one kind of primitive, then use it to build all the others we care about. We study many different primitives, so there are many choices for which one to choose as the “axiom” of provable security.

Valuing mathematical elegance and order of presentation: PRGs are the simplest primitive with security that can't be proven from first principles. We can use PRGs to provably build everything else in the symmetric-key part of this book. For example, we show how to use a PRG to build a PRF (don't worry what that means right now) and prove that the resulting PRF is secure if the underlying PRG is secure. Then we show how to use a PRF to build symmetric-key encryption and prove that the encryption is secure if the underlying PRF is secure, and so on.

Thus, the security of PRFs and symmetric-key encryption (and other primitives) ultimately reduces to the security of the simpler underlying PRG. In other words, if secure PRGs exist, then surely secure PRFs and secure symmetric-key encryption (and other primitives) exist as well. The conjecture that secure PRFs exist is therefore not an extra conjecture; we get PRFs for free, assuming that secure PRGs exist.

In this book, we start with the simplest primitives (PRGs) and build “upward” in conceptual complexity. Most of the constructions you will see are oriented in this direction: building something more complex from something simpler.

Valuing practical efficiency: It is instructive to understand how, for example, secure symmetric-key encryption can be built from PRGs alone. However, real-world encryption schemes are not built in this way; the result would be far too inefficient because PRGs are too low-level. In practice, symmetric-key encryption is built from objects of intermediate complexity—typically PRPs, which are introduced later in chapter 7. These PRPs serve as the “ground truth” for cryptographic constructions in practice; we standardize highly optimized PRPs and use them to construct other things of both higher and lower complexity, with security proofs that reduce security to that of the underlying PRP.

5.3. Application: Pseudo-OTP

We originally motivated PRGs as a way to encrypt long plaintexts using a short key. Let's return to that motivation and formalize the details.

The key in pseudo-OTP is only $\secpar$ bits, but it can be used to encrypt a plaintext of length $\secpar+\ell$. Pseudo-OTP achieves a similar security property to plain OTP, but involving indistinguishability:

Proof idea: You might expect a security proof for something called pseudo-OTP to closely follow the security proof for plain OTP. We proved claim 2.2.2 by explicitly calculating probabilities. Unfortunately, that same strategy won't work against pseudo-OTP, because the PRG $G$ is completely unspecified; we simply don't seem to have enough information to reason about exact probabilities.

Instead, we must remember this chapter's motivation: We want to use a value $G(\key)$ as a OTP key to mask the plaintext. Plain OTP requires its key to be uniform, but the theme of this chapter is that being pseudorandom is the next best option.

This idea is formalized in a proof by introducing an intermediate hybrid library. $\lib{ots-real}$, which generates pseudo-OTP ciphertexts using $G(\key)$ as a kind of OTP key, is indistinguishable from a library that uses a truly uniform OTP key. This new library generates true OTP ciphertexts, so it is of course indistinguishable from $\lib{ots-real}$, as desired. So instead of adapting the technique used to prove security of OTP, we simply use the security of OTP, as-is, in a single step of our proof.

5.4. How to extend a PRG's stretch

A PRG's stretch measures how much longer the plaintext can be than the key in pseudo-OTP. A larger stretch means you can encrypt longer plaintexts with a conveniently short key.

In this section, we show how to use a PRG with small stretch to build a PRG with longer stretch. We illustrate only the case of using a PRG with stretch $\secpar$ to build a PRG with stretch $2\secpar$. Exercise 5.9 explores the more general case.

We can extend a PRG's stretch by invoking it twice in sequence:

Construction 5.4.2 (PRG feedback construction)

Let $G$ be a length-doubling PRG. Then the following function is length-tripling:

$H(\seed)$:

$A \| B := G(\seed)$

$C \| D := G(B)$

return $A \| C \| D$

$\quad$

Proof idea: We want to show that $H$ is a secure PRG. In other words, when inputs to $H$ are chosen uniformly, its outputs are indistinguishable from uniform. Working backwards from our desired goal, what can we say about the outputs of $H$?

Its output consists of three blocks, each of which is the output of some call to $G$, a secure PRG. Outputs of a PRG are pseudorandom, so proof complete... right? Don't fall into this tempting trap; things are not so simple! A secure PRG is not a magical device that always produces pseudorandom output in every situation; its outputs are pseudorandom only when its input is chosen uniformly.

Here's another way to think about it: The only way to use the fact that $G$ is a secure PRG in a proof is to factor out some lines of a library into a separate instance of $\lib{prg-real}^G$, so they can be replaced with $\lib{prg-rand}^G$. In $\lib{prg-real}^G$, the input to $G$ is sampled uniformly.

$H$ computes its final two output blocks as $C \|D := G(B)$. In order to take advantage of $G$'s property as a secure PRG, its input $B$ must be chosen uniformly. Unfortunately, this is not the case here; fortunately, though, $B$ is pseudorandom, and that's the next best option. It means we can consider an indistinguishable intermediate hybrid in which $B$ actually is uniform.

Thus, the proof has two main steps:

• Starting with $\lib{prg-real}^H$, apply the PRG security of $G$ to the first call to $G$, which is possible because it involves a uniform input to $G$. The result is a new intermediate hybrid in which $A$ and $B$ are uniformly sampled.

• Now that the intermediate hybrid samples $B$ uniformly, we can apply the PRG security of $G$ to the remaining call to $G$, on input $B$.

5.5. How to attack pseudorandomness

Security is a knife's edge. One small change can make a secure construction catastrophically insecure. In this book we will encounter many examples of this phenomenon, starting with the following small modification to construction 5.4.2:

Claim 5.5.1 (An insecure attempt at extending a PRG's stretch)

The following function $H$ is not a secure PRG, even if $G$ is.

$H(\seed)$:

$A \| B := G(\seed)$

$C \| D := G(B)$

return $A \| \hl{B} \| C \| D$

$\quad$

In other words, the following two libraries are not indistinguishable:

$\lib{prg-real}^H$

$\prgsamp(\,)$:

$\seed \gets \bits^\secpar$

// $H(\seed)$:

$A\|B := G(\seed)$

$C\|D := G(B)$

return $A\|B\|C\|D$

$\not\indist$

$\lib{prg-rand}^H$

$\prgsamp(\,)$:

$Y \gets \bits^{4\secpar}$

return $Y$

Pay special attention to how this claim is worded. We should be able to attack $H$, even when $G$ is the most secure PRG in the world. It would be futile in that case to try to distinguish outputs of $G$ from uniform.

Instead, we must attack the erroneous way that $H$ uses $G$. Even the best PRG in the world can guarantee security only when its seed is chosen uniformly and not used for anything else. This is the “proper” way to use a PRG, spelled out explicitly in $\lib{prg-real}$.

Our $H$ function violates this “contract” by using $B$ as the input to $G$ while also including $B$ in the output. An adversary who knows $B$ can also compute $G(B)$, and will notice that the result is exactly equal to the second half of the output from $H$. On the other hand, if $A, B, C,$ and $D$ are all chosen uniformly, it is unlikely that $C\|D$ will have anything to do with the value $G(B)$. Thus, we have identified a way to distinguish outputs of $H$ from the uniform distribution.

We now formalize this attack idea, proving claim 5.5.1:

Exercises

1. Describe an exponential-time adversary that can successfully distinguish the two libraries from definition 5.1.2, and calculate its distinguishing advantage.

2. Suppose $G_1$ and $G_2$ are both secure PRGs with identical input/output lengths. Is it possible to tell whether a victim is generating outputs according to $G_1$ or $G_2$ just by looking at its outputs? Assume that the victim indeed samples seeds uniformly and uses each seed only once.

3. Let $G : \bits^\secpar \to \bits^{\secpar+\ell}$ be a deterministic function, and define the following set:

   $A_G := \{ Y \mid \exists \seed \in \bits^\secpar : G(\seed) = Y \}.$

   Show that if there is a polynomial-time (in $\secpar$) algorithm for determining membership in $A_G$, then $G$ is not a secure PRG.

   $A_G$ is unconditionally in the complexity class NP, for any polynomial-time function $G$. If P = NP, then there is a polynomial-time algorithm for membership in $A_G$. In other words, if P = NP, no function $G$ can be a secure PRG.

4. What can an adversary learn by observing two pseudo-OTP ciphertexts encrypted using the same key?

5. Pseudo-OTP (construction 5.3.1) is defined in terms of a function $G : \bits^\secpar \to \bits^{\secpar+\ell}$. We proved that if $G$ is a secure PRG, then pseudo-OTP has computational one-time secrecy. Prove that the converse is also true: If pseudo-OTP (using some function $G$) has computational one-time secrecy, then $G$ is a secure PRG.

6. Let $G$ be a length-doubling PRG. Show that the following encryption scheme does not have computational one-time secrecy, even if $G$ is a secure PRG:

   $\begin{aligned} \K &= \bits^\secpar \\ \M &= \bits^{4\secpar} \\ \C &= \bits^{4\secpar}\end{aligned}$

   // each $\ptxt_i$ is exactly $\secpar$ bits

   $\Enc(\key,\ptxt_1 \| \cdots \| \ptxt_4)$:

   $S_1 \| S_2 := G(\key)$

   $S_3 \| S_4 := G(S_1)$

   for $i =1$ to $4$:

   $\ctxt_i := S_i \oplus \ptxt_i$

   return $\ctxt_1 \| \cdots \| \ctxt_4$

   // each $\ctxt_i$ is exactly $\secpar$ bits

   $\Dec(\key,\ctxt_1 \| \cdots \| \ctxt_4)$:

   $S_1 \| S_2 := G(\key)$

   $S_3 \| S_4 := G(S_1)$

   for $i =1$ to $4$:

   $\ptxt_i := S_i \oplus \ctxt_i$

   return $\ptxt_1 \| \cdots \| \ptxt_4$

7. Prove that if an encryption scheme $\Sigma$ has computational one-time secrecy, then the following two libraries are indistinguishable:

   $\lib{left}$

   $\otsenc(\ptxt)$:

   $\key \gets \Sigma.\K$

   $\ctxt := \Sigma.\Enc(\ptxt)$

   return $\ctxt$

   $\indist$

   $\lib{right}$

   $\otsenc(\ptxt)$:

   $\key \gets \Sigma.\K$

   $\ptxt' \gets \Sigma.\M$

   $\ctxt := \Sigma.\Enc(\hl{\ptxt'})$

   return $\ctxt$

8. Suppose $\Sigma_1$ and $\Sigma_2$ are encryption schemes, where $\Sigma_2.\K \subseteq \Sigma_1.\M$ (i.e., $\Sigma_1$ can encrypt keys for $\Sigma_2$). Prove that if both $\Sigma_1$ and $\Sigma_2$ have computational one-time secrecy, then so does the following scheme (from construction 2.6.1):

   $\begin{aligned}\K &:= \Sigma_1.\K \\ \M &:= \Sigma_2.\M \\ \C &:= \Sigma_1.\C \times \Sigma_2.\C \end{aligned}$

   $\Enc(\key,\ptxt)$:

   $\key' \gets \Sigma_2.\K$

   $\ctxt_1 := \Sigma_1.\Enc(\key,\key')$

   $\ctxt_2 := \Sigma_2.\Enc(\key',\ptxt)$

   return $(\ctxt_1,\ctxt_2)$

   $\Dec(\key,(\ctxt_1,\ctxt_2))$:

   $\key' := \Sigma_1.\Dec(\key,\ctxt_1)$

   $\ptxt := \Sigma_2.\Dec(\key',\ctxt_2)$

   return $\ptxt$

9. In construction 5.4.2 we showed how to transform a PRG with stretch $\secpar$ into one with stretch $2\secpar$. Show how to extend a PRG with stretch 1 into a PRG with stretch $\ell$, for any $\ell > 1$. Prove that your construction is secure.

10. Prove that if $G$ is a secure length-doubling PRG, then the following algorithm $H$ is also a secure PRG:

    $H(\seed)$:

    $A\|B := G(\seed)$

    $C := G(A)$

    $D := G(B)$

    return $C \| D$

11. We've been so focused on extending a PRG's stretch, but what about reducing a PRG's stretch? Prove that if $G$ is a secure length-tripling PRG (i.e., its output is $3\secpar$ bits), then the following algorithm $H$ is also a secure PRG:

    $H(\seed)$:

    $A\|B\|C := G(\seed)$

    return $A \| B$

12. h Prove that if $G$ is a secure PRG, then the function $H(\seed) = \overline{G(\seed)}$ is also a secure PRG. $\overline{G(\seed)}$ means to take the bitwise complement of $G(\seed)$ (i.e., flip every bit in the string $G(\seed)$).

    $\overline{X} = X \oplus \bit1^\secpar$.

13. h Prove that if $G$ is a secure PRG, then the function $H(\seed) = G(\overline{\seed})$ is also a secure PRG. $\overline{\seed}$ means to take the bitwise complement of $\seed$ (i.e., flip every bit in the string $\seed$).

    $\overline{X} = X \oplus \bit1^\secpar$.

14. In this exercise, let's allow a PRG to have input length other than exactly $\secpar$ bits. The only restriction should be that the PRG's output is longer than its input.

    Let $G_1$ and $G_2$ be length-tripling functions, and define the algorithm

    $H( \seed_1 \| \seed_2 ) = G_1(\seed_1) \oplus G_2(\seed_2).$

    So $H$ has inputs of length $2\secpar$ and outputs of length $3\secpar$. Show that $H$ is a secure PRG if either $G_1$ or $G_2$ is secure.

    Your proof should involve two cases: In the first case, assume that $G_1$ is secure, but assume nothing about $G_2$, except that its outputs have the correct length. Then repeat, swapping the roles of $G_1$ and $G_2$.

15. Continuing the previous exercise, what is wrong with the simpler construction $H(\seed) = G_1(\seed) \oplus G_2(\seed)$?

16. In this exercise, let's allow a PRG to have input length other than exactly $\secpar$ bits. The only restriction should be that the PRG's output is longer than its input.

    1. Let $G : \bits^\secpar \to \bits^{3\secpar}$ be a conventional length-tripling PRG. Prove that the following function $H: \bits^{2\secpar} \to \bits^{3\secpar}$ is a secure PRG if $G$ is:

       // $\seed$ is $2\secpar$ bits

       $H(\seed)$:

       // $A$ = first $\secpar$ bits of $\seed$

       $A \| B := \seed$

       return $G(A)$

       Thus, it is possible for a PRG to be secure despite ignoring half of its seed.

    2. Let $G : \bits^\secpar \to \bits^{2\secpar}$ be a conventional length-doubling PRG. Prove that the following function $H: \bits^{2\secpar} \to \bits^{3\secpar}$ is a secure PRG if $G$ is:

       // $\seed$ is $2\secpar$ bits

       $H(\seed)$:

       // $A$ = first $\secpar$ bits of $\seed$

       $A \| B := \seed$

       return $A \| G(B)$

       Thus, it is possible for a PRG to be secure despite including half of its seed directly in the output.

17. h Suppose $G$ is a secure PRG with stretch $\ell$. Prove that the following function $H$ is also a secure PRG:

    $H(\seed)$:

    if $\seed == \bit0^\secpar$:

    return $\bit0^{\secpar+\ell}$

    else:

    return $G(\seed)$

    Thus, it is possible for a PRG to be secure despite having a “weak” input.

    Use a bad event.

18. Show that the following algorithm $H$ is not a secure PRG, even if $G$ is:

    $H(\seed)$:

    $A := G(\seed)$

    $B := G(\seed)$

    return $A \| B$

19. Let $G$ be a length-doubling function. Show that the following algorithm $H$ is not a secure PRG, even if $G$ is:

    $H(\seed)$:

    $A\|B := G(\seed)$

    $C\|D := G(A \oplus B)$

    return $A \| B \| C \| D$

20. Show that the following algorithm $H$ is not a secure PRG, even if $G$ is:

    $H(\seed)$:

    $A \| B := G(\seed)$

    $C \| D := G(B)$

    return $B \big\| (A\oplus C) \big\| (A \oplus D)$

    (Contrast with exercise 5.23.)

21. Let $G$ be a secure length-doubling PRG. Is the following algorithm $H$ a secure PRG? Give either a security proof or a formal attack.

    $H(\seed)$:

    $A \| B := G(\seed)$

    $C \| D := G(B)$

    return $(A \oplus B) \big\| C \big\| D$

22. Let $G$ be a secure length-doubling PRG. Is the following algorithm $H$ a secure PRG? Give either a security proof or a formal attack.

    $H(\seed)$:

    $A \| B := G(\seed)$

    $C \| D := G(A \oplus B)$

    return $A \| C \| D$

23. Let $G$ be a secure length-doubling PRG. Is the following algorithm $H$ a secure PRG? Give either a security proof or a formal attack.

    $H(\seed)$:

    $A \| B := G(\seed)$

    $C \| D := G(B)$

    return $B \big\| (A \oplus C)$

    (Contrast with exercise 5.20.)

24. Let $G$ be a secure length-doubling PRG. Is the following algorithm $H$ a secure PRG? Give either a security proof or a formal attack.

    $H(\seed)$:

    $A \| B := G(\seed)$

    $C \| D := G(A \oplus B)$

    return $(A \oplus C) \big\| (B \oplus C) \big\| D$

25. Let $G$ be a secure length-doubling PRG. Is the following algorithm $H$ a secure PRG? Give either a security proof or a formal attack.

    $H(\seed)$:

    $A := G(\seed)$

    $B := G(\bit0^\secpar)$

    return $A \oplus B$

26. Suppose $G$ and $G'$ are both secure PRGs. Is the function $H(\seed) = G(\seed) \| G'(\seed)$ necessarily a secure PRG too? Either give a security proof or a counterexample (a way to choose secure PRGs $G$ and $G'$ that cause $H$ to be insecure).

Chapter Notes

The first candidate PRG, provably secure from number-theoretic conjectures, was proposed by Blum and Micali [49]. Concurrently, Yao [220] developed the modern security definition for PRGs based on indistinguishability.

The P vs NP question is the most important unsolved question in computer science. It asks whether two classes of computational problems are equal. P refers to the set of problems that can be solved in (deterministic) polynomial time. NP refers to the set of problems whose solutions can be verified (but perhaps not discovered) in polynomial time. An accessible introduction to P, NP, and computational complexity in general can be found in the textbook of Sipser [208] or Arora and Barak [7].

1. Previous Chapter4. Modern Computational Cryptography
2. Next Chapter6. Pseudorandom Functions