You are here

Introduction to Modern Cryptography

Jonathan Katz and Yehuda Lindell
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2008
Number of Pages: 
534
Format: 
Hardcover
Series: 
Chapman & Hall/CRC Cryptography and Network Security
Price: 
79.95
ISBN: 
9781584885511
Category: 
Textbook
[Reviewed by
Donald L. Vestal
, on
06/13/2008
]

In the information age, one of the most common applications of mathematics is cryptography. Throughout the twentieth century, mathematicians tried to develop a cogent theory to explain the various encryption schemes and try to measure their security. This book gives a nice overview of this theory. It mentions some of the history and presents the mathematical ideas in a precise manner.

The topics covered include: the key principles that an encryption scheme should satisfy as well as attack scenarios that they should survive, Shannon’s Theorem on perfect secrecy, Computationally-Secure Encryption, the use of pseudorandom functions to create CPA-Secure Encryption Schemes, creating Secure Message Authentication Codes and collision resistant hash functions (including the Markle-Damgård transform), combining encryption and authentication, design principles for constructing (modern) block ciphers, the theory behind the constructing pseudorandom objects, primality testing and implications for the RSA system, discrete logarithms and Diffie-Hellman problems, elliptic curve groups, algorithms for factoring (Pollard’s p–1 method, Pollard’s rho method, and the Quadratic Sieve, algorithms for computing discrete logarithms (the baby-step/giant-step method and the Pohlig-Hellman algorithm) , management and distribution of private keys, the Diffie-Hellman key exchange, Public-Key Encryption (including the issue of security), combinations of public- and private-key schemes, the RSA and El Gamal Encryption schemes, the use of trapdoor permutations, other Public-Key Encryption schemes (the Goldwasser-Micali scheme, the Rabin scheme, and the Paillier scheme), digital signatures , digital certificates, message integrity, and the Random Oracle Model in validating cryptographic schemes.

The book contains enough information to serve as a textbook for an undergraduate course as well as a graduate course. Also, since the authors intend for the material to be mathematically rigorous, appendices with appropriate mathematical background are included. Each chapter ends with a collection of exercises and a list of 149 references is included. If I could change one thing, it would be this; the authors use many acronyms (such as CPA for “chosen plaintext attack”), and while there is a list of common notation just before the appendices, not all terms are included. I think a more complete list might have been handy .

However, 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 is an Assistant Professor of Mathematics at South Dakota State University. His interests include number theory, combinatorics, spending time with his family, and working on his hot sauce collection. He can be reached at Donald.Vestal(AT)sdstate.edu.

 

 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

Dummy View - NOT TO BE DELETED