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

    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


    2. Perfectly Secret Encryption


    The One-Time Pad

    Limitations of Perfect Secrecy

    *Shannon's Theorem

    References and Additional Reading


    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


    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


    The Basic Construction

    *Proof of Security

    GMAC and Poly

    MACs from Difference-Universal Functions


    *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


    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


    6. Hash Functions and Applications


    Collision Resistance

    Weaker Notions of Security

    Domain Extension: The Merkle-Damgard Transform

    Message Authentication Using Hash Functions



    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


    7. Practical Constructions of Symmetric-Key Primitives

    Stream Ciphers

    Linear-Feedback Shift Registers

    Adding Nonlinearity




    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


    8. *Theoretical Constructions of Symmetric-Key Primitives

    One-Way Functions


    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


    III Public-Key (Asymmetric) Cryptography

    9. Number Theory and Cryptographic Hardness Assumptions

    Preliminaries and Basic Group Theory

    Primes and Divisibility

    Modular Arithmetic


    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


    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


    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


    12. Public-Key Encryption

    Public-Key Encryption - An Overview


    Security against Chosen-Plaintext Attacks

    Multiple Encryptions

    Security against Chosen-Ciphertext Attacks

    Hybrid Encryption and the KEM/DEM Paradigm



    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


    13. Digital Signature Schemes

    Digital Signatures - An Overview


    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


    References and Additional Reading


    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


    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


    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





    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