| Description |
1 online resource |
| Contents |
1.1.1. Encryption Schemes 2 -- 1.1.2. Pseudorandom Generators 3 -- 1.1.3. Digital Signatures 4 -- 1.1.4. Fault-Tolerant Protocols and Zero-Knowledge Proofs 6 -- 1.2. Some Background from Probability Theory 8 -- 1.2.1. Notational Conventions 8 -- 1.2.2. Three Inequalities 9 -- 1.3. Computational Model 12 -- 1.3.1. P, NP, and NP-Completeness 12 -- 1.3.2. Probabilistic Polynomial Time 13 -- 1.3.3. Non-Uniform Polynomial Time 16 -- 1.3.4. Intractability Assumptions 19 -- 1.3.5. Oracle Machines 20 -- 1.4. Motivation to the Rigorous Treatment 21 -- 1.4.1. Need for a Rigorous Treatment 21 -- 1.4.2. Practical Consequences of the Rigorous Treatment 23 -- 1.4.3. Tendency to Be Conservative 24 -- 1.5.1. Historical Notes 25 -- 1.5.3. Open Problems 27 -- 2 Computational Difficulty 30 -- 2.1. One-Way Functions: Motivation 31 -- 2.2. One-Way Functions: Definitions 32 -- 2.2.1. Strong One-Way Functions 32 -- 2.2.2. Weak One-Way Functions 35 -- 2.2.3. Two Useful Length Conventions 35 -- 2.2.4. Candidates for One-Way Functions 40 -- 2.2.5. Non-Uniformly One-Way Functions 41 -- 2.3. Weak One-Way Functions Imply Strong Ones 43 -- 2.3.1. Construction and Its Analysis (Proof of Theorem 2.3.2) 44 -- 2.3.2. Illustration by a Toy Example 48 -- 2.4. One-Way Functions: Variations 51 -- 2.4.1. Universal One-Way Function 52 -- 2.4.2. One-Way Functions as Collections 53 -- 2.4.3. Examples of One-Way Collections 55 -- 2.4.4. Trapdoor One-Way Permutations 58 -- 2.4.5. Claw-Free Functions 60 -- 2.4.6. On Proposing Candidates 63 -- 2.5. Hard-Core Predicates 64 -- 2.5.2. Hard-Core Predicates for Any One-Way Function 65 -- 2.5.3. Hard-Core Functions 74 -- 2.6. Efficient Amplification of One-Way Functions 78 -- 2.6.1. Construction 80 -- 2.6.2. Analysis 81 -- 2.7.1. Historical Notes 89 -- 3 Pseudorandom Generators 101 -- 3.1. Motivating Discussion 102 -- 3.1.1. Computational Approaches to Randomness 102 -- 3.1.2. A Rigorous Approach to Pseudorandom Generators 103 -- 3.2. Computational Indistinguishability 103 -- 3.2.2. Relation to Statistical Closeness 106 -- 3.2.3. Indistinguishability by Repeated Experiments 107 -- 3.2.4. Indistinguishability by Circuits 111 -- 3.2.5. Pseudorandom Ensembles 112 -- 3.3. Definitions of Pseudorandom Generators 112 -- 3.3.1. Standard Definition of Pseudorandom Generators 113 -- 3.3.2. Increasing the Expansion Factor 114 -- 3.3.3. Variable-Output Pseudorandom Generators 118 -- 3.3.4. Applicability of Pseudorandom Generators 119 -- 3.3.5. Pseudorandomness and Unpredictability 119 -- 3.3.6. Pseudorandom Generators Imply One-Way Functions 123 -- 3.4. Constructions Based on One-Way Permutations 124 -- 3.4.1. Construction Based on a Single Permutation 124 -- 3.4.2. Construction Based on Collections of Permutations 131 -- 3.4.3. Using Hard-Core Functions Rather than Predicates 134 -- 3.5. Constructions Based on One-Way Functions 135 -- 3.5.1. Using 1-1 One-Way Functions 135 -- 3.5.2. Using Regular One-Way Functions 141 -- 3.5.3. Going Beyond Regular One-Way Functions 147 -- 3.6. Pseudorandom Functions 148 -- 3.6.3. Applications: A General Methodology 157 -- 3.7. Pseudorandom Permutations 164 -- 3.8.1. Historical Notes 169 -- 4 Zero-Knowledge Proof Systems 184 -- 4.1. Zero-Knowledge Proofs: Motivation 185 -- 4.1.1. Notion of a Proof 187 -- 4.1.2. Gaining Knowledge 189 -- 4.2. Interactive Proof Systems 190 -- 4.2.2. An Example (Graph Non-Isomorphism in IP) 195 -- 4.2.3. Structure of the Class IP 198 -- 4.2.4. Augmentation of the Model 199 -- 4.3. Zero-Knowledge Proofs: Definitions 200 -- 4.3.1. Perfect and Computational Zero-Knowledge 200 -- 4.3.2. An Example (Graph Isomorphism in PZK) 207 -- 4.3.3. Zero-Knowledge with Respect to Auxiliary Inputs 213 -- 4.3.4. Sequential Composition ofh Zero-Knowledge Proofs 216 -- 4.4. Zero-Knowledge Proofs for NP 223 -- 4.4.1. Commitment Schemes 223 -- 4.4.2. Zero-Knowledge Proof of Graph Coloring 228 -- 4.4.3. General Result and Some Applications 240 -- 4.4.4. Second-Level Considerations 243 -- 4.5. Negative Results 246 -- 4.5.1. On the Importance of Interaction and Randomness 247 -- 4.5.2. Limitations of Unconditional Results 248 -- 4.5.3. Limitations of Statistical ZK Proofs 250 -- 4.5.4. Zero-Knowledge and Parallel Composition 251 -- 4.6. Witness Indistinguishability and Hiding 254 -- 4.6.2. Parallel Composition 258 -- 4.7. Proofs of Knowledge 262 -- 4.7.2. Reducing the Knowledge Error 267 -- 4.7.3. Zero-Knowledge Proofs of Knowledge for NP 268 -- 4.7.5. Proofs of Identity (Identification Schemes) 270 -- 4.7.6. Strong Proofs of Knowledge 274 -- 4.8. Computationally Sound Proofs (Arguments) 277 -- 4.8.2. Perfectly Hiding Commitment Schemes 278 -- 4.8.3. Perfect Zero-Knowledge Arguments for NP 284 -- 4.8.4. Arguments of Poly-Logarithmic Efficiency 286 -- 4.9. Constant-Round Zero-Knowledge Proofs 288 -- 4.9.1. Using Commitment Schemes with Perfect Secrecy 289 -- 4.9.2. Bounding the Power of Cheating Provers 294 -- 4.10. Non-Interactive Zero-Knowledge Proofs 298 -- 4.10.3. Extensions 306 -- 4.11. Multi-Prover Zero-Knowledge Proofs 311 -- 4.11.2. Two-Sender Commitment Schemes 313 -- 4.11.3. Perfect Zero-Knowledge for NP 317 -- 4.12.1. Historical Notes 320 -- Appendix A Background in Computational Number Theory 331 -- A.1. Prime Numbers 331 -- A.1.1. Quadratic Residues Modulo a Prime 331 -- A.1.2. Extracting Square Roots Modulo a Prime 332 -- A.1.3. Primality Testers 332 -- A.1.4. On Uniform Selection of Primes 333 -- A.2. Composite Numbers 334 -- A.2.1. Quadratic Residues Modulo a Composite 335 -- A.2.2. Extracting Square Roots Modulo a Composite 335 -- A.2.3. Legendre and Jacobi Symbols 336 -- A.2.4. Blum Integers and Their Quadratic-Residue Structure 337 -- Appendix B Brief Outline of Volume 338 -- B.1. Encryption: Brief Summary 338 -- B.1.3. Beyond Eavesdropping Security 343 -- B.2. Signatures: Brief Summary 345 -- B.3. Cryptographic Protocols: Brief Summary 350 |
| Summary |
Cryptography is concerned with the conceptualization, definition and construction of computing systems that address security concerns. The design of cryptographic systems must be based on firm foundations. This book presents a rigorous and systematic treatment of the foundational issues: defining cryptographic tasks and solving new cryptographic problems using existing tools. It focuses on the basic mathematical tools: computational difficulty (one-way functions), pseudorandomness and zero-knowledge proofs. The emphasis is on the clarification of fundamental concepts and on demonstrating the feasibility of solving cryptographic problems, rather than on describing ad-hoc approaches. The book is suitable for use in a graduate course on cryptography and as a reference book for experts. The author assumes basic familiarity with the design and analysis of algorithms; some knowledge of complexity theory and probability is also useful |
| Notes |
Title from title screen |
| Bibliography |
Includes bibliographical references and indexes |
| Subject |
Coding theory.
|
|
Cryptography -- Mathematics
|
|
BUSINESS & ECONOMICS -- Business Writing.
|
|
Coding theory
|
|
Cryptography -- Mathematics
|
|
Kryptologie
|
| Form |
Electronic book
|
| ISBN |
1280430060 |
|
9781280430060 |
|
0511546890 |
|
9780511546891 |
|
9781461949176 |
|
1461949173 |
|
