I. Introduction and Classical Cryptography 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 Exercises Perfectly Secret Encryption Definitions The One-Time Pad Limitations of Perfect Secrecy Shannon's Theorem References and Additional Reading Exercises II. Private-Key (Symmetric) Cryptography Private-Key Encryption Computational Security The Concrete Approach The Asymptotic Approach Defining Computationally Secure Encryption The Basic Definition of Security Semantic Security Constructing Secure Encryption Schemes Pseudorandom Generators and Stream Ciphers Proofs by Reduction A Secure Fixed-Length Encryption Scheme Stronger Security Notions Security for Multiple Encryptions Chosen-Plaintext Attacks and CPA-Security Constructing CPA-Secure Encryption Schemes Pseudorandom Functions and Block Ciphers CPA-Secure Encryption from Pseudorandom Functions Modes of Operation Stream-Cipher Modes of Operation Block-Cipher Modes of Operation Chosen-Ciphertext Attacks Defining CCA-Security Padding-Oracle Attacks References and Additional Reading Exercises Message Authentication Codes Message Integrity Secrecy vs. Integrity Encryption vs. Message Authentication Message Authentication Codes - Definitions Constructing Secure Message Authentication Codes A Fixed-Length MAC Domain Extension for MACs CBC-MAC The Basic Construction Proof of Security Authenticated Encryption Definitions Generic Constructions Secure Communication Sessions CCA-Secure Encryption Information-Theoretic MACs Constructing Information-Theoretic MACs Limitations on Information-Theoretic MACs References and Additional Reading Exercises Hash Functions and Applications Definitions Collision Resistance Weaker Notions of Security Domain Extension: The Merkle-Damgard Transform Message Authentication Using Hash Functions Hash-and-MAC HMAC Generic Attacks on Hash Functions Birthday Attacks for Finding Collisions Small-Space Birthday Attacks Time/Space Tradeoffs for Inverting 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 Exercises Practical Constructions of Symmetric-Key Primitives Stream Ciphers Linear-Feedback Shift Registers Adding Nonlinearity Trivium RC4 Block Ciphers Substitution-Permutation Networks Feistel Networks DES - The Data Encryption Standard 3DES: Increasing the Key Length of a Block Cipher AES - The Advanced Encryption Standard Differential and Linear Cryptanalysis Hash Functions Hash Functions from Block Ciphers MD5 SHA-0, SHA-1, and SHA-2 SHA-3 (Keccak) References and Additional Reading Exercises Theoretical Constructions of Symmetric-Key Primitives One-Way Functions Definitions 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 Exercises III. Public-Key (Asymmetric) Cryptography Number Theory and Cryptographic Hardness Assumptions Preliminaries and Basic Group Theory Primes and Divisibility Modular Arithmetic Groups 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 RSA and Factoring 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 Constructing Collision-Resistant Hash Functions References and Additional Reading Exercises Algorithms for Factoring and Computing Discrete Logarithms Algorithms for Factoring Pollard's p 1 Algorithm Pollard's Rho Algorithm The Quadratic Sieve Algorithm Algorithms for Computing Discrete Logarithms The Pohlig-Hellman Algorithm The Baby-Step/Giant-Step Algorithm Discrete Logarithms from Collisions The Index Calculus Algorithm Recommended Key Lengths References and Additional Reading Exercises 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 Exercises Public-Key Encryption Public-Key Encryption - An Overview Definitions Security against Chosen-Plaintext Attacks Multiple Encryptions Security against Chosen-Ciphertext Attacks Hybrid Encryption and the KEM/DEM Paradigm CPA-Security CCA-Security 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 Encryption Plain RSA Padded RSA and PKCS #1 v1.5 CPA-Secure Encryption without Random Oracles OAEP and RSA PKCS #1 v A CCA-Secure KEM in the Random-Oracle Model RSA Implementation Issues and Pitfalls References and Additional Reading Exercises Digital Signature Schemes Digital Signatures - An Overview Definitions The Hash-and-Sign Paradigm RSA Signatures Plain RSA RSA-FDH and PKCS #1 v Signatures from the Discrete-Logarithm Problem The Schnorr Signature Scheme DSA and ECDSA Signatures from Hash Functions Lamport's Signature Scheme Chain-Based Signatures Tree-Based Signatures Certificates and Public-Key Infrastructures Putting It All Together - SSL/TLS Signcryption References and Additional Reading Exercises 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 ZN2 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 Exercises Index of Common Notation Appendix A: Mathematical Background Identities and Inequalities Asymptotic Notation Basic Probability The "Birthday" Problem Finite Fields Appendix B: Basic Algorithmic Number Theory Integer Arithmetic Basic Operations The Euclidean and Extended Euclidean Algorithms Modular Arithmetic Basic Operations Computing Modular Inverses Modular Exponentiation Montgomery Multiplication Choosing a Uniform Group Element Finding a Generator of a Cyclic Group Group-Theoretic Background Efficient Algorithms References and Additional Reading Exercises References Index
Jonathan Katz is a professor of computer science at the University of Maryland, and director of the Maryland Cybersecurity Center. He has published over 100 articles on cryptography, and serves as an editor of the Journal of Cryptology, the premier journal of the field. Prof. Katz has been invited to give introductory lectures on cryptography for audiences in academia, industry, and government, as well as an on-line cryptography course through Coursera. Yehuda Lindell is a professor of computer science at Bar-Ilan University. He has published more than 90 articles on cryptography and four books, and has considerable industry experience in deploying cryptographic schemes. Professor Lindell lectures widely in both academic and industry venues on both theoretical and applied cryptography, and has been recognized with two prestigious grants from the European Research Council.
"The work is comprehensive, rigorous, and yet accessible for
-Computing Reviews, October 2015
"... this book fills a significant gap among previous
cryptography textbooks by explicitly discussing the philosophy
behind this approach, gradually building up the relevant theory and
giving a broad overview of the discipline conceived within this
framework. The result is a coherent picture of the field that
provides a pleasing clarity in its explanation of this perspective
through a systematic, step-by-step development of important
concepts. ... The material from the first edition has been
restructured and expanded, with an emphasis on practical aspects
that provides a nice counterpoint to the theory and helps to
highlight its real-world relevance. ... This textbook is
appropriate for use in teaching at either an advanced undergraduate
or graduate level ... a particularly valuable resource for graduate
students with a computer science or mathematics background who are
seeking a pathway to understanding the current cryptography
research literature. In the preface, the authors mention their aim
of treating modern cryptography through a unified approach that is
rigorous yet accessible-Introduction to Modern
Cryptography achieves this admirably."
-Mathematical Reviews, August 2015
Praise for the First Edition:
"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. This is 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
indispensable resource for modern cryptography."
-Donald L. Vestal, South Dakota State University, Brookings, USA, MAA Online, July 2008
"... 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, 2009
"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