Indistinguishable things are
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
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.
Previous Page Next Page