Foundations of cryptography :
Goldreich, Oded,
Foundations of cryptography : basic tools / Oded Goldreich. - Cambridge : Cambridge University Press, 2003. - 1 online resource (xix, 372 pages) : digital, PDF file(s).
Title from publisher's bibliographic system (viewed on 05 Oct 2015).
Encryption Schemes Pseudorandom Generators Digital Signatures Fault-Tolerant Protocols and Zero-Knowledge Proofs Some Background from Probability Theory Notational Conventions Three Inequalities Computational Model P, NP, and NP-Completeness Probabilistic Polynomial Time Non-Uniform Polynomial Time Intractability Assumptions Oracle Machines Motivation to the Rigorous Treatment Need for a Rigorous Treatment Practical Consequences of the Rigorous Treatment Tendency to Be Conservative Historical Notes Open Problems 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 Construction and Its Analysis (Proof of Theorem 2.3.2) Illustration by a Toy Example 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 Hard-Core Predicates for Any One-Way Function Hard-Core Functions Efficient Amplification of One-Way Functions Construction Analysis Historical Notes Pseudorandom Generators Motivating Discussion Computational Approaches to Randomness A Rigorous Approach to Pseudorandom Generators Computational Indistinguishability 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 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 Applications: A General Methodology Pseudorandom Permutations Historical Notes Zero-Knowledge Proof Systems Zero-Knowledge Proofs: Motivation Notion of a Proof Gaining Knowledge Interactive Proof Systems An Example (Graph Non-Isomorphism in IP) 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 ofh Zero-Knowledge Proofs Zero-Knowledge Proofs for NP Commitment Schemes Zero-Knowledge Proof of Graph Coloring 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 Parallel Composition Proofs of Knowledge Reducing the Knowledge Error Zero-Knowledge Proofs of Knowledge for NP Proofs of Identity (Identification Schemes) Strong Proofs of Knowledge Computationally Sound Proofs (Arguments) 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 Extensions Multi-Prover Zero-Knowledge Proofs Two-Sender Commitment Schemes Perfect Zero-Knowledge for NP Historical Notes A 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 Legendre and Jacobi Symbols Blum Integers and Their Quadratic-Residue Structure Brief Outline of Volume Encryption: Brief Summary Beyond Eavesdropping Security Signatures: Brief Summary Cryptographic Protocols: Brief Summary 1.1.1. 2 -- 1.1.2. 3 -- 1.1.3. 4 -- 1.1.4. 6 -- 1.2. 8 -- 1.2.1. 8 -- 1.2.2. 9 -- 1.3. 12 -- 1.3.1. 12 -- 1.3.2. 13 -- 1.3.3. 16 -- 1.3.4. 19 -- 1.3.5. 20 -- 1.4. 21 -- 1.4.1. 21 -- 1.4.2. 23 -- 1.4.3. 24 -- 1.5.1. 25 -- 1.5.3. 27 -- 2 30 -- 2.1. 31 -- 2.2. 32 -- 2.2.1. 32 -- 2.2.2. 35 -- 2.2.3. 35 -- 2.2.4. 40 -- 2.2.5. 41 -- 2.3. 43 -- 2.3.1. 44 -- 2.3.2. 48 -- 2.4. 51 -- 2.4.1. 52 -- 2.4.2. 53 -- 2.4.3. 55 -- 2.4.4. 58 -- 2.4.5. 60 -- 2.4.6. 63 -- 2.5. 64 -- 2.5.2. 65 -- 2.5.3. 74 -- 2.6. 78 -- 2.6.1. 80 -- 2.6.2. 81 -- 2.7.1. 89 -- 3 101 -- 3.1. 102 -- 3.1.1. 102 -- 3.1.2. 103 -- 3.2. 103 -- 3.2.2. 106 -- 3.2.3. 107 -- 3.2.4. 111 -- 3.2.5. 112 -- 3.3. 112 -- 3.3.1. 113 -- 3.3.2. 114 -- 3.3.3. 118 -- 3.3.4. 119 -- 3.3.5. 119 -- 3.3.6. 123 -- 3.4. 124 -- 3.4.1. 124 -- 3.4.2. 131 -- 3.4.3. 134 -- 3.5. 135 -- 3.5.1. 135 -- 3.5.2. 141 -- 3.5.3. 147 -- 3.6. 148 -- 3.6.3. 157 -- 3.7. 164 -- 3.8.1. 169 -- 4 184 -- 4.1. 185 -- 4.1.1. 187 -- 4.1.2. 189 -- 4.2. 190 -- 4.2.2. 195 -- 4.2.3. 198 -- 4.2.4. 199 -- 4.3. 200 -- 4.3.1. 200 -- 4.3.2. 207 -- 4.3.3. 213 -- 4.3.4. 216 -- 4.4. 223 -- 4.4.1. 223 -- 4.4.2. 228 -- 4.4.3. 240 -- 4.4.4. 243 -- 4.5. 246 -- 4.5.1. 247 -- 4.5.2. 248 -- 4.5.3. 250 -- 4.5.4. 251 -- 4.6. 254 -- 4.6.2. 258 -- 4.7. 262 -- 4.7.2. 267 -- 4.7.3. 268 -- 4.7.5. 270 -- 4.7.6. 274 -- 4.8. 277 -- 4.8.2. 278 -- 4.8.3. 284 -- 4.8.4. 286 -- 4.9. 288 -- 4.9.1. 289 -- 4.9.2. 294 -- 4.10. 298 -- 4.10.3. 306 -- 4.11. 311 -- 4.11.2. 313 -- 4.11.3. 317 -- 4.12.1. 320 -- Appendix 331 -- A.1. 331 -- A.1.1. 331 -- A.1.2. 332 -- A.1.3. 332 -- A.1.4. 333 -- A.2. 334 -- A.2.1. 335 -- A.2.2. 335 -- A.2.3. 336 -- A.2.4. 337 -- Appendix B 338 -- B.1. 338 -- B.1.3. 343 -- B.2. 345 -- B.3. 350.
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.
9780511546891 (ebook)
Coding theory.
Cryptography--Mathematics.
QA268 / .G5745 2003
652/.8
Foundations of cryptography : basic tools / Oded Goldreich. - Cambridge : Cambridge University Press, 2003. - 1 online resource (xix, 372 pages) : digital, PDF file(s).
Title from publisher's bibliographic system (viewed on 05 Oct 2015).
Encryption Schemes Pseudorandom Generators Digital Signatures Fault-Tolerant Protocols and Zero-Knowledge Proofs Some Background from Probability Theory Notational Conventions Three Inequalities Computational Model P, NP, and NP-Completeness Probabilistic Polynomial Time Non-Uniform Polynomial Time Intractability Assumptions Oracle Machines Motivation to the Rigorous Treatment Need for a Rigorous Treatment Practical Consequences of the Rigorous Treatment Tendency to Be Conservative Historical Notes Open Problems 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 Construction and Its Analysis (Proof of Theorem 2.3.2) Illustration by a Toy Example 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 Hard-Core Predicates for Any One-Way Function Hard-Core Functions Efficient Amplification of One-Way Functions Construction Analysis Historical Notes Pseudorandom Generators Motivating Discussion Computational Approaches to Randomness A Rigorous Approach to Pseudorandom Generators Computational Indistinguishability 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 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 Applications: A General Methodology Pseudorandom Permutations Historical Notes Zero-Knowledge Proof Systems Zero-Knowledge Proofs: Motivation Notion of a Proof Gaining Knowledge Interactive Proof Systems An Example (Graph Non-Isomorphism in IP) 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 ofh Zero-Knowledge Proofs Zero-Knowledge Proofs for NP Commitment Schemes Zero-Knowledge Proof of Graph Coloring 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 Parallel Composition Proofs of Knowledge Reducing the Knowledge Error Zero-Knowledge Proofs of Knowledge for NP Proofs of Identity (Identification Schemes) Strong Proofs of Knowledge Computationally Sound Proofs (Arguments) 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 Extensions Multi-Prover Zero-Knowledge Proofs Two-Sender Commitment Schemes Perfect Zero-Knowledge for NP Historical Notes A 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 Legendre and Jacobi Symbols Blum Integers and Their Quadratic-Residue Structure Brief Outline of Volume Encryption: Brief Summary Beyond Eavesdropping Security Signatures: Brief Summary Cryptographic Protocols: Brief Summary 1.1.1. 2 -- 1.1.2. 3 -- 1.1.3. 4 -- 1.1.4. 6 -- 1.2. 8 -- 1.2.1. 8 -- 1.2.2. 9 -- 1.3. 12 -- 1.3.1. 12 -- 1.3.2. 13 -- 1.3.3. 16 -- 1.3.4. 19 -- 1.3.5. 20 -- 1.4. 21 -- 1.4.1. 21 -- 1.4.2. 23 -- 1.4.3. 24 -- 1.5.1. 25 -- 1.5.3. 27 -- 2 30 -- 2.1. 31 -- 2.2. 32 -- 2.2.1. 32 -- 2.2.2. 35 -- 2.2.3. 35 -- 2.2.4. 40 -- 2.2.5. 41 -- 2.3. 43 -- 2.3.1. 44 -- 2.3.2. 48 -- 2.4. 51 -- 2.4.1. 52 -- 2.4.2. 53 -- 2.4.3. 55 -- 2.4.4. 58 -- 2.4.5. 60 -- 2.4.6. 63 -- 2.5. 64 -- 2.5.2. 65 -- 2.5.3. 74 -- 2.6. 78 -- 2.6.1. 80 -- 2.6.2. 81 -- 2.7.1. 89 -- 3 101 -- 3.1. 102 -- 3.1.1. 102 -- 3.1.2. 103 -- 3.2. 103 -- 3.2.2. 106 -- 3.2.3. 107 -- 3.2.4. 111 -- 3.2.5. 112 -- 3.3. 112 -- 3.3.1. 113 -- 3.3.2. 114 -- 3.3.3. 118 -- 3.3.4. 119 -- 3.3.5. 119 -- 3.3.6. 123 -- 3.4. 124 -- 3.4.1. 124 -- 3.4.2. 131 -- 3.4.3. 134 -- 3.5. 135 -- 3.5.1. 135 -- 3.5.2. 141 -- 3.5.3. 147 -- 3.6. 148 -- 3.6.3. 157 -- 3.7. 164 -- 3.8.1. 169 -- 4 184 -- 4.1. 185 -- 4.1.1. 187 -- 4.1.2. 189 -- 4.2. 190 -- 4.2.2. 195 -- 4.2.3. 198 -- 4.2.4. 199 -- 4.3. 200 -- 4.3.1. 200 -- 4.3.2. 207 -- 4.3.3. 213 -- 4.3.4. 216 -- 4.4. 223 -- 4.4.1. 223 -- 4.4.2. 228 -- 4.4.3. 240 -- 4.4.4. 243 -- 4.5. 246 -- 4.5.1. 247 -- 4.5.2. 248 -- 4.5.3. 250 -- 4.5.4. 251 -- 4.6. 254 -- 4.6.2. 258 -- 4.7. 262 -- 4.7.2. 267 -- 4.7.3. 268 -- 4.7.5. 270 -- 4.7.6. 274 -- 4.8. 277 -- 4.8.2. 278 -- 4.8.3. 284 -- 4.8.4. 286 -- 4.9. 288 -- 4.9.1. 289 -- 4.9.2. 294 -- 4.10. 298 -- 4.10.3. 306 -- 4.11. 311 -- 4.11.2. 313 -- 4.11.3. 317 -- 4.12.1. 320 -- Appendix 331 -- A.1. 331 -- A.1.1. 331 -- A.1.2. 332 -- A.1.3. 332 -- A.1.4. 333 -- A.2. 334 -- A.2.1. 335 -- A.2.2. 335 -- A.2.3. 336 -- A.2.4. 337 -- Appendix B 338 -- B.1. 338 -- B.1.3. 343 -- B.2. 345 -- B.3. 350.
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.
9780511546891 (ebook)
Coding theory.
Cryptography--Mathematics.
QA268 / .G5745 2003
652/.8