3rd Edition

# Introduction to Modern Cryptography

By Jonathan Katz, Yehuda Lindell Copyright 2021
648 Pages 50 B/W Illustrations
by Chapman & Hall

648 Pages 50 B/W Illustrations
by Chapman & Hall

Also available as eBook on:

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