Modern Cryptography, Probabilistic Proofs and Pseudorandomness

✍ Scribed by Oded Goldreich

• Publisher: Springer
• Year: 1998
• Tongue: English
• Leaves: 202
• Series: Algorithms and Combinatorics
• Edition: 1
• Category: Library

✦ Synopsis

Cryptography is one of the most active areas in current mathematics research and applications. This book focuses on cryptography along with two related areas: the study of probabilistic proof systems, and the theory of computational pseudorandomness. Following a common theme that explores the interplay between randomness and computation, the important notions in each field are covered, as well as novel ideas and insights.

✦ Table of Contents

Front cover
......Page 1
Preface......Page 9
Organization......Page 11
Table of Contents......Page 15
1.1 Introduction......Page 19
1.2 Central Paradigms......Page 23
1.2.1 Computational Difficulty......Page 25
1.2.3 The Simulation Paradigm......Page 26
1.3.1 The Basics......Page 27
1.3.2 Pseudorandom Functions......Page 28
1.4.1 The Basics......Page 30
1.4.2 Some Variants......Page 31
1.5.1 Definitions......Page 33
1.5.2 Constructions......Page 35
1.5.3 Security Beyond Passive Attacks......Page 37
1.6 Signatures......Page 38
1.6.2 Constructions......Page 39
1.6.3 Two Variants......Page 41
1.7 Cryptographic Protocols......Page 42
1.7.1 Definitions......Page 43
1.8 Some Notes......Page 44
1.8.1 General Notes......Page 45
1.8.2 Specific Notes......Page 49
1.9 Historical Perspective......Page 51
1.10 Two Suggestions for Future Research......Page 53
1.11 Some Suggestions for Further Reading......Page 54
2.1 Introduction......Page 57
2.2.1 Definition......Page 59
2.2.2 The Role of Randomness......Page 60
2.2.3 The Power of Interactive Proofs......Page 61
2.2.4 The Interactive Proof System Hierarchy......Page 65
2.2.5 How Powerful Should the Prover Be......Page 66
2.3.1 A Sample Definition......Page 67
2.3.2 The Power of Zero-Knowledge......Page 69
2.4.1 Definition......Page 71
2.4.2 The Power of Probabilistically Checkable Proofs......Page 72
2.4.3 PCP and Approximation......Page 75
2.4.4 More on PCP Itself......Page 76
2.4.5 The Role of Randomness......Page 78
2.5.1 Restricting the Prover's Strategy......Page 79
2.5.3 Proofs of Knowledge......Page 82
2.6.1 Comparison Among the Various Notions......Page 83
2.6.2 The Story......Page 85
2.6.3 Open Problems......Page 89
3.1 Introduction......Page 91
3.2 The General Paradigm......Page 93
3.3 The Archetypical Case......Page 95
3.3.1 A Short Discussion......Page 96
3.3.2 Some Basic Observations......Page 97
3.3.3 Constructions......Page 100
3.3.4 Pseudorandom Functions......Page 103
3.4 Derandomization of Time-complexity Classes......Page 105
3.5 Space Pseudorandom Generators......Page 106
3.6 Special Purpose Generators......Page 110
3.6.1 Pairwise-Independence Generators......Page 111
3.6.2 Small-Bias Generators......Page 113
3.6.3 Random Walks on Expanders......Page 114
3.6.4 Samplers......Page 116
3.6.5 Dispersers, Extractors and Weak Random Sources......Page 119
3.7 Concluding Remarks......Page 121
3.7.2 Historical Perspective......Page 122
3.7.3 Open Problems......Page 124
A.l Probability Theory - Three Inequalities......Page 125
A.2.1 P, NP, and More......Page 128
A.2.2 Probabilistic Polynomial-Time......Page 129
A.2.3 Non-Uniform Polynomial-Time......Page 131
A.2.4 Oracle Machines......Page 133
A.2.5 Space Bounded Machines......Page 134
A.2.6 Average-Case Complexity......Page 135
A.3 Complexity Classes - Glossary......Page 136
A.4. 1 Encryption Schemes......Page 137
A.4.2 Digital Signatures and Message Authentication......Page 139
A.4.3 The RSA and Rabin Functions......Page 141
B.l Randomized Algorithms......Page 143
B.l.l Approx. Counting of DNF Satisfying Assignments......Page 144
B.l.2 Finding a Perfect Matching......Page 145
B.l.3 Testing Whether Polynomials Are Identical......Page 148
B.l.4 Randomized Rounding Applied to MaxSAT......Page 149
B.l.5 Primality Testing......Page 150
B.l.6 Testing Graph Connectivity via a Random Walk......Page 151
B.l.7 Finding Minimum Cuts in Graphs......Page 152
B.2.1 Reducing (Approximate) Counting to Deciding......Page 153
B.2.2 Two-sided Error Versus One-sided Error......Page 155
B.2.3 The Permanent: Worst-Case vs Average Case......Page 156
B.3.1 Testing String Equality......Page 157
B.3.2 Routing in Networks......Page 158
B.3.3 Byzantine Agreement......Page 159
B.4 Bibliographic Notes......Page 161
C.l Parallel Repetition of Interactive Proofs......Page 163
C.2 A Generic Hard-Core Predicate......Page 167
C.2. 1 A Motivating Discussion......Page 169
C.2.2 Back to the Formal Argument......Page 170
C.2.3 Improved Implementation of Algorithm A......Page 172
D Related Surveys by the Author......Page 175
Bibliography......Page 177
Index......Page 197
back cover......Page 202