---

General description

Cryptography delivers tools for protecting confidentiality and integrity of data. These tools are already used at scale to protect billions of daily online transactions, e.g., within the TLS protocol, in end-to-end encrypted messaging applications (like Signal), and in a myriad of other applications. At the same time, modern cryptography has developed a number of tools whose end goal extends beyond that of solely protecting confidentiality and integrity, such as zero-knowledge proofs, secure multi-party computation, and fully-homomorphic encryption. In addition to its benefits to computer security, a unique aspect of modern cryptography is how it interfaces with theoretical computer science -- both by adopting tools and techniques, but also by inspiring problems and directions.

This course gives a comprehensive introduction to cryptography. The focus is on (1) understanding how existing tools work; (2) how to formalize the security goals they achieve, and (3) how to prove that they achieve these goals. The class will aim to be both of interest to theory students, as well as to a broader audience interested in using cryptography in a sound way. In partcular, a main objective is exposure to the paradigm of provable security which allows us to reason rigorously about cryptographic security.

Topics will include (tentative): Cryptographic pseudorandomness, encryption (secret- and public-key), key-agreement, authentication, hash functions, digital signatures, basics of post-quantum cryptography, introduction to cryptographic protocols (multi-party computation and zero-knowledge proofs)

Required background. Students are expected to be ready to understand and write mathematical definitions and proofs. Exposure to basic probability, discrete mathematics, and theory of computing is also expected. (If in doubt, please reach out to the instructor.)

---

Resources

There is no mandatory textbook. Reading materials will be posted throughout the class. Hower, the following are good references:

• R. Pass and a. shelat. A Course in Cryptography (graduate level, focusing on theory)
• M. Rosulek. The Joy of Cryptography (undergraduate level, broader scope)
• O. Goldreich. The Foundations of Cryptography (a thorough and formal textbook on foundations.)
• J. Katz and Y. Lindell. Introduction to Modern Cryptography (a textbook, graduate level)
• D. Boneh and V. Shoup A Graduate Course in Applied Cryptography (a textbook, graduate level)
• M. Bellare and P. Rogaway's lecture notes. Introduction to Modern Cryptography (lecture notes for a grad class, focus on practice-oriented provable security)

A good overview on secure multi-party computation is available in this free textbook

---

Grading

There will be four homework assignments (to be solved in teams of two students), and a take home final (to be solved individually). The grading split will be, roughly: Homework (60%), Final (30%), Participation (10%)

---

Schedule

This is a tentative schedule meant to give an overview of the topics we are going to cover. It will be expanded/refined as we proceed through the quarter.

Wk	Date	Lecture contents	Reading
1	3/31	Introduction Formal details Examples of Cryptographic Applications Introduction to games and advantages	[Lecture 1]
	4/2	Unpredictability and Pseudorandomness I Generic attacks against UF-CMA security Computational efficiency Concrete vs asymptotic security Reductions: Key-recovery, random messages, and multiple verification queries	[Lecture 2] [Lecture 2 (annotated)]
2	4/7	Unpredictability and Pseudorandomness II Definition of pseudorandom functions (PRFs) UF-CMA vs PRF Range extension and hybrid argument	[Lecture 3] [Lecture 3 (annotated)]
	4/9	Pseudorandomness, Introduction to Encryption Hybrid argument/game hopping Block ciphers Security/syntax of secret-key encryption	[Lecture 4] [Lecture 4 (annotated)] [Homework 1]
3	4/14	Secret-key Encryption I Encryption from PRFs Modes of operation Intro to authenticated encryption	[Lecture 5] [Lecture 5 (annotated)]
	4/16	Secret-key encryption / Intro to algebra Plaintext and ciphertext integrity Generic composition: Encrypt-then-MAC Introduction to Algebra	[Lecture 6] [Lecture 6 (annotated)]
4	4/21	Groups and Number Theory Finite Groups Modular Arithmetic Exponentiations and Discrete Logarithms The hardness of the Discrete Logarithm problem
	4/23	Hard Problems in Groups Elliptic Curves Diffe-Hellman Key Exchange The DDH Assumption Detour: PRF construction from DDH	[Homework 2]
5	4/28	Public-key Encryption I IND-CPA and IND-CCA security ElGamal Encryption One vs Many Encryptions
	4/30	Public-key Encryption II The Random-Oracle Model The Fujisaki-Okamoto transform
6	5/5	Digital Signatures I UF-CMA security of signaturs Application: Authenticated Key Exchange Hash functions Trapdoor Permutations and the Full-Domain Hash	[Homework 3]
	5/7	Digital Signatures II Schnorr Signatures
7	5/12	Lattice-Based Cryptography I A brief introduction to lattices and shortest vectors The LWE assumption Regev Encryption
	5/14	Lattice-Based Cryptography II Lattice trapdoors Lattice-based signatures
8	5/19	Fully-Homomorphic Encryption The GSW Construction Application: Private Information Retrieval
	5/21	Multi-Party Computation I 2PC Security Definition Garbled Circuits and Oblivious Trasnfer	[Homework 4]
9	5/26	Memorial day
	5/28	Multi-Party Computation II Secret Sharing and the GMW Protocol
10	6/2	Zero-Knowledge I General formalism Zero-knowledge proofs for NP
	6/4	Zero-Knowledge II Non-interactive zero-knowledge