Introduction to Modern Cryptography

University of Maryland, College Park, USA Bar-Ilan University, Ramat Gan, Israel

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.