Modern Cryptography, Probabilistic Proofs and Pseudorandomness (Algorithms and Combinatorics)

Front cover......Page 1
Title......Page 3
Preface......Page 7
Organization......Page 9
Table of Contents......Page 13
1.1 Introduction......Page 17
1.2 Central Paradigms......Page 21
1.2.1 Computational Difficulty......Page 23
1.2.3 The Simulation Paradigm......Page 24
1.3.1 The Basics......Page 25
1.3.2 Pseudorandom Functions......Page 26
1.4.1 The Basics......Page 28
1.4.2 Some Variants......Page 29
1.5.1 Definitions......Page 31
1.5.2 Constructions......Page 33
1.5.3 Security Beyond Passive Attacks......Page 35
1.6 Signatures......Page 36
1.6.2 Constructions......Page 37
1.6.3 Two Variants......Page 39
1.7 Cryptographic Protocols......Page 40
1.7.1 Definitions......Page 41
1.8 Some Notes......Page 42
1.8.1 General Notes......Page 43
1.8.2 Specific Notes......Page 47
1.9 Historical Perspective......Page 49
1.10 Two Suggestions for Future Research......Page 51
1.11 Some Suggestions for Further Reading......Page 52
2.1 Introduction......Page 55
2.2.1 Definition......Page 57
2.2.2 The Role of Randomness......Page 58
2.2.3 The Power of Interactive Proofs......Page 59
2.2.4 The Interactive Proof System Hierarchy......Page 63
2.2.5 How Powerful Should the Prover Be......Page 64
2.3.1 A Sample Definition......Page 65
2.3.2 The Power of Zero-Knowledge......Page 67
2.4.1 Definition......Page 69
2.4.2 The Power of Probabilistically Checkable Proofs......Page 70
2.4.3 PCP and Approximation......Page 73
2.4.4 More on PCP Itself......Page 74
2.4.5 The Role of Randomness......Page 76
2.5.1 Restricting the Prover\'s Strategy......Page 77
2.5.3 Proofs of Knowledge......Page 80
2.6.1 Comparison Among the Various Notions......Page 81
2.6.2 The Story......Page 83
2.6.3 Open Problems......Page 87
3.1 Introduction......Page 89
3.2 The General Paradigm......Page 91
3.3 The Archetypical Case......Page 93
3.3.1 A Short Discussion......Page 94
3.3.2 Some Basic Observations......Page 95
3.3.3 Constructions......Page 98
3.3.4 Pseudorandom Functions......Page 101
3.4 Derandomization of Time-complexity Classes......Page 103
3.5 Space Pseudorandom Generators......Page 104
3.6 Special Purpose Generators......Page 108
3.6.1 Pairwise-Independence Generators......Page 109
3.6.2 Small-Bias Generators......Page 111
3.6.3 Random Walks on Expanders......Page 112
3.6.4 Samplers......Page 114
3.6.5 Dispersers, Extractors and Weak Random Sources......Page 117
3.7 Concluding Remarks......Page 119
3.7.2 Historical Perspective......Page 120
3.7.3 Open Problems......Page 122
A.l Probability Theory - Three Inequalities......Page 123
A.2.1 P, NP, and More......Page 126
A.2.2 Probabilistic Polynomial-Time......Page 127
A.2.3 Non-Uniform Polynomial-Time......Page 129
A.2.4 Oracle Machines......Page 131
A.2.5 Space Bounded Machines......Page 132
A.2.6 Average-Case Complexity......Page 133
A.3 Complexity Classes - Glossary......Page 134
A.4. 1 Encryption Schemes......Page 135
A.4.2 Digital Signatures and Message Authentication......Page 137
A.4.3 The RSA and Rabin Functions......Page 139
B.l Randomized Algorithms......Page 141
B.l.l Approx. Counting of DNF Satisfying Assignments......Page 142
B.l.2 Finding a Perfect Matching......Page 143
B.l.3 Testing Whether Polynomials Are Identical......Page 146
B.l.4 Randomized Rounding Applied to MaxSAT......Page 147
B.l.5 Primality Testing......Page 148
B.l.6 Testing Graph Connectivity via a Random Walk......Page 149
B.l.7 Finding Minimum Cuts in Graphs......Page 150
B.2.1 Reducing (Approximate) Counting to Deciding......Page 151
B.2.2 Two-sided Error Versus One-sided Error......Page 153
B.2.3 The Permanent: Worst-Case vs Average Case......Page 154
B.3.1 Testing String Equality......Page 155
B.3.2 Routing in Networks......Page 156
B.3.3 Byzantine Agreement......Page 157
B.4 Bibliographic Notes......Page 159
C.l Parallel Repetition of Interactive Proofs......Page 161
C.2 A Generic Hard-Core Predicate......Page 165
C.2. 1 A Motivating Discussion......Page 167
C.2.2 Back to the Formal Argument......Page 168
C.2.3 Improved Implementation of Algorithm A......Page 170
D Related Surveys by the Author......Page 173
Bibliography......Page 175
Index......Page 195
Back cover......Page 200