Cryptography Reference
In-Depth Information
that this definition of pseudorandom generators is equivalent to the definition of Blum
and Micali [36].
Generalizations of Yao's result, by which one-way permutations imply pseudoran-
dom generators, were published by Levin [150] and by Goldreich, Krawczyk, and
Luby [108], culminating with the result of Hastad, Impagliazzo, Levin, and Luby [129]
asserting that pseudorandom generators exist if and only if one-way functions exist.
The constructions presented in Section 3.5 follow those ideas [108, 129]. These con-
structions make extensive use of universal 2 hashing functions, which were introduced
by Carter and Wegman [49] and were first used in complexity theory by Sipser [201].
Simple pseudorandom generators based on specific intractability assumptions are
presented in [36, 32, 5, 208, 141]. In particular, [5] presents pseudorandom gener-
ators based on the intractability of factoring, whereas [141] presents pseudorandom
generators based on the intractability of various discrete-logarithm problems (see
Section 2.4.3.4). In both cases, the main technical step is the construction of hard-
core predicates for the corresponding collections of one-way permutations.
Pseudorandom functions were introduced and investigated by Goldreich,
Goldwasser, and Micali [102]. In particular, the construction of pseudorandom func-
tions based on pseudorandom generators is taken from [102]. First applications of
pseudorandom functions were given in [103, 89, 90], and the list of applications has
been rapidly growing since.
Pseudorandom permutations were defined and constructed by Luby and Rackoff
[156], and our presentation follows their work.
The hybrid method originated from the work of Goldwasser and Micali [123]. The
terminology was suggested by Leonid Levin.
3.8.2. Suggestions for Further Reading
A wider perspective on pseudorandomness is offered by Goldreich [97]. It surveys
various notions of pseudorandom generators, viewing the one discussed in this chapter
as an archetypical instantiation of a general paradigm. The general paradigm amounts
to considering as pseudorandom those distributions that cannot be distinguished from
the uniform distribution by certain types of resource-bounded distinguishers. The com-
plexity of the generator itself, as well as its stretch function, can vary as well (rather than
being polynomial-time and polynomially bounded, respectively, as here). Starting with
the general paradigm, Chapter 3 of [97] surveys the archetypical case of pseudoran-
dom generators (considered here), as well as generators withstanding space-bounded
distinguishers, the de-randomization of complexity classes such as
BPP
, and various
special-purpose generators. (Readers interested in Kolmogorov complexity are referred
elsewhere [152].)
Proposition 3.2.3 presents a pair of ensembles that are computationally indistin-
guishable, although they are statistically far apart. This is shown without making
any intractability assumptions, but one of the two ensembles is not constructible in
polynomial time. This situation is unavoidable, because the existence of a pair of
polynomial-time-constructible ensembles having such properties (i.e., being computa-
tionally indistinguishable and yet statistically far apart) implies the existence of one-way
Search WWH ::




Custom Search