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-
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
Previous Page Next Page