x PREFACE

supposed to fool (i.e., the algorithms with respect to which the computational indis-

tinguishability requirement should hold); and the resources that the generators are

allowed to use (i.e., their own computational complexity).

The archetypical case of pseudorandom generators refers to efficient generators

that fool any feasible procedure; that is, the potential distinguisher is any proba-

bilistic polynomial-time algorithm, which may be more complex than the generator

itself (which, in turn, has time-complexity bounded by a fixed polynomial). These

generators are called general-purpose, because their output can be safely used in any

efficient application. Such (general-purpose) pseudorandom generators exist if and

only if there exist functions (called one-way functions) that are easy to evaluate but

hard to invert.

In contrast to such (general-purpose) pseudorandom generators, for the purpose

of derandomization (i.e., converting randomized algorithms into corresponding de-

terministic ones), a relaxed definition of pseudorandom generators suffices. In partic-

ular, for such a purpose, one may use pseudorandom generators that are somewhat

more complex than the potential distinguisher (which represents a randomized al-

gorithm to be derandomized). Following this approach, adequate pseudorandom

generators yield a full derandomization of probabilistic polynomial-time algorithms

(e.g., BPP = P), and such generators can be constructed based on the assump-

tion that some exponential-time solvable problems (i.e., problems in E) have no

sub-exponential size circuits.

Indeed, both the general-purpose pseudorandom generators and the aforemen-

tioned “derandomizers” demonstrate that randomness and computational difficulty

are related. This trade-off is not surprising in light of the fact that the very defi-

nition of pseudorandomness refers to computational difficulty (i.e., the difficulty of

distinguishing the pseudorandom distribution from a truly random one).

Finally, we mention that it is also beneficial to consider pseudorandom genera-

tors that fool space-bounded distinguishers and generators that exhibit some limited

random behavior (e.g., outputting a pairwise independent or a small-bias sequence).

Such (special-purpose) pseudorandom generators can be constructed without relying

on any computational complexity assumptions, because the behavior of the corre-

sponding (limited) distinguishers can be analyzed even at the current historical time.

Nevertheless, such (special-purpose) pseudorandom generators offer numerous appli-

cations.

Note: The study of pseudorandom generators is part of complexity theory(cf.e.g.,[24]),

and some basic familiarity with complexity theory will be assumed in the current

text. In fact, the current primer is an abbreviated (and somewhat revised) version

of [24, Chap. 8]. Nevertheless, we believe that there are merits to providing a sep-

arate treatment of the theory of pseudorandomness, since this theory is of natural

interest to various branches of mathematics and science. In particular, we hope to

reach readers that may not have a general interest in complexity theory at large

and/or do not wish to purchase a book on the latter topic.

Acknowledgments. We are grateful to Alina Arbitman and Ron Rothblum for

their comments and suggestions regarding this primer.

Oded Goldreich

Weizmann Institute of Science