Contents
Preface ix
1 Introduction 1
1.1 The Third Theory of Randomness . . . . . . . . . . . . . . . . . . . . 2
1.2 Organization of the Primer . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Standard Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 The General Paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4.1 Three fundamental aspects . . . . . . . . . . . . . . . . . . . . 6
1.4.2 Notational conventions . . . . . . . . . . . . . . . . . . . . . . . 7
1.4.3 Some instantiations of the general paradigm . . . . . . . . . . . 8
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 General-Purpose Pseudorandom Generators 11
2.1 The Basic Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 The Archetypical Application . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Computational Indistinguishability . . . . . . . . . . . . . . . . . . . . 15
2.3.1 The general formulation . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Relation to statistical closeness . . . . . . . . . . . . . . . . . . 16
2.3.3 Indistinguishability by multiple samples . . . . . . . . . . . . . 16
2.4 Amplifying the Stretch Function . . . . . . . . . . . . . . . . . . . . . 19
2.5 Constructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5.1 Background: one-way functions . . . . . . . . . . . . . . . . . . 21
2.5.2 A simple construction . . . . . . . . . . . . . . . . . . . . . . . 23
2.5.3 An alternative presentation . . . . . . . . . . . . . . . . . . . . 23
2.5.4 A necessary and sufficient condition . . . . . . . . . . . . . . . 24
2.6 Non-uniformly Strong Pseudorandom Generators . . . . . . . . . . . . 25
2.7 Stronger (Uniform-Complexity) Notions . . . . . . . . . . . . . . . . . 27
2.7.1 Fooling stronger distinguishers . . . . . . . . . . . . . . . . . . 27
2.7.2 Pseudorandom functions . . . . . . . . . . . . . . . . . . . . . . 27
2.8 Conceptual Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
v
9
Previous Page Next Page