Cryptography plays a key role in ensuring the privacy and integrity of data and the security of computer networks. Introduction to Modern Cryptography provides a rigorous yet accessible treatment of modern cryptography, with a focus on formal definitions, precise assumptions, and rigorous proofs.

The authors introduce the core principles of modern cryptography, including the modern, computational approach to security that overcomes the limitations of perfect secrecy. An extensive treatment of private-key encryption and message authentication follows. The authors also illustrate design principles for block ciphers, such as the Data Encryption Standard (DES) and the Advanced Encryption Standard (AES), and present provably secure constructions of block ciphers from lower-level primitives. The second half of the book focuses on public-key cryptography, beginning with a self-contained introduction to the number theory needed to understand the RSA, Diffie-Hellman, El Gamal, and other cryptosystems. After exploring public-key encryption and digital signatures, the book concludes with a discussion of the random oracle model and its applications.

Serving as a textbook, a reference, or for self-study, Introduction to Modern Cryptography presents the necessary tools to fully understand this fascinating subject.

PREFACE

INTRODUCTION AND CLASSICAL CRYPTOGRAPHY

INTRODUCTION

Cryptography and Modern Cryptography

The Setting of Private-Key Encryption

Historical Ciphers and Their Cryptanalysis

The Basic Principles of Modern Cryptography

PERFECTLY SECRET ENCRYPTION

Definitions and Basic Properties

The One-Time Pad (Vernam's Cipher)

Limitations of Perfect Secrecy

Shannon's Theorem

Summary

PRIVATE-KEY (SYMMETRIC) CRYPTOGRAPHY

PRIVATE-KEY ENCRYPTION AND PSEUDORANDOMNESS

A Computational Approach to Cryptography

A Definition of Computationally Secure Encryption

Pseudorandomness

Constructing Secure Encryption Schemes

Security against Chosen-Plaintext Attacks (CPA)

Constructing CPA-Secure Encryption Schemes

Security against Chosen-Ciphertext Attacks (CCA)

MESSAGE AUTHENTICATION CODES AND COLLISION-RESISTANT HASH FUNCTIONS

Secure Communication and Message Integrity

Encryption vs. Message Authentication

Message Authentication Codes-Definitions

Constructing Secure Message Authentication Codes

CBC-MAC

Collision-Resistant Hash Functions

NMAC and HMAC

Constructing CCA-Secure Encryption Schemes

Obtaining Privacy and Message Authentication

PRACTICAL CONSTRUCTIONS OF PSEUDORANDOM PERMUTATIONS (BLOCK CIPHERS)

Substitution-Permutation Networks

Feistel Networks

The Data Encryption Standard (DES)

Increasing the Key Size of a Block Cipher

The Advanced Encryption Standard (AES)

Differential and Linear Cryptanalysis-A Brief Look

THEORETICAL CONSTRUCTIONS OF PSEUDORANDOM OBJECTS

One-Way Functions

Overview: From One-Way Functions to Pseudorandomness

A Hard-Core Predicate for Any One-Way Function

Constructing Pseudorandom Generators

Constructing Pseudorandom Functions

Constructing (Strong) Pseudorandom Permutations

Necessary Assumptions for Private-Key Cryptography

A Digression-Computational Indistinguishability

PUBLIC-KEY (ASYMMETRIC) CRYPTOGRAPHY

NUMBER THEORY AND CRYPTOGRAPHIC HARDNESS ASSUMPTIONS

Preliminaries and Basic Group Theory

Primes, Factoring, and RSA

Assumptions in Cyclic Groups

Cryptographic Applications of Number-Theoretic Assumptions

FACTORING AND COMPUTING DISCRETE LOGARITHMS

Algorithms for Factoring

Algorithms for Computing Discrete Logarithms

PRIVATE-KEY MANAGEMENT AND THE PUBLIC-KEY REVOLUTION

Limitations of Private-Key Cryptography

A Partial Solution-Key Distribution Centers

The Public-Key Revolution

Diffie-Hellman Key Exchange

PUBLIC-KEY ENCRYPTION

Public-Key Encryption-An Overview

Definitions

Hybrid Encryption

RSA Encryption

The El Gamal Encryption Scheme

Security against CCA

Trapdoor Permutations

ADDITIONAL PUBLIC-KEY ENCRYPTION SCHEMES

The Goldwasser-Micali Encryption Scheme

The Rabin Encryption Scheme

The Paillier Encryption Scheme

DIGITAL SIGNATURE SCHEMES

Digital Signatures-An Overview

Definitions

RSA Signatures

The Hash-and-Sign Paradigm

Lamport's One-Time Signature Scheme

Signatures from Collision-Resistant Hashing

The Digital Signature Standard

Certificates and Public-Key Infrastructures

PUBLIC-KEY CRYPTOSYSTEMS IN THE RANDOM ORACLE MODEL

The Random Oracle Methodology

Public-Key Encryption in the Random Oracle Model

Signatures in the Random Oracle Model

APPENDIX A: MATHEMATICAL BACKGROUND

Identities and Inequalities

Asymptotic Notation

Basic Probability

The Birthday Problem

APPENDIX B: SUPPLEMENTARY ALGORITHMIC NUMBER THEORY

Integer Arithmetic

Modular Arithmetic

Finding a Generator of a Cyclic Group

INDEX

Each chapter contains References, Additional Reading, and Exercises.

This book is a comprehensive, rigorous introduction to what the authors name ‘modern’ cryptography … a novel approach to how cryptography is taught, replacing the older, construction-based approach. … The concepts are clearly stated, both in an intuitive fashion and formally. … I would heartily recommend this book to anyone who is interested in cryptography. … the exercises are challenging and interesting, and can benefit readers of all academic levels. …

—IACR book reviews, January 2010

Over the past 30 years, cryptography has been transformed from a mysterious art into a mathematically rigorous science. The textbook by Jonathan Katz and Yehuda Lindell finally makes this modern approach to cryptography accessible to a broad audience. Readers of this text will learn how to think precisely about the security of protocols against arbitrary attacks, a skill that will remain relevant and useful regardless of how technology and cryptography standards change. The book uses just enough formalism to maintain precision and rigor without obscuring the development of ideas. It manages to convey both the theory's conceptual beauty and its relevance to practice. I plan to use it every time I teach an undergraduate course in cryptography.

—Salil Vadhan, Harvard University, Cambridge, Massachusetts, USA

… the greatest attribute is the fact that the material is presented in such a unified way. These are not just a collection of topics from cryptography, thrown together at random. One topic leads effortlessly to the next. As such, this is a virtually indispensible resource for modern cryptography.

—Donald L. Vestal, South Dakota State University, *MAA Online*, July 2008

… gives an excellent introduction to the theoretical background of cryptography. It would be a fine textbook for an advanced undergraduate (or graduate) course in theoretical computer science for students who have already seen the rudiments of cryptography. It will be a valuable reference for researchers in the field …

—Steven D. Galbraith, *Mathematical Reviews*, 2009b

The book is highly recommended as a textbook in cryptography courses at graduate or advanced undergraduate levels … covers in a splendid way the main notions of current cryptography from the point of view of information-theoretical security. This corresponds indeed to a modern cryptography approach.

—Guillermo Morales-Luna, *Zentralblatt MATH*, Vol. 1143