CS 7810 - Foundations of Cryptography, Fall 2025

Course Description

Cryptography is the science of protecting information against adversarial eavesdropping and tampering. Although people have been fascinated with cryptography since ancient times, it has only recently blossomed into a scientific discipline with rigorous mathematical foundations and methodologies. In this graduate course, intended for students at the PhD level, we will provide an accelerated introduction to modern cryptography and quickly progress to advanced topics that are at the forefront of current research. We will start by understanding what kind of security properties can be achieved by relying solely on probability and information theory, without restricting the adversary's computational power. We will then study the complexity-theoretic basis of modern cryptography and the connection between computational hardness and pseudoradnomness. As the main component of the course, we will explore how to take a few well-studied problems in number theory and algebra and use them to build powerful cryptosystems with advanced functionality and security properties such as public-key encryption, digital signatures, multi-party computation, fully-homomorphic encryption, etc.

Prerequisites: The main pre-requisite is a high degree of mathematical maturity. We will also rely on some rudimentary knowledge of probability, algorithms, and theory of computation. No prior knowledge of cryptography or number theory is required (but some familiarity will be helpful).

Although the course is intended for PhD students, interested undergraduate and Masters students are encouraged to contact the instructor.

Logistics

Lecture Time: Monday, Thursday: 11:45 am - 1:25 pm (Tentative)
Location: Ell Hall 410 (Tentative)
Instructor: Daniel Wichs. Email: (instructor's five-letter last name)@ccs.neu.edu.
Office hours: By appointment. Office 177 Huntington 622.

Grading

Problem Sets 70%, Final Project 30%

Resources

There is no required textbook. We will rely on lecture notes from a previous version of this class: course notes 2017.
The following textbook is useful as a reference: Introduction to Modern Cryptography by Katz and Lindell.
Other useful resources include:
MIT Course by Vinod Vaikuntanathan
Graduate Crypto Book by Dan Boneh and Victor Shoup.
Lecture Notes by Rafael Pass and Abhi Shelat.
Lecture notes by Yevgeniy Dodis
Lecture notes by Chris Peikert
Lecture notes by Boaz Barak.
Slides by Stefan Dziembowski.
Slides,Notes by Gil Segev.

Problem Sets

Problem sets will be posted here. Use latex to write up your solutions. A template file is provided for you for each problem set. You should try to solve each problem on your own. If you can't solve the problem on your own, you are allowed to discuss with others from the class. However, you must write down the solution on your own. You should also write down who you discussed each problem with. You are not allowed to use any other external resources.

Lectures

Class/Date Topic Covered Notes
Class 1, 1/6: introduction, perfect secrecy, one-time pad, optimality. scribe notes , slides
Class 2, 1/9: authentication, secret sharing scribe notes.
Class 3, 1/13: multiparty computation scribe notes.
Class 4, 1/16: statistical security, computational security, indistinguishability scribe notes.
Class 5, 1/23: pseudorandom generators (PRGs), increasing the output sizescribe notes
Class 6, 1/27: pseudorandom functions (PRFs), GGM construction from PRGs, CPA security class slides, PRF notes, CPA notes
Class 7, 1/30: MACs from PRFs, One-way functions MAC slides, OWF Slides, notes
Class 8, 2/3: Hardcore Bits, Goldreich-Levin theorem OWF Slides, scribe notes I, scribe notes II (from 2015)
Class 9, 2/6: hash functions, Merkle-Damgaard, Merkle Tree, random oracle scribe notes
Class 10, 2/10: number theory, cyclic groups scribe notes
Class 11, 2/13: discrete logarithms, CDH and DDH assumptions, Diffie-Hellman Key-Agreement scribe notes
Class 12, 2/20: ElGamal Encryption, hash functions from DL, PRGs from DDH, Naor-Reingold PRF scribe notes
Class 13, 2/24 trapdoor-permutations, RSA, Rabin scribe notes
Class 14, 2/27 lattice-based cryptography slides
Class 15,16 3/10 and 3/13: Signatures from CRHFs (and OWFs) scribe notes, slides
Class 17,18 3/17,3/20: zero-knowledge proofs for NP slides, scribe notes 1, scribe notes 2 scribe notes 3
Class 19,20 3/24, 3/27: multiparty computation slides


Tentative Syllabus

Information-Theoretic Cryptography
Foundations of Symmetric-Key Cryptography
Number-Theory Assumptions and Cryptosystems I Sigma Protocols, Signatures, and Zero-Knowledge Proofs Assumptions and Cryptosystems II Advanced Topics (depending on time and interest)