Chapter 2

General-Purpose

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

11

http://dx.doi.org/10.1090/ulect/055/02