This is the webpage for the Northeastern University course Cryptography (CY 4770) in Spring, 2021.
Pre-requisites:The main pre-requisite is mathematical maturity and comfort with understanding/writing proofs. Familiarity with basic probability and discrete math is assumed (e.g., of conditional probability, modular arithmetic, and the big O notation). Prior knowledge on number theory is not assumed, but may be useful - we will cover the required background in class.
Grading: The final grade will be based on:
Lateness and Collaboration Policy:
Lecture | Topics Covered | Relevant Reading (based on KL, 2nd edition) | Problem Set | Quiz |
---|---|---|---|---|
L1 (Jan 21) | Introduction, encryption problem, perfect secrecy | Chapters 1, 2.1 | ||
L2 (Jan 25) | One-time pad, Shannon's Theorem, computational security, PRG | Chapters 2.2-3, 3.1-3 | PS1, due Feb 8 | |
L3 (Jan 28) | More on PRG, OWF, encrypting multiple messages, CPA security | Chapters 7.1.1, 7.4.2, 3.4 | Quiz 1, due Feb 1 | |
L4 (Feb 1) | PRF, CPA-secure encryption from PRF | Chapter 3.5 | ||
L5 (Feb 4) | PRF from PRG, PRP, block ciphers | Chapter 3.5 | Quiz 2, due Feb 8 | |
L6 (Feb 8) | Modes of operation | Chapter 3.6 | PS2, due Feb 22 | |
L7 (Feb 11) | CCA security, padding-oracle attacks | Chapter 3.7 | Quiz 3, due Feb 15 | |
No lecture (Feb 15) | Presidents' Day | |||
L8 (Feb 18) | MACs | Chapter 4 | Quiz 4, due Feb 24 | |
L9 (Feb 22) | Hash functions | Chapters 5.1, 5.2, 5.4 | PS3, due Mar 8 | |
L10 (Feb 25) | Hash functions continued, basic number theory | Chapters 5.5, 8.1.1 | Quiz 5, due Mar 3 | |
L11 (Mar 1) | Modular arithmetic, basic group theory | Chapters 8.1.2, 8.1.3, B.1 | ||
L12 (Mar 4) | Basic group theory, the factoring assumption | Chapters 8.1.4, 8.2.1, 8.2.3, 8.4.1 | Quiz 6, due Mar 10 | |
L13 (Mar 8) | The RSA assumption, CRT, cyclic groups | Chapters 8.1.5, 8.2, 8.3.1 | PS4, due Mar 22 | |
L14 (Mar 11) | DL, CDH, DDH | Chapters 8.3, 8.4.2, 9.2.1, 9.2.2 | Quiz 7, due Mar 17 | |
L15 (Mar 15) | Key Agreement, the Diffie-Hellman protocol | Chapter 10 | ||
L16 (Mar 18) | El Gamal encryption | Chapters 11.1, 11.2, 11.4.1 | Quiz 8, due Mar 24 | |
L17 (Mar 22) | KEM, Textbook RSA | Chapters 11.3, 11.4.2, 11.4.3, 11.5.1 | PS5, due Apr 5 | |
L18 (Mar 25) | Padded RSA | Chapters 11.5.2, 11.5.4 | Quiz 9, due Mar 31 | |
L19 (Mar 29) | RSA-based KEM (CPA/CCA) | Chapter 11.5.5 | ||
L20 (Apr 1) | Digital signatures, RSA-FDH | Chapters 12.1, 12.2, 12.3, 12.4 | Quiz 10, due Apr 7 | |
L21 (Apr 5) | Schnorr's signatures | Chapter 12.5.1 | PS6, due Apr 19 | |
L22 (Apr 8) | (EC)DSA, Lamport's signatures, certificates, TLS | Chapters 12.5.2, 12.6, 12.7, 12.8 | Quiz 11, due Apr 14 | |
No lecture (Apr 12) | ||||
L23 (Apr 15) | Signcryption, pairings, 3-party KA, BLS, IBE, Boneh-Franklin | |||
L24 (Apr 19) | MPC, oblivious transfer, garbled circuits, Yao's protocol |
We will follow the textbook Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell. There is no need to purchase the book as we will cover all relevant material in class. Note that there are 3 editions to this book, but we will cover basic material that is clearly presented in all 3 editions, so prior editions will also be very useful.