# 5: Pseudorandom Generators

- Page ID
- 7347

We have already seen that randomness is essential for cryptographic security. Following Kerckhoff’s principle, we assume that an adversary knows *everything* about our cryptographic algorithms except for the outcome of the internal random choices made when running the algorithm. Private randomness truly is the *only* resource honest parties can leverage for security in the presence of an adversary. One-time secrecy for encryption is a very demanding requirement, when we view randomness as a resource. One-time secrecy essentially requires one to use independent, uniformly random bits to mask every bit of plaintext that is sent. As a result, textbook one-time pad is usually grossly impractical for practical use.

In this chapter, we ask whether it might be beneficial to settle for a distribution of bits which is not uniform but merely “looks uniform enough.” This is exactly the idea behind **pseudorandomness**. A pseudorandom distribution is not uniform in a strict mathematical sense, but is *indistinguishable* from the uniform distribution by polynomial-time algorithms (in the sense defined in the previous chapter). Perhaps surprisingly, a relatively small amount of *truly uniform* bits can be used to generate a huge amount of *pseudorandom* bits. Pseudorandomness therefore leads to an entire new world of cryptographic possibilities, an exploration that we begin in this chapter.

- 5.1: Definition of Pseudorandom Generators
- As mentioned above, a pseudorandom distribution “looks uniform” to all polynomial-time computations. We already know of a distribution that “looks uniform” — namely, the uniform distribution itself! A more interesting case is when λ uniform bits are used to deterministically (i.e., without further use of randomness) produce λ+ℓ pseudorandom bits, for λ>0 . The process that “extends” λ bits into λ+ℓ bits is called a pseudorandom generator.

- 5.2: Application: Shorter Keys in One-Time-Series Encryption
- PRGs essentially convert a smaller amount of uniform randomness into a larger amount of good-enough-for-polynomial-time randomness. So a natural first application of PRGs is to obtain one-time-secure encryption but with keys that are shorter than the plaintext. This is the first of many acts of crypto-magic which are impossible except when restricting our focus to polynomial-time adversaries.

- 5.3: Taking the Contrapositive Point-of-View
- We just proved the statement “if G is a secure PRG, then pOTP[ G ] has one-time secrecy,” but let’s also think about the contrapositive of that statement: If the pOTP[G] scheme is not one-time secret, then G is not a secure PRG.

- 5.4: Extending the Stretch of a PRG
- In this section we will see that once you can extend a PRG a little bit, you can also extend it a lot. This is another magical feat that is possible with pseudorandomness but not with truly uniform distributions. We will demonstrate the concept by extending a PRG with stretch λ into one with stretch 2λ, but the idea can be used to increase the stretch of any PRG indefinitely (see the exercises).