Introduction to Modern Cryptography: Principles and Protocols

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.