Preface

Indistinguishable things are

identical.1

G.W. Leibniz (1646–1714)

This primer to the theory of pseudorandomness presents a fresh look at the question

of randomness, which arises from a complexity theoretic approach to randomness.

The crux of this (complexity theoretic) approach is the postulate that a distribution

is random (or rather pseudorandom) if it cannot be distinguished from the uniform

distribution by any efficient procedure. Thus, (pseudo)randomness is not an inherent

property of an object, but is rather subjective to the observer.

At the extreme, this approach says that the question of whether the world is

actually deterministic or allows for some free choice (which may be viewed as a source

of randomness) is irrelevant. What matters is how the world looks to us and to various

computationally bounded devices. That is, if some phenomenon looks random, then

we may treat it as if it is random. Likewise, if we can generate sequences that cannot

be distinguished from the uniform distribution by any efficient procedure, then we

can use these sequences in any efficient randomized application instead of the ideal

coin tosses that are postulated in the design of this application.

The pivot of the foregoing approach is the notion of computational indistinguisha-

bility, which refers to pairs of distributions that cannot be distinguished by efficient

procedures. The most fundamental incarnation of this notion associates efficient pro-

cedures with polynomial-time algorithms, but other incarnations that restrict atten-

tion to different classes of distinguishing procedures also lead to important insights.

Likewise, the effective generation of pseudorandom objects, which is of major con-

cern, is actually a general paradigm with numerous useful incarnations (which differ

in the computational complexity limitations imposed on the generation process).

Following the foregoing principles, we briefly outline some of the key elements

of the theory of pseudorandomness. Indeed, the key concept is that of a pseudo-

random generator, which is an efficient deterministic procedure that stretches short

random seeds into longer pseudorandom sequences. Thus, a generic formulation

of pseudorandom generators consists of specifying three fundamental aspects – the

stretch measure of the generators; the class of distinguishers that the generators are

1This

is Leibniz’s Principle of Identity of Indiscernibles. Leibniz admits that counterexamples to

this principle are conceivable but will not occur in real life because God is much too benevolent. We

thus believe that he would have agreed to the theme of this text, which asserts that indistinguishable

things should be considered as if they were identical.

ix