Modern Cryptography

CSc 80010–Fall 2018

CUNY Graduate Center
Computer Science Department

Instructor: Dr. Nelly Fazio
Lectures: Thursdays, 11:45am–1:45pm (Room 3310B)
Office hours: By appointment (Room 4439)
Email: nfazio AT gc DOT cuny DOT edu

[ Course Description | List of Topics | Textbook | Weekly Schedule ]

Course Description

This introductory, graduate-level course covers the theoretical foundations of modern cryptography. Emphasis will be placed on precise definitions, rigorous proof techniques, and analysis of the relations among the various cryptographic primitives (such as one-way functions, pseudo-random generators, pseudo-random permutations, and trapdoor permutations). List of topics includes: computational security, cryptographic hash functions, private-key encryption, message authentication codes, public-key encryption, digital signatures, commitment schemes. No previous knowledge of cryptography is required. However, general ease with algorithms and elementary probability theory, and maturity with mathematical proofs will be assumed.


Required: Recommended:

List of Topics

Weekly Schedule (tentative)

Lecture Topic Readings
1 Introduction. Classical vs. Modern Cryptography.
Brush-up on Probability Theory. Information-Theoretic Security.
KL Ch. 1–2
KL Appendix A
2 More on Perfect Secrecy. From Information Theory to the Computational Approach. KL Ch. 3.1
3 Brush-up on Number Theory. KL Appendix B
KL Ch. 7.1, 7.2.1,
7.2.3-7.2.4, 7.3.1-7.3.3
4 Computational-Secure Private-Key Encryption. Pseudorandomness. Pseudorandom generators. KL Ch. 3.2–3.4.2
5 One-Way Functions. One-Way Permutations. OWF Candidate: Integer Multiplication. OWP Candidate: Modular Exponentiation.
Quadratic Residue. Legendre Symbol. LSB. MSB. Hardcore Bits. Goldreich-Levin Theorem.
KL 6.1, 6.2,
6.3.1, 7.4.1
6 Next-Bit Unpredictability. Blum/Micali Construction. Pseudo Random Generators.
Computational Indistinguishability. Hybrid Argument.
KL 6.4
7 Blum-Micali construction. Efficient instantiation: Blum-Blum-Shub construction.
Pseudo-random functions (PRF). Goldreich-Goldwasser-Micali construction.
Application of PRF. Pseudo-random permutations (PRP). Feistel Network. Luby-Rackoff construction.
KL 3.6.1, 6.5
KL 3.6.2, 3.6.3, 6.6
8 Security for Multiple Encryptions. Security Against Chosen-Plaintext Attacks (CPA).
Security Against Chosen-Ciphertext Attacks (CCA). Block-ciphers and mode of operations.
Integrity. Message Authentication Codes (MACs).
ε-universal, universal one-way, and collision resistant hash functions.
Merkle-Damgaard construction. Hash-then-MAC paradigm.
KL 3.4.3, 3.5
3.6.2-3.6.4, 3.7
KL 4.1–4.6.4
9 Diffie-Hellman Key Exchange. Asymmetric Setting. Computationally-Secure
Public-Key Encryption. Security Against Chosen-Plaintext Attacks (CPA).
KL 9, 10.1–10.2
10 Security for Multiple Encryptions. Hybrid Encryption. ElGamal.
Security Against Chosen-Ciphertext Attacks (CCA).
KL 10.2.2, 10.3, 10.5, 10.6
11 Trapdoor Permutations and Hardcore Predicates. Blum-Goldwasser
Construction. Example of trapdoor permutations: RSA. OAEP. OAEP+
KL 10.4 10.7
12 Digital Signatures. The Hash_then_Sign paradigm.
One Time Signature Schemes. Lamport's Scheme.
Rabin and RSA Schemes. Padding Schemes (PSSR).
KL 12.1–12.5
13 Schnorr signature scheme. Signature schemes for multiple messages:
"chain-based" signatures and "tree-based" signatures
KL 12.6
14 TBD
Final Report Presentations

Copyright © Nelly Fazio