# 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: Definitions
- 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: Pseudorandom Generators in Practice
- 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.