1 Introduction
1.1. Cryptography: Main Topics
1.1.1. Encryption Schemes
1.1.2. Pseudorandom Generators
1.1.3. Digital Signatures
1.1.4. Fault-Tolerant Protocols and Zero-Knowledge Proofs
1.2. Some Background from probability Theory
1.2.1. Notational Conventions
1.2.2. Three Inequalities
1.3. The Computational Model
1.3.1. p, NP, and NP-Completeness
1.3.2. Probabilistic Polynomial Time
1.3.3. Non-Uniform Polynomial Time
1.3.4. Intractability Assumptions
1.3.5. Oracle Machines
1.4. Motivation to the Rigorous Treatment
1.4.1. The Need for a Rigorous Treatment
1.4.2. Practical Consequences of the Rigorous Treatment
1.4.3. The Tendency to Be Conservative
1.5. Miscellaneous
1.5.1. Historical Notes
1.5.2. Suggestions for Further Reading
1.5.3. Open Problems
1.5.4. Exercises
2 Computational Difficulty
2.1. One-Way Functions: Motivation
2.2. One-Way Functions: Definitions
2.2.1. Strong One-Way Functions
2.2.2. Weak One-Way Functions
2.2.3. Two Useful Length Conventions
2.2.4. Candidates for One-Way Functions
2.2.5. Non-Uniformly One-Way Functions
2.3 Weak One-Way Functions Imply Strong Ones
2.3.1. The Construction and Its Analysis (Proof of Theorem 2.3.2)
2.3.2. Illustration by a Toy Example
2.3.3. Discussion
2.4. One-Way Functions: Variations
2.4.1.* Universal One-Way Function
2.4.2. One-Way Functions as Collections
2.4.3. Examples of One-Way Collections
2.4.4. Trapdoor One-Way Permutations
2.4.5." Claw-Free Functions
2.4.6." On Proposing Candidates
2.5. Hard-Core Predicates
2.5.1. Definition
2.5.2. Hard-Core Predicates for Any One-Way Function
2.5.3. Hard-Core Functions
2.6.' Efficient Amplification of One-Way Functions
2.6.1. The Construction
2.6.2. Analysis
2.7. Miscellaneous
2.7.1. Historical Notes
2.7.2. Suggestions for Further Reading
2.7.3. Open Problems
2.7.4. Exercises
3 Pseudorandom Generators
3.1. Motivating Discussion
3.1.1. Computational Approaches to Randomness
3.1.2. A Rigorous Approach to Pseudorandom Generators
3.2. Computational Indistinguishability
3.2.1. Definition
3.2.2. Relation to Statistical Closeness
3.2.3. Indistinguishability by Repeated Experiments
3.3.4.' Indistinguishability by Circuits
3.2.5. Pseudorandom Ensembles
3.3. Definitions of Pseudorandom Generators
3.3.1. Standard Definition of Pseudorandom Generators
3.3.2. Increasing the Expansion Factor
3.3.3.' Variable-Output Pseudorandom Generators
3.3.4. The Applicability of Pseudorandom Generators
3.3.5. Pseudorandomness and Unpredictability
3.3.6. Pseudorandom Generators Imply One-Way Functions
3.4. Constructions Based on One-Way Permutations
3.4.1. Construction Based on a Single Permutation
3.4.2. Construction Based on Collections of Permutations
3.4.3.' Using Hard-Core Functions Rather than Predicates
3.5.' Constructions Based on One-Way Functions
3.5.1. Using 1-1 One-Way Functions
3.5.2. Using Regular One-Way Functions
3.5.3. Going Beyond Regular One-Way Functions
3.6. Pseudorandom Functions
3.6.1. Definitions
3.6.2. Construction
3.6.3. Applications: A General Methodology
3.6.4.' Generalizations
3.7.' Pseudorandom Permutations
3.7.1. Definitions
3.7.2. Construction
3.8. Miscellaneous
3.8.1. Historical Notes
3.8.2. 'Suggestions for Further Reading
3.8.3. Open Problems
3.8.4. Exercises
4 Zero-Knowledge Proof Systems
4.1. Zero-Knowledge Proofs: Motivation
4.1.1. The Notion ofa Proof
4.1.2. Gaining Knowledge
4.2. Interactive Proof Systems
4.2.1. Definition
4.2.2. An Example (Graph Non-Isomorphism in IP)
4.2.3.' The Structure of the Class IP
4.2.4. Augmentation of the Model
4.3. Zero-Knowledge Proofs: Definitions
4.3.1. Perfect and Computational Zero-Knowledge
4.3.2. An Example (Graph Isomorphism in PZK)
4.3.3. Zero-Knowledge with Respect to Auxiliary Inputs
4.3.4. Seqaential Composition of Zero-Knowledge Proofs
4.4. Zero-Knowledge hoofs for NP
4.4.1. Commitment Schemes
4.4.2. Zero-Knowledge Proof of Graph Coloring
4.4.3. The General Result and Some Applications
4.4.4. Second-Level Considerations .
4.5." Negative Results
4.5.1. On the Importance of Interaction and Randomoess
4.5.2. Limitations of Unconditional Results
4.5.3. Limitations of Statistical ZK Proofs
4.5.4. Zero-Knowledge and Parallel Composition
4.6.' Witness Indistinguishability and Hiding
4.6.1. Definitions
4.6.2. Parallel Composition
4.6.3. Constructions
4.6.4. Applications
4.7.' Proofs of Knowledge
4.7.1. Definition
4.7.2. Reducing the Knowledge Error
4.7.3. Zero-Knowledge Proofs of Knowledge for NP
4.7.4. Applications
4.7.5. Proofs of Identity (Identification Schemes)
4.7.6. Strong Proofs of Knowledge
4.8." Computationally Sound Proofs (Arguments)
4.8.1. Definition
4.8.2. Perfectly Hiding Commitment Schemes
4.8.3. Perfect Zero-Knowledge Arguments for NP
4.8.4. Arguments of Poly-Logarithmic Efficiency
4.9.' Constant-Round Zero-Knowledge Proofs
4.9.1. Using Commitment Schemes with Perfect Secrecy
4.9.2. Bounding the Power of Cheating Provers
4.10.' Non-Interactive Zero-Knowledge Proofs
4.10.1. Basic Definitions
4.10.2. Constructions
4.10.3. Extensions
4.11.' Multi-Prover Zero-Knowledge Proofs
4.11.1. Definitions
4.11.2. Two-Sender Commitment Schemes
4.11.3. Perfect Zero-Knowledge for NP
4.11.4. Applications
4.12. Miscellaneous
4.12.1. Historical Notes
4.12.2. Suggestions for Further Reading
4.12.3. Open Problems
4.12.4. Exercises
Appendix A: Background in Computational Number Theory
A.1. Prime Numbers
A.1.1. Quadratic Residues Modulo a Prime
A.1.2. Extracting Square Roots Modulo a Prime
A.1.3. Primality Testers
A.1.4. On Uniform Selection of Primes
A.2. Composite Numbers
A.2.1. Quadratic Residues Modulo a Composite
A.2.2. Extracting Square Roots Modulo a Composite
A.2.3. The Legendre and Jacobi Symbols
A.2.4. Blum Integers and Their Quadratic-Residue Structure
Appendix B: Brief Outline of Volume 2
B.1. Encryption: Brief Summary
B.1.1. Definitions
B.1.2. Constructions
B.1.3. Beyond Eavesdropping Security
B.1.4. Some Suggestions
B.2. Signatures: Brief Summary
B.2.1. Definitions
B.2.2. Constructions
B.2.3. Some Suggestions
B.3. Cryptographic Protocols: Brief S
B.3.1. Definitions
B.3.2. Constructions
B.3.3. Some Suggestions
Bibliography
Index
鄂公网安备 42010302001612号 