Cryptography Reference
In-Depth Information
output sequence
seed
Gen
?
a truly random sequence
Figure 3.1: Pseudorandom generators: an illustration.
role in many of the proofs that refer to computational indistinguishability. Thus, in
case you choose to skip this specific proof, do incorporate a discussion of the hybrid
technique in the first place you use it.
3.1. Motivating Discussion
The nature of randomness has puzzled thinkers for centuries. We believe that the notion
of computation, and in particular that of efficient computation, provides a good basis
for understanding the nature of randomness.
3.1.1. Computational Approaches to Randomness
One computational approach to randomness was initiated by Solomonov and
Kolmogorov in the early 1960s (and rediscovered by Chaitin in the early 1970s). This
approach is “ontological” in nature. Loosely speaking, a string s is considered
Kolmogorov-random if its length (i.e.,
) equals the length of the shortest program pro-
ducing s . This shortest program can be considered the “simplest” “explanation” for the
phenomenon described by the string s . Hence the string s is considered Kolmogorov-
random if it does not possess a “simple” explanation (i.e., an explanation that is sub-
stantially shorter than
|
s
|
). We stress that one cannot determine whether or not a given
string is Kolmogorov-random (and, more generally, Kolmogorov complexity is a func-
tion that cannot be computed). Furthermore, this approach seems to have no application
to the issue of “pseudorandom generators.”
An alternative computational approach to randomness is presented in the rest of this
chapter. This approach was initiated in the early 1980s. In contrast to the approach
of Kolmogorov, this new approach is behavioristic in nature. Instead of considering
the “explanation” for a phenomenon, we consider the phenomenon's effect on the
environment. Loosely speaking, a string is considered pseudorandom if no efficient
observer can distinguish it from a uniformly chosen string of the same length. The
underlying postulate is that objects that cannot be differentiated by efficient proce-
dures are considered equivalent, although they may be very different in nature (e.g.,
can have fundamentally different (Kolmogorov) complexities). Furthermore, the new
approach naturally leads to the concept of a pseudorandom generator, which is a
|
s
|
Search WWH ::




Custom Search