Cryptography Reference
In-Depth Information
CHAPTER
3
Pseudorandom Generators
In this chapter we discuss pseudorandom generators. Loosely speaking, these are ef-
ficient deterministic programs that expand short, randomly selected seeds into much
longer “pseudorandom” bit sequences (see illustration in Figure 3.1). Pseudorandom se-
quences are defined as computationally indistinguishable from truly random sequences
by efficient algorithms. Hence the notion of computational indistinguishability (i.e.,
indistinguishability by efficient procedures) plays a pivotal role in our discussion. Fur-
thermore, the notion of computational indistinguishability plays a key role also in sub-
sequent chapters, in particular in the discussions of secure encryption, zero-knowledge
proofs, and cryptographic protocols.
The theory of pseudorandomness is also applied to functions, resulting in the notion
of pseudorandom functions, which is a useful tool for many cryptographic applications.
In addition to definitions of pseudorandom distributions, pseudorandom generators,
and pseudorandom functions, this chapter contains constructions of pseudorandom
generators (and pseudorandom functions) based on various types of one-way functions.
In particular, very simple and efficient pseudorandom generators are constructed based
on the existence of one-way permutations. We highlight the
hybrid technique
, which
plays a central role in many of the proofs. (For the first use and further discussion of
this technique, see Section 3.2.3.)
Organization.
Basic discussions, definitions, and constructions of pseudorandom gen-
erators appear in Sections 3.1-3.4: We start with a motivating discussion (Section 3.1),
proceed with a general definition of computational indistinguishability (Section 3.2),
next present and discuss definitions of pseudorandom generators (Section 3.3), and fi-
nally present some simple constructions (Section 3.4). More general constructions are
discussed in Section 3.5. Pseudorandom functions are defined and constructed (based
on any pseudorandom generator) in Section 3.6. Pseudorandom permutations are dis-
cussed in Section 3.7.
Teaching Tip.
The
hybrid technique
, first used to show that computational indistin-
guishability is preserved under multiple samples (Section 3.2.3), plays an important
