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.