Cryptography Reference
In-Depth Information
functions [93]. Other abstract results regarding the notion of computational indistin-
guishability appear in [111, 119].
Combining Theorem 2.5.6 and Construction 3.4.7, we obtain a generic (black-box)
construction of a pseudorandom generator based on any one-way permutation that
outputs a logarithmic number of bits per each application of the one-way permutation.
Elsewhere [88] it is shown that as far as generic (black-box) constructions go, this is
the best performance (i.e., number of output bits per an application of the one-way
permutation) that one can expect.
Section 3.5 falls short of presenting the construction of Hastad et al. [129], not to
mention proving its validity. Unfortunately, the proof of this fundamental theorem,
asserting that pseudorandom generators exist if one-way functions exist, is too com-
plicated to fit into this topic. The interested reader is thus referred to the original paper
[129].
Alternative constructions of pseudorandom functions were given in [172]. Con-
structions of unbounded-input (and generalized) pseudorandom functions based on
(ordinary) pseudorandom functions are discussed in [14].
An alternative presentation of the construction of pseudorandom permutations (based
on pseudorandom functions) can be found in [173]. That alternative distills the real
structure of the proof and provides related results.
Pseudorandom generators and functions have many applications to cryptography;
some of them will be presented in Volume 2 of this topic (e.g., signatures and
encryption).
Using Sources of Imperfect Randomness.
Pseudorandom generators and functions
enable us to expand randomness (or pseudorandomness), but they do not allow us to
“generate randomness (or pseudorandomness) deterministically.” In fact, we cannot
expect to have an efficient deterministic program that generates pseudorandom objects
(because the very same program may be employed by the distinguisher). In order to
employ a pseudorandom generator (or function), we need to start with a random seed,
and the question is where to obtain it. The answer is that this random seed (or something
that appears so) can be obtained by sampling some physical phenomena. Indeed, such
samples may not be uniformly distributed over the set of strings (of a specific length),
yet if they contain enough entropy, then almost perfect randomness can be (efficiently)
extracted from them. Methods for such randomness extraction will be discussed in the
third volume of this topic.
The Random Oracle Methodology.
In contrast to the methodology discussed in
Section 3.6.3, the
Random Oracle Model
refers to a setting in which the adversary
has
direct
access to a random oracle (that is later “implemented” by a function, the
description of which is given also to the adversary). The
Random Oracle Methodol-
ogy
[80, 21] consists of first designing an
ideal
system in which all parties (including
the adversary) have oracle access to a truly random function, and then replacing the
random oracle by a “good cryptographic hashing function,” providing all parties (in-
cluding the adversary) the succinct description of this function. Recall that, in contrast,
the methodology of Section 3.6.3 refers to a situation in which the adversary does not
