Chapter 2
Pseudorandom Generators
Randomness is playing an increasingly important role in computation: It is frequently
used in the design of sequential, parallel and distributed algorithms, and it is of course
central to cryptography. Whereas it is convenient to design such algorithms making
free use of randomness, it is also desirable to minimize the usage of randomness in
real implementations. Thus, general-purpose pseudorandom generators (as defined
next) are a key ingredient in an “algorithmic tool-box” they provide an automatic
compiler of programs written with free usage of randomness into programs that make
an economical use of randomness.
Organization of this chapter. Since this is a relatively long chapter, a short
roadmap seems appropriate. In Section 2.1 we provide the basic definition of general-
purpose pseudorandom generators, and in Section 2.2 we describe their archetypical
application (which was alluded to in the former paragraph). In Section 2.3 we pro-
vide a wider perspective on the notion of computational indistinguishability that
underlies the basic definition, and in Section 2.4 we justify the little concern (shown
in Section 2.1) regarding the specific stretch function. In Section 2.5 we address the
existence of general-purpose pseudorandom generators. In Section 2.6 we motivate
and discuss a non-uniform version of computational indistinguishability. We con-
clude by reviewing other variants and reflecting on various conceptual aspects of the
notions discussed in this chapter (see Sections 2.7 and 2.8, resp.).
2.1 The Basic Definition
Loosely speaking, general-purpose pseudorandom generators are efficient determin-
istic programs that expand short randomly selected seeds into longer pseudoran-
dom bit sequences, where the latter are defined as computationally indistinguishable
from truly random sequences by any efficient algorithm. Identifying efficiency with
polynomial-time operation, this means that the generator (being a fixed algorithm)
works within some fixed polynomial-time, whereas the distinguisher may be any al-
gorithm that runs in polynomial-time. Thus, the distinguisher is potentially more
Previous Page Next Page