Introduction to Modern Cryptography

Now the most used texbook for introductory cryptography courses in both mathematics and computer science, the Third Edition builds upon previous editions by offering several new sections, topics, and exercises. The authors present the core principles of modern cryptography, with emphasis on formal definitions, rigorous proofs of security.

I Introduction and Classical Cryptography 1. Introduction Cryptography and Modern Cryptography The Setting of Private-Key Encryption Historical Ciphers and Their Cryptanalysis Principles of Modern Cryptography Principle 1 - Formal Definitions Principle 2 - Precise Assumptions Principle 3 - Proofs of Security Provable Security and Real-World Security References and Additional Reading Exercises 2. Perfectly Secret Encryption Definitions The One-Time Pad Limitations of Perfect Secrecy *Shannon's Theorem References and Additional Reading Exercises II Private-Key (Symmetric) Cryptography 3. Private-Key Encryption Computational Security The Concrete Approach The Asymptotic Approach Defining Computationally Secure Encryption The Basic Definition of Security (EAV-Security) *Semantic Security Constructing an EAV-Secure Encryption Scheme Pseudorandom Generators Proofs by Reduction EAV-Security from a Pseudorandom Generator Stronger Security Notions Security for Multiple Encryptions Chosen-Plaintext Attacks and CPA-Security CPA-Security for Multiple Encryptions Constructing a CPA-Secure Encryption Scheme Pseudorandom Functions and Permutations CPA-Security from a Pseudorandom Function Modes of Operation and Encryption in Practice Stream Ciphers Stream-Cipher Modes of Operation Block Ciphers and Block-Cipher Modes of Operation *Nonce-Based Encryption References and Additional Reading Exercises 4. Message Authentication Codes Message Integrity Secrecy vs Integrity Encryption vs Message Authentication Message Authentication Codes (MACs) - Definitions Constructing Secure Message Authentication Codes A Fixed-Length MAC Domain Extension for MACs CBC-MAC The Basic Construction *Proof of Security GMAC and Poly MACs from Difference-Universal Functions Instantiations *Information-Theoretic MACs One-Time MACs from Strongly Universal Functions One-Time MACs from Difference-Universal Functions Limitations on Information-Theoretic MACs References and Additional Reading Exercises 5. CCA-Security and Authenticated Encryption Chosen-Ciphertext Attacks and CCA-Security Padding-Oracle Attacks Defining CCA-Security Authenticated Encryption Defining Authenticated Encryption CCA Security vs Authenticated Encryption Authenticated Encryption Schemes Generic Constructions Standardized Schemes Secure Communication Sessions References and Additional Reading Exercises 6. Hash Functions and Applications Definitions Collision Resistance Weaker Notions of Security Domain Extension: The Merkle-Damgard Transform Message Authentication Using Hash Functions Hash-and-MAC HMAC Generic Attacks on Hash Functions Birthday Attacks for Finding Collisions Small-Space Birthday Attacks *Time/Space Tradeo s for Inverting Hash Functions The Random-Oracle Model The Random-Oracle Model in Detail Is the Random-Oracle Methodology Sound? Additional Applications of Hash Functions Fingerprinting and Deduplication Merkle Trees Password Hashing Key Derivation Commitment Schemes References and Additional Reading Exercises 7. Practical Constructions of Symmetric-Key Primitives Stream Ciphers Linear-Feedback Shift Registers Adding Nonlinearity Trivium RC4 ChaCha20 Block Ciphers Substitution-Permutation Networks Feistel Networks DES - The Data Encryption Standard 3 DES: Increasing the Key Length of a Block Cipher AES -The Advanced Encryption Standard *Differential and Linear Cryptanalysis Compression Functions and Hash Functions Compression Functions from Block Ciphers MD5, SHA-1, and SHA-2 The Sponge Construction and SHA-3 (Keccak) References and Additional Reading Exercises 8. *Theoretical Constructions of Symmetric-Key Primitives One-Way Functions Definitions Candidate One-Way Functions Hard-Core Predicates From One-Way Functions to Pseudorandomness Hard-Core Predicates from One-Way Functions A Simple Case A More Involved Case The Full Proof Constructing Pseudorandom Generators Pseudorandom Generators with Minimal Expansion Increasing the Expansion Factor Constructing Pseudorandom Functions Constructing (Strong) Pseudorandom Permutations Assumptions for Private-Key Cryptography Computational Indistinguishability References and Additional Reading Exercises III Public-Key (Asymmetric) Cryptography 9. Number Theory and Cryptographic Hardness Assumptions Preliminaries and Basic Group Theory Primes and Divisibility Modular Arithmetic Groups The Group ZN *Isomorphisms and the Chinese Remainder Theorem Primes, Factoring, and RSA Generating Random Primes *Primality Testing The Factoring Assumption The RSA Assumption *Relating the Factoring and RSA Assumptions Cryptographic Assumptions in Cyclic Groups Cyclic Groups and Generators The Discrete-Logarithm/Diffie-Hellman Assumptions Working in (Subgroups of) Zp Elliptic Curves *Cryptographic Applications One-Way Functions and Permutations Collision-Resistant Hash Functions References and Additional Reading Exercises 10. *Algorithms for Factoring and Computing Discrete Logarithms Algorithms for Factoring Pollard's p - Algorithm Pollard's Rho Algorithm The Quadratic Sieve Algorithm Generic Algorithms for Computing Discrete Logarithms The Pohlig-Hellman Algorithm The Baby-Step/Giant-Step Algorithm Discrete Logarithms from Collisions Index Calculus: Computing Discrete Logarithms in Zp Recommended Key Lengths References and Additional Reading Exercises 11. Key Management and the Public-Key Revolution Key Distribution and Key Management A Partial Solution: Key-Distribution Centers Key Exchange and the Diffie-Hellman Protocol The Public-Key Revolution References and Additional Reading Exercises 12. Public-Key Encryption Public-Key Encryption - An Overview Definitions Security against Chosen-Plaintext Attacks Multiple Encryptions Security against Chosen-Ciphertext Attacks Hybrid Encryption and the KEM/DEM Paradigm CPA-Security CCA-Security CDH/DDH-Based Encryption El Gamal Encryption DDH-Based Key Encapsulation *A CDH-Based KEM in the Random-Oracle Model *Chosen-Ciphertext Security and DHIES/ECIES RSA-Based Encryption Plain RSA Encryption Padded RSA and PKCS # v *CPA-Secure Encryption without Random Oracles OAEP and PKCS # v *A CCA-Secure KEM in the Random-Oracle Model RSA Implementation Issues and Pitfalls References and Additional Reading Exercises 13. Digital Signature Schemes Digital Signatures - An Overview Definitions The Hash-and-Sign Paradigm RSA-Based Signatures Plain RSA Signatures RSA-FDH and PKCS #1 Standards Signatures from the Discrete-Logarithm Problem Identification Schemes and Signatures The Schnorr Identification/Signature Schemes DSA and ECDSA Certificates and Public-Key Infrastructures Putting It All Together { TLS *Signcryption References and Additional Reading Exercises 14. *Post-Quantum Cryptography Post-Quantum Symmetric-Key Cryptography Grover's Algorithm and Symmetric-Key Lengths Collision-Finding Algorithms and Hash Functions Shor's Algorithm and its Impact on Cryptography Post-Quantum Public-Key Encryption Post-Quantum Signatures Lamport's Signature Scheme Chain-Based Signatures Tree-Based Signatures References and Additional Reading Exercises 15. *Advanced Topics in Public-Key Encryption Public-Key Encryption from Trapdoor Permutations Trapdoor Permutations Public-Key Encryption from Trapdoor Permutations The Paillier Encryption Scheme The Structure of Z_N The Paillier Encryption Scheme Homomorphic Encryption Secret Sharing and Threshold Encryption Secret Sharing Verifiable Secret Sharing Threshold Encryption and Electronic Voting The Goldwasser-Micali Encryption Scheme Quadratic Residues Modulo a Prime Quadratic Residues Modulo a Composite The Quadratic Residuosity Assumption The Goldwasser-Micali Encryption Scheme The Rabin Encryption Scheme Computing Modular Square Roots A Trapdoor Permutation Based on Factoring The Rabin Encryption Scheme References and Additional Reading Exercises Index of Common Notation Appendix A Mathematical Background A Identities and Inequalities A Asymptotic Notation A Basic Probability A The \Birthday" Problem A *Finite Fields

Jonathan Katz is Director, Maryland Cybersecurity Center and Professor, Department of Computer Science and UMIACS Department of Electrical and Computer Engineering at University of Maryland. He is the co-author with Yehuda Lindell of Introdution to Modern Cryptography, Second Edition, published by CRC Press.Vadim Yehuda Lindell is a professor in the Department of Computer Science at Bar-Ilan University where he conducts research on cryptography with a focus on the theory of secure computation and its application in practice. Lindell received a Raviv Fellowship[1] and spent two years at IBM's cryptography research group at the T.J. Watson Research Center.