Cryptography Reference
In-Depth Information
fundamental concept with lots of practical applications (particularly in the field of
cryptography).
3.1.2. A Rigorous Approach to Pseudorandom Generators
The approach to pseudorandom generators presented in this topic stands in contrast to
the heuristic approach that is still common in discussions concerning “pseudorandom
generators” that are being used in real computers. The heuristic approach considers
“pseudorandom generators” as programs that produce bit sequences that can “pass”
some specific
statistical tests. The choices of statistical tests to which these programs
are subjected are quite arbitrary and lack any systematic foundation. Furthermore, it is
possible to construct efficient statistical tests that will foil the “pseudorandom genera-
tors” commonly used in practice (and in particular will distinguish their output from a
uniformly chosen string of equal length). Consequently, before using a “pseudorandom
generator” in a new application that requires “random” sequences, extensive tests have
to be conducted in order to determine whether or not the behavior of the application
when using the “pseudorandom generator” will be the same as its behavior when using
a “true source of randomness.” Any modification of the application will require a new
comparison of the “pseudorandom generator” against the “random source,” because
the non-randomness of the “pseudorandom generator” may adversely affect the modi-
fied application (even if it did not affect the original application). Things become even
worse with respect to cryptographic applications, because in such cases an application
is fully determined only after the adversary is fixed. That is, one cannot
test
the effect of
the “pseudorandom generator” on the performance of a yet-unspecified adversary, and
it is unreasonable to assume that the adversary is going to employ a specific strategy
known to the designer. Thus, using such a “pseudorandom generator” for cryptographic
purposes is highly risky.
In contrast, the concept of pseudorandom generators presented herein is a robust one:
By definition, these pseudorandom generators produce sequences that look random to
any efficient observer. It follows that the output of a pseudorandom generator can
be used instead of “random sequences” in any efficient application requiring such
(i.e., “random”) sequences. In particular, no efficient adversary can capitalize on the
replacement of “truly random sequences” by pseudorandom ones.
3.2. Computational Indistinguishability
As stated earlier, the concept of computational indistinguishability is the basis for our
definition of pseudorandomness. Thus, we start with a general definition and discussion
of this fundamental concept.
The concept of efficient computation leads naturally to a new kind of equivalence be-
tween objects:
Objects are considered to be computationally equivalent if they cannot
be differentiated by any efficient procedure
. We note that considering
indistinguish-
able objects
as equivalent is one of the basic paradigms of both science and real-life
