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
Appendix B Basic Algorithmic Number Theory
B Integer Arithmetic
B Basic Operations
B The Euclidean and Extended Euclidean Algorithms
B Modular Arithmetic
B Basic Operations
B Computing Modular Inverses
B Modular Exponentiation
B *Montgomery Multiplication
B Choosing a Uniform Group Element
B *Finding a Generator of a Cyclic Group
B Group-Theoretic Background
B Efficient Algorithms
References and Additional Reading
Exercises
Biography
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.
The organization is quite natural, and aligns well with my course. My course covers the topics in exactly the same order as in Katz and Lindell, except that we skip some sections due to time constraints. I actually find Chapter 1 (Introduction) among the strongest aspects of this book. It does an excellent job discussing historical cryptography, explaining the motivation behind "modern cryptography," and introducing the non-expert to some of the basic concepts on which the rest of the contents of the book are built. I think this is an excellent textbook, and I can find very little fault with it. As I mentioned above, a possible suggestion is to add some more modern topics (lattice crypto, code-based crypto, FHE, obfuscation etc.) On the other hand, as an introductory textbook, it is perhaps also fine without those more advanced and more modern topics. - Gorjan Alagic
I find Chapters 2 and 5 to be the best. Both for its clarity. Chapter 2 is clear on certain details that, in my view, make the material much easier to understand than other treatments I have come across. E.g., clearly clarifying that when we consider the notion of "secret," we address the case only that one single message is sent. Not multiple messages. This really helps one quickly understand the technical details and proofs. Similarly, Chapter 5 on hash functions, in my view, is tricky to present. E.g., it must be clear that one is not dealing with a particular instance of a collision, but really finding collisions. This distinction is made very clearly in this book.- Mahesh Tripunitara
