Introduction to Modern Cryptography

By Jonathan Katz, Yehuda Lindell. 2020

2,534 citations recorded by the source corpus.

Preface 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

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Zerocash: Decentralized Anonymous Payments from Bitcoin (2014, background): “We assume familiarity with the deﬁnitions of these building blocks; for more details, see, e.g., [27].”
Evading Classifiers by Morphing in the Dark (2017, methodology): “Under HsrMorpher , the morpher operates in the same way as the Random Oracle [17] employed in the studies of hash functions does, producing truly random outcomes for unique query, and being consistent with repeated queries.”
Secure Multiparty Computation for Privacy-Preserving Data Mining (2009, background): “For those interested in going a step further, we recommend (28) for a general introduction to cryptography, and (20; 21) for a rigorous and in-depth study of the foundations of cryptography.”
Verifying computations with state (2013, methodology): “To support variable-length input, we use a prefix-free variant of the Merkle-Damgård transform [44, Ch. 4.6.4] that prepends the input with its length [25].”
Distributed Internet-Based Load Altering Attacks Against Smart Power Grids (2011, background): “Some details on private key encryption and related implementation issues can be found in [25].”
Countering GATTACA: efficient and secure testing of fully-sequenced human genomes (2011, background): “For ease of exposition, we omit basic notions and refer to [31, 46, 57] for details on various cryptographic primitives, such as hash functions, number-theoretic assumptions, as well as encryption and signature schemes.”
The Melbourne Shuffle: Improving Oblivious Storage in the Cloud (2014, methodology): “We require this scheme to be secure against the chosen-ciphertext attack (CPA) for multiple messages [16].”
Structured Encryption and Controlled Disclosure (2010, background): “We refer the reader to [25] for formal definitions of CPA-security, PRFs and PRPs.”
Paragon: QoS-aware scheduling for heterogeneous datacenters (2013, methodology): “We hash the scores of tolerated interference of each server using variations of SHA-1 [22] as differ ent hash functions (hj ) for each SoI to increase entropy.”
Privacy-Preserving Computation with Trusted Computing via Scramble-then-Compute (2017, methodology): “S first generates a permutation πo using a secure pseudo-random permutation [29].”
Parallel and Dynamic Searchable Symmetric Encryption (2013, methodology): “We refer the reader to [12] for formal definitions of CPA-security, PRFs and random oracles.”
Hyperproperties (2010, background): “A private-key encryption scheme satisfies perfect indistinguishability [32] if the probability distribution on ciphertexts is the same for all plaintexts.”
TrustVisor: Efficient TCB Reduction and Attestation (2010, methodology): “The data sealed by a μTPM is protected using authenticated encryption [18] with keys maintained by TrustVisor itself.”