Enhanced descriptions from Syndetics:

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.

Table of contents provided by Syndetics

• List of Figures (p. xii)
• Preface (p. xiii)
• 1 Introduction (p. 1)
• 1.1. Cryptography: Main Topics (p. 1)
• 1.1.1. Encryption Schemes (p. 2)
• 1.1.2. Pseudorandom Generators (p. 3)
• 1.1.3. Digital Signatures (p. 4)
• 1.1.4. Fault-Tolerant Protocols and Zero-Knowledge Proofs (p. 6)
• 1.2. Some Background from Probability Theory (p. 8)
• 1.2.1. Notational Conventions (p. 8)
• 1.2.2. Three Inequalities (p. 9)
• 1.3. The Computational Model (p. 12)
• 1.3.1. P, NP, and NP-Completeness (p. 12)
• 1.3.2. Probabilistic Polynomial Time (p. 13)
• 1.3.3. Non-Uniform Polynomial Time (p. 16)
• 1.3.4. Intractability Assumptions (p. 19)
• 1.3.5. Oracle Machines (p. 20)
• 1.4. Motivation to the Rigorous Treatment (p. 21)
• 1.4.1. The Need for a Rigorous Treatment (p. 21)
• 1.4.2. Practical Consequences of the Rigorous Treatment (p. 23)
• 1.4.3. The Tendency to Be Conservative (p. 24)
• 1.5. Miscellaneous (p. 25)
• 1.5.1. Historical Notes (p. 25)
• 1.5.2. Suggestions for Further Reading (p. 27)
• 1.5.3. Open Problems (p. 27)
• 1.5.4. Exercises (p. 28)
• 2 Computational Difficulty (p. 30)
• 2.1. One-Way Functions: Motivation (p. 31)
• 2.2. One-Way Functions: Definitions (p. 32)
• 2.2.1. Strong One-Way Functions (p. 32)
• 2.2.2. Weak One-Way Functions (p. 35)
• 2.2.3. Two Useful Length Conventions (p. 35)
• 2.2.4. Candidates for One-Way Functions (p. 40)
• 2.2.5. Non-Uniformly One-Way Functions (p. 41)
• 2.3. Weak One-Way Functions Imply Strong Ones (p. 43)
• 2.3.1. The Construction and Its Analysis (Proof of Theorem 2.3.2) (p. 44)
• 2.3.2. Illustration by a Toy Example (p. 48)
• 2.3.3. Discussion (p. 50)
• 2.4. One-Way Functions: Variations (p. 51)
• 2.4.1. Universal One-Way Function (p. 52)
• 2.4.2. One-Way Functions as Collections (p. 53)
• 2.4.3. Examples of One-Way Collections (p. 55)
• 2.4.4. Trapdoor One-Way Permutations (p. 58)
• 2.4.5. Claw-Free Functions (p. 60)
• 2.4.6. On Proposing Candidates (p. 63)
• 2.5. Hard-Core Predicates (p. 64)
• 2.5.1. Definition (p. 64)
• 2.5.2. Hard-Core Predicates for Any One-Way Function (p. 65)
• 2.5.3. Hard-Core Functions (p. 74)
• 2.6. Efficient Amplification of One-Way Functions (p. 78)
• 2.6.1. The Construction (p. 80)
• 2.6.2. Analysis (p. 81)
• 2.7. Miscellaneous (p. 88)
• 2.7.1. Historical Notes (p. 89)
• 2.7.2. Suggestions for Further Reading (p. 89)
• 2.7.3. Open Problems (p. 91)
• 2.7.4. Exercises (p. 92)
• 3 Pseudorandom Generators (p. 101)
• 3.1. Motivating Discussion (p. 102)
• 3.1.1. Computational Approaches to Randomness (p. 102)
• 3.1.2. A Rigorous Approach to Pseudorandom Generators (p. 103)
• 3.2. Computational Indistinguishability (p. 103)
• 3.2.1. Definition (p. 104)
• 3.2.2. Relation to Statistical Closeness (p. 106)
• 3.2.3. Indistinguishability by Repeated Experiments (p. 107)
• 3.2.4. Indistinguishability by Circuits (p. 111)
• 3.2.5. Pseudorandom Ensembles (p. 112)
• 3.3. Definitions of Pseudorandom Generators (p. 112)
• 3.3.1. Standard Definition of Pseudorandom Generators (p. 113)
• 3.3.2. Increasing the Expansion Factor (p. 114)
• 3.3.3. Variable-Output Pseudorandom Generators (p. 118)
• 3.3.4. The Applicability of Pseudorandom Generators (p. 119)
• 3.3.5. Pseudorandomness and Unpredictability (p. 119)
• 3.3.6. Pseudorandom Generators Imply One-Way Functions (p. 123)
• 3.4. Constructions Based on One-Way Permutations (p. 124)
• 3.4.1. Construction Based on a Single Permutation (p. 124)
• 3.4.2. Construction Based on Collections of Permutations (p. 131)
• 3.4.3. Using Hard-Core Functions Rather than Predicates (p. 134)
• 3.5. Constructions Based on One-Way Functions (p. 135)
• 3.5.1. Using 1-1 One-Way Functions (p. 135)
• 3.5.2. Using Regular One-Way Functions (p. 141)
• 3.5.3. Going Beyond Regular One-Way Functions (p. 147)
• 3.6. Pseudorandom Functions (p. 148)
• 3.6.1. Definitions (p. 148)
• 3.6.2. Construction (p. 150)
• 3.6.3. Applications: A General Methodology (p. 157)
• 3.6.4. Generalizations (p. 158)
• 3.7. Pseudorandom Permutations (p. 164)
• 3.7.1. Definitions (p. 164)
• 3.7.2. Construction (p. 166)
• 3.8. Miscellaneous (p. 169)
• 3.8.1. Historical Notes (p. 169)
• 3.8.2. Suggestions for Further Reading (p. 170)
• 3.8.3. Open Problems (p. 172)
• 3.8.4. Exercises (p. 172)
• 4 Zero-Knowledge Proof Systems (p. 184)
• 4.1. Zero-Knowledge Proofs: Motivation (p. 185)
• 4.1.1. The Notion of a Proof (p. 187)
• 4.1.2. Gaining Knowledge (p. 189)
• 4.2. Interactive Proof Systems (p. 190)
• 4.2.1. Definition (p. 190)
• 4.2.2. An Example (Graph Non-Isomorphism in IP) (p. 195)
• 4.2.3. The Structure of the Class IP (p. 198)
• 4.2.4. Augmentation of the Model (p. 199)
• 4.3. Zero-Knowledge Proofs: Definitions (p. 200)
• 4.3.1. Perfect and Computational Zero-Knowledge (p. 200)
• 4.3.2. An Example (Graph Isomorphism in PZK) (p. 207)
• 4.3.3. Zero-Knowledge with Respect to Auxiliary Inputs (p. 213)
• 4.3.4. Sequential Composition of Zero-Knowledge Proofs (p. 216)
• 4.4. Zero-Knowledge Proofs for NP (p. 223)
• 4.4.1. Commitment Schemes (p. 223)
• 4.4.2. Zero-Knowledge Proof of Graph Coloring (p. 228)
• 4.4.3. The General Result and Some Applications (p. 240)
• 4.4.4. Second-Level Considerations (p. 243)
• 4.5. Negative Results (p. 246)
• 4.5.1. On the Importance of Interaction and Randomness (p. 247)
• 4.5.2. Limitations of Unconditional Results (p. 248)
• 4.5.3. Limitations of Statistical ZK Proofs (p. 250)
• 4.5.4. Zero-Knowledge and Parallel Composition (p. 251)
• 4.6. Witness Indistinguishability and Hiding (p. 254)
• 4.6.1. Definitions (p. 254)
• 4.6.2. Parallel Composition (p. 258)
• 4.6.3. Constructions (p. 259)
• 4.6.4. Applications (p. 261)
• 4.7. Proofs of Knowledge (p. 262)
• 4.7.1. Definition (p. 262)
• 4.7.2. Reducing the Knowledge Error (p. 267)
• 4.7.3. Zero-Knowledge Proofs of Knowledge for NP (p. 268)
• 4.7.4. Applications (p. 269)
• 4.7.5. Proofs of Identity (Identification Schemes) (p. 270)
• 4.7.6. Strong Proofs of Knowledge (p. 274)
• 4.8. Computationally Sound Proofs (Arguments) (p. 277)
• 4.8.1. Definition (p. 277)
• 4.8.2. Perfectly Hiding Commitment Schemes (p. 278)
• 4.8.3. Perfect Zero-Knowledge Arguments for NP (p. 284)
• 4.8.4. Arguments of Poly-Logarithmic Efficiency (p. 286)
• 4.9. Constant-Round Zero-Knowledge Proofs (p. 288)
• 4.9.1. Using Commitment Schemes with Perfect Secrecy (p. 289)
• 4.9.2. Bounding the Power of Cheating Provers (p. 294)
• 4.10. Non-Interactive Zero-Knowledge Proofs (p. 298)
• 4.10.1. Basic Definitions (p. 299)
• 4.10.2. Constructions (p. 300)
• 4.10.3. Extensions (p. 306)
• 4.11. Multi-Prover Zero-Knowledge Proofs (p. 311)
• 4.11.1. Definitions (p. 311)
• 4.11.2. Two-Sender Commitment Schemes (p. 313)
• 4.11.3. Perfect Zero-Knowledge for NP (p. 317)
• 4.11.4. Applications (p. 319)
• 4.12. Miscellaneous (p. 320)
• 4.12.1. Historical Notes (p. 320)
• 4.12.2. Suggestions for Further Reading (p. 322)
• 4.12.3. Open Problems (p. 323)
• 4.12.4. Exercises (p. 323)
• Appendix A Background in Computational Number Theory (p. 331)
• A.1. Prime Numbers (p. 331)
• A.1.1. Quadratic Residues Modulo a Prime (p. 331)
• A.1.2. Extracting Square Roots Modulo a Prime (p. 332)
• A.1.3. Primality Testers (p. 332)
• A.1.4. On Uniform Selection of Primes (p. 333)
• A.2. Composite Numbers (p. 334)
• A.2.1. Quadratic Residues Modulo a Composite (p. 335)
• A.2.2. Extracting Square Roots Modulo a Composite (p. 335)
• A.2.3. The Legendre and Jacobi Symbols (p. 336)
• A.2.4. Blum Integers and Their Quadratic-Residue Structure (p. 337)
• Appendix B Brief Outline of Volume (p. 338)
• B.1. Encryption: Brief Summary (p. 338)
• B.1.1. Definitions (p. 338)
• B.1.2. Constructions (p. 340)
• B.1.3. Beyond Eavesdropping Security (p. 343)
• B.1.4. Some Suggestions (p. 345)
• B.2. Signatures: Brief Summary (p. 345)
• B.2.1. Definitions (p. 346)
• B.2.2. Constructions (p. 347)
• B.2.3. Some Suggestions (p. 349)
• B.3. Cryptographic Protocols: Brief Summary (p. 350)
• B.3.1. Definitions (p. 350)
• B.3.2. Constructions (p. 352)
• B.3.3. Some Suggestions (p. 353)
• Bibliography (p. 355)
• Index (p. 367)