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

You can start by putting the DO NOT DISTURB sign. Cay, in Desert Hearts (1985). The interplay between randomness and computation is one of the most fas­ cinating scientific phenomena uncovered in the last couple of decades. This interplay is at the heart of modern cryptography and plays a fundamental role in complexity theory at large. Specifically, the interplay of randomness and computation is pivotal to several intriguing notions of probabilistic proof systems and is the focal of the computational approach to randomness. This book provides an introduction to these three, somewhat interwoven domains (i.e., cryptography, proofs and randomness). Modern Cryptography. Whereas classical cryptography was confined to the art of designing and breaking encryption schemes (or "secrecy codes"), Modern Cryptography is concerned with the rigorous analysis of any system which should withstand malicious attempts to abuse it. We emphasize two aspects of the transition from classical to modern cryptography: ( 1) the wide­ ning of scope from one specific task to an utmost wide general class of tasks; and (2) the move from an engineering-art which strives on ad-hoc tricks to a scientific discipline based on rigorous approaches and techniques. 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 You can start by putting the DO NOT DISTURB sign. Cay, in Desert Hearts (1985). The interplay between randomness and computation is one of the most fasƯ cinating scientific phenomena uncovered in the last couple of decades. This interplay is at the heart of modern cryptography and plays a fundamental role in complexity theory at large. Specifically, the interplay of randomness and computation is pivotal to several intriguing notions of probabilistic proof systems and is the focal of the computational approach to randomness. This book provides an introduction to these three, somewhat interwoven domains (i.e., cryptography, proofs and randomness). Modern Cryptography. Whereas classical cryptography was confined to the art of designing and breaking encryption schemes (or "secrecy codes"), Modern Cryptography is concerned with the rigorous analysis of any system which should withstand malicious attempts to abuse it. We emphasize two aspects of the transition from classical to modern cryptography: (1) the wideƯ ning of scope from one specific task to an utmost wide general class of tasks; and (2) the move from an engineering-art which strives on ad-hoc tricks to a scientific discipline based on rigorous approaches and techniques The book focuses on three related areas in the theory of computation. The areas are modern cryptography, the study of probabilistic proof systems, and the theory of computational pseudorandomness. The common theme is the interplay between randomness and computation. The book offers an introduction and extensive survey to each of these areas, presenting both the basic notions and the most important (sometimes advanced) results. The presentation is focused on the essentials and does not elaborate on details. In some cases it offers a novel and illuminating perspective. The reader may obtain from the book 1. A clear view of what each of these areas is all above. 2. Knowledge of the basic important notions and results in each area. 3. New insights into each of these areas. It is believed that the book may thus be useful both to a beginner (who has only some background in the theory of computing), and an expert in any of these areas.

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.

Preface Chapter 1: The Foundations of Modern Cryptography Chapter 2: Probabilistic Proof Systems Chapter 3: Pseudorandom Generators Appendix A: Background on Randomness and Computation Appendix B: Randomized Computations Appendix C: Notes on two proofs Appendix D: Related Surveys by the Author Bibliography.