Instructor: Prashant Nalini Vasudevan
TA: Kareem Shehata
Lectures: Thu 4pm - 6pm
Tutorials: Tue 2pm - 3pm
Location: COM1-VCRM (COM1-02-13)
Modern cryptographic primitives can generate strings that look random, send messages that only intended recipients can read, authenticate individuals, run computations on sensitive data without compromising privacy, and perform several other seemingly paradoxical tasks.
We will study a number of these primitives with emphasis on how to:
define their security requirements rigorously,
construct them, and,
prove that these constructions are secure
We will focus on the theoretical foundations that they are built upon, using tools from algebra, number theory, combinatorics, and probability. This will involve rigorous mathematical definitions and proofs.
Pre-requisites: The following modules are pre-requisites:
CS1231/CS1231S (Discrete Structures)
CS3230 (Design and Analysis of Algorithms)
ST2334 (Probability and Statistics) or ST2131 or MA2216
Having taken CS4236 (Cryptography Theory and Practice) would be helpful, but is not necessary.
| Week | Date | Topics |
| 1 | Jan 12 | Introduction, Security Definitions, Computational Hardness |
| 2 | Jan 19 | Pseudo-Random Generators, Security Reductions |
| 3 | Jan 26 | Pseudo-Random Functions, Secret-Key Encryption, Security Games |
| 4 | Feb 2 | One-Way Functions |
| 5 | Feb 9 | Public-Key Cryptography |
| 6 | Feb 16 | Security from Algebra: Diffie-Hellman, Discrete Log |
| 7 | Mar 2 | Security from Number Theory: RSA, Quadratic Residuosity |
| 8 | Mar 9 | Digital Signatures, CCA-secure Encryption |
| 9 | Mar 16 | Hashing, Random Oracle Model |
| 10 | Mar 23 | Secure Multi-Party Computation, Garbled Circuits |
| 11 | Mar 30 | Zero-Knowledge |
| 12 | Apr 4 | Lattice-Based Cryptography (in tutorial slot) |
| 13 | Apr 11 | Homomorphic Encryption (in tutorial slot) |
| 13 | Apr 13 | Program Obfuscation, Review |
| Week | Date | Topics |
| 2 | Jan 17 | Probability, Tail Bounds |
| 4 | Jan 31 | Complexity Theory |
| 5 | Feb 7 | Review |
| 6 | Feb 14 | Group Theory |
| 7 | Feb 28 | Number Theory |
| 8 | Mar 7 | Circuits |
| 9 | Mar 14 | Review |
| 10 | Mar 21 | Secret Sharing |
| 11 | Mar 28 | Interactive Proofs |
Grading will be based on:
Problem sets (40%)
Scribing (10%)
Midterm exam (25%)
Final project (25%)
Problem Set 1: released 13 Jan, due 20 Jan
Problem Set 2: released 27 Jan, due 10 Feb
Problem Set 3: released 17 Feb, due 10 Mar
Problem Set 4: released 17 Mar, due 31 Mar
Submissions are due at 23:59 on the respective dates. Late submissions will be accepted during the subsequent 48 hours, but their score will be scaled down linearly with time (e.g., a submission that is 12 hours late will only be given 75% of the marks it deserves, and one that is 48 hours late will be given 0%). Extensions will only be granted for medical reasons and emergencies.
Every lecture (except the first) will be scribed by 2-3 students. The scribe notes should be written in latex, and should be complete and polished - see the notes for the first lecture for an example. The notes for each lecture are to be submitted before the subsequent lecture. The procedure for signing up will be discussed in class. The latex templates to be used may be downloaded here.
Time: 18 March, 10am to noon
Venue: COM1-VCRM (tentative)
The final project will involve reading a few topically related papers and writing a survey of them. Details will be posted later.
There is no prescribed textbook for the course, but many of the topics we will cover may be found in the references below. I will update this list over the course of the semester. With your help, we will also be preparing notes for the lectures, which you can use for reference afterward.
Textbooks on cryptography
Introduction to Modern Cryptography, by Jonathan Katz and Yehuda Lindell
The Foundations of Cryptography (Volumes 1 and 2), by Oded Goldreich
The Joy of Cryptography, by Mike Rosulek
Lecture Notes on Cryptography, by Goldwasser and Bellare
Other courses on the foundations of cryptography
6.875 Foundations of Cryptography, by Vinod Vaikuntanathan at MIT, Fall 2022
CS7810 Foundations of Cryptography, by Daniel Wichs at Northeastern University, Fall 2017
CS276 Cryptography, by Sanjam Garg at UC Berkeley, Fall 2014
CMSC858K Advanced Topics in Cryptography, by Jonathan Katz at University of Maryland, Spring 2004
Other references
Tutorials on the Foundations of Cryptography, edited by Yehuda Lindell
A Graduate Course in Applied Cryptography, by Dan Boneh and Victor Shoup
By the end of this module, students should develop:
An understanding of the theoretical foundations of cryptography and its connections to other areas of computer science.
An understanding of the source of security in advanced cryptographic primitives.
The ability to define and construct new cryptographic primitives tailored to various applications.
The ability to prove the security of advanced cryptographic constructions using reductions to computational hardness assumptions.
A knowledge of the capabilities of modern cryptographic primitives that are available for them to use in applications.