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