| |
| |
| List of Figures | |
| |
| |
| Preface | |
| |
| |
| |
| Introduction | |
| |
| |
| |
| Cryptography: Main Topics | |
| |
| |
| |
| Encryption Schemes | |
| |
| |
| |
| Pseudorandom Generators | |
| |
| |
| |
| Digital Signatures | |
| |
| |
| |
| Fault-Tolerant Protocols and Zero-Knowledge Proofs | |
| |
| |
| |
| Some Background from Probability Theory | |
| |
| |
| |
| Notational Conventions | |
| |
| |
| |
| Three Inequalities | |
| |
| |
| |
| The Computational Model | |
| |
| |
| |
| P, NP, and NP-Completeness | |
| |
| |
| |
| Probabilistic Polynomial Time | |
| |
| |
| |
| Non-Uniform Polynomial Time | |
| |
| |
| |
| Intractability Assumptions | |
| |
| |
| |
| Oracle Machines | |
| |
| |
| |
| Motivation to the Rigorous Treatment | |
| |
| |
| |
| The Need for a Rigorous Treatment | |
| |
| |
| |
| Practical Consequences of the Rigorous Treatment | |
| |
| |
| |
| The Tendency to Be Conservative | |
| |
| |
| |
| Miscellaneous | |
| |
| |
| |
| Historical Notes | |
| |
| |
| |
| Suggestions for Further Reading | |
| |
| |
| |
| Open Problems | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Computational Difficulty | |
| |
| |
| |
| One-Way Functions: Motivation | |
| |
| |
| |
| One-Way Functions: Definitions | |
| |
| |
| |
| Strong One-Way Functions | |
| |
| |
| |
| Weak One-Way Functions | |
| |
| |
| |
| Two Useful Length Conventions | |
| |
| |
| |
| Candidates for One-Way Functions | |
| |
| |
| |
| Non-Uniformly One-Way Functions | |
| |
| |
| |
| Weak One-Way Functions Imply Strong Ones | |
| |
| |
| |
| The Construction and Its Analysis (Proof of Theorem 2.3.2) | |
| |
| |
| |
| Illustration by a Toy Example | |
| |
| |
| |
| Discussion | |
| |
| |
| |
| One-Way Functions: Variations | |
| |
| |
| |
| Universal One-Way Function | |
| |
| |
| |
| One-Way Functions as Collections | |
| |
| |
| |
| Examples of One-Way Collections | |
| |
| |
| |
| Trapdoor One-Way Permutations | |
| |
| |
| |
| Claw-Free Functions | |
| |
| |
| |
| On Proposing Candidates | |
| |
| |
| |
| Hard-Core Predicates | |
| |
| |
| |
| Definition | |
| |
| |
| |
| Hard-Core Predicates for Any One-Way Function | |
| |
| |
| |
| Hard-Core Functions | |
| |
| |
| |
| Efficient Amplification of One-Way Functions | |
| |
| |
| |
| The Construction | |
| |
| |
| |
| Analysis | |
| |
| |
| |
| Miscellaneous | |
| |
| |
| |
| Historical Notes | |
| |
| |
| |
| Suggestions for Further Reading | |
| |
| |
| |
| Open Problems | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Pseudorandom Generators | |
| |
| |
| |
| Motivating Discussion | |
| |
| |
| |
| Computational Approaches to Randomness | |
| |
| |
| |
| A Rigorous Approach to Pseudorandom Generators | |
| |
| |
| |
| Computational Indistinguishability | |
| |
| |
| |
| Definition | |
| |
| |
| |
| Relation to Statistical Closeness | |
| |
| |
| |
| Indistinguishability by Repeated Experiments | |
| |
| |
| |
| Indistinguishability by Circuits | |
| |
| |
| |
| Pseudorandom Ensembles | |
| |
| |
| |
| Definitions of Pseudorandom Generators | |
| |
| |
| |
| Standard Definition of Pseudorandom Generators | |
| |
| |
| |
| Increasing the Expansion Factor | |
| |
| |
| |
| Variable-Output Pseudorandom Generators | |
| |
| |
| |
| The Applicability of Pseudorandom Generators | |
| |
| |
| |
| Pseudorandomness and Unpredictability | |
| |
| |
| |
| Pseudorandom Generators Imply One-Way Functions | |
| |
| |
| |
| Constructions Based on One-Way Permutations | |
| |
| |
| |
| Construction Based on a Single Permutation | |
| |
| |
| |
| Construction Based on Collections of Permutations | |
| |
| |
| |
| Using Hard-Core Functions Rather than Predicates | |
| |
| |
| |
| Constructions Based on One-Way Functions | |
| |
| |
| |
| Using 1-1 One-Way Functions | |
| |
| |
| |
| Using Regular One-Way Functions | |
| |
| |
| |
| Going Beyond Regular One-Way Functions | |
| |
| |
| |
| Pseudorandom Functions | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Construction | |
| |
| |
| |
| Applications: A General Methodology | |
| |
| |
| |
| Generalizations | |
| |
| |
| |
| Pseudorandom Permutations | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Construction | |
| |
| |
| |
| Miscellaneous | |
| |
| |
| |
| Historical Notes | |
| |
| |
| |
| Suggestions for Further Reading | |
| |
| |
| |
| Open Problems | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Zero-Knowledge Proof Systems | |
| |
| |
| |
| Zero-Knowledge Proofs: Motivation | |
| |
| |
| |
| The Notion of a Proof | |
| |
| |
| |
| Gaining Knowledge | |
| |
| |
| |
| Interactive Proof Systems | |
| |
| |
| |
| Definition | |
| |
| |
| |
| An Example (Graph Non-Isomorphism in IP) | |
| |
| |
| |
| The Structure of the Class IP | |
| |
| |
| |
| Augmentation of the Model | |
| |
| |
| |
| Zero-Knowledge Proofs: Definitions | |
| |
| |
| |
| Perfect and Computational Zero-Knowledge | |
| |
| |
| |
| An Example (Graph Isomorphism in PZK) | |
| |
| |
| |
| Zero-Knowledge with Respect to Auxiliary Inputs | |
| |
| |
| |
| Sequential Composition of Zero-Knowledge Proofs | |
| |
| |
| |
| Zero-Knowledge Proofs for NP | |
| |
| |
| |
| Commitment Schemes | |
| |
| |
| |
| Zero-Knowledge Proof of Graph Coloring | |
| |
| |
| |
| The General Result and Some Applications | |
| |
| |
| |
| Second-Level Considerations | |
| |
| |
| |
| Negative Results | |
| |
| |
| |
| On the Importance of Interaction and Randomness | |
| |
| |
| |
| Limitations of Unconditional Results | |
| |
| |
| |
| Limitations of Statistical ZK Proofs | |
| |
| |
| |
| Zero-Knowledge and Parallel Composition | |
| |
| |
| |
| Witness Indistinguishability and Hiding | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Parallel Composition | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| Applications | |
| |
| |
| |
| Proofs of Knowledge | |
| |
| |
| |
| Definition | |
| |
| |
| |
| Reducing the Knowledge Error | |
| |
| |
| |
| Zero-Knowledge Proofs of Knowledge for NP | |
| |
| |
| |
| Applications | |
| |
| |
| |
| Proofs of Identity (Identification Schemes) | |
| |
| |
| |
| Strong Proofs of Knowledge | |
| |
| |
| |
| Computationally Sound Proofs (Arguments) | |
| |
| |
| |
| Definition | |
| |
| |
| |
| Perfectly Hiding Commitment Schemes | |
| |
| |
| |
| Perfect Zero-Knowledge Arguments for NP | |
| |
| |
| |
| Arguments of Poly-Logarithmic Efficiency | |
| |
| |
| |
| Constant-Round Zero-Knowledge Proofs | |
| |
| |
| |
| Using Commitment Schemes with Perfect Secrecy | |
| |
| |
| |
| Bounding the Power of Cheating Provers | |
| |
| |
| |
| Non-Interactive Zero-Knowledge Proofs | |
| |
| |
| |
| Basic Definitions | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| Extensions | |
| |
| |
| |
| Multi-Prover Zero-Knowledge Proofs | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Two-Sender Commitment Schemes | |
| |
| |
| |
| Perfect Zero-Knowledge for NP | |
| |
| |
| |
| Applications | |
| |
| |
| |
| Miscellaneous | |
| |
| |
| |
| Historical Notes | |
| |
| |
| |
| Suggestions for Further Reading | |
| |
| |
| |
| Open Problems | |
| |
| |
| |
| Exercises | |
| |
| |
| |
| Background in Computational Number Theory | |
| |
| |
| |
| Prime Numbers | |
| |
| |
| |
| Quadratic Residues Modulo a Prime | |
| |
| |
| |
| Extracting Square Roots Modulo a Prime | |
| |
| |
| |
| Primality Testers | |
| |
| |
| |
| On Uniform Selection of Primes | |
| |
| |
| |
| Composite Numbers | |
| |
| |
| |
| Quadratic Residues Modulo a Composite | |
| |
| |
| |
| Extracting Square Roots Modulo a Composite | |
| |
| |
| |
| The Legendre and Jacobi Symbols | |
| |
| |
| |
| Blum Integers and Their Quadratic-Residue Structure | |
| |
| |
| |
| Brief Outline of Volume | |
| |
| |
| |
| Encryption: Brief Summary | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| Beyond Eavesdropping Security | |
| |
| |
| |
| Some Suggestions | |
| |
| |
| |
| Signatures: Brief Summary | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| Some Suggestions | |
| |
| |
| |
| Cryptographic Protocols: Brief Summary | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Constructions | |
| |
| |
| |
| Some Suggestions | |
| |
| |
| Bibliography | |
| |
| |
| Index | |