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 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 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.