---

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/27	Introduction Formal details Examples of Cryptographic Applications Introduction to games and advantages	[Slides] [Annotated]
	3/29	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	[Slides] [Annotated]
2	4/3	Unpredictability and Pseudorandomness II Pseudorandom functions PRFs are good MACs	[Slides] [Annotated]
	4/5	Construction pseudorandom functions Range Extension and the Hybrid Argument AES and practical PRFs	[Slides] [Annotated] [Homework 1]
3	4/10	Symmetric Encryption I Modes of operation ECB Insecurity INDR and IND-CPA Security CTR and its security	[Slides] [Annotated]
	4/12	Symmetric Encryption II Integrity attacks Plaintext and ciphertext integrity Generic composition: Encrypt-then-MAC Wegman-Carter MACs	[Slides] [Annotated]
4	4/17	Groups and Number Theory Finite Groups Modular Arithmetic Cyclic Groups Exponentiations and Discrete Logarithms Universal Hash Functions from Modular Arithmetic	[Slides] [Annotated]
	4/19	Hard Problems in Groups The hardness of the DL problem Elliptic Curves Diffe-Hellman Key Exchange The DDH Assumption	[Slides] [Annotated] [Homework 2]
5	4/24	Public-key Encryption I IND-CPA Security ElGamal Encryption One vs Many Encryptions	[Slides] [Annotated]
	4/26	Public-key Encryption II RSA Trapdoor Functions Hardcore Functions IND-CPA security from Trapdoor Functions	[Slides]
6	5/1	Chosen-Ciphertext Security Motivation & definition The Cramer-Shoup Lite Encryption Scheme	[Slides] [Annotated] [Homework 3]
	5/3	CCA Security & Random Oracles Cramer Shoup wrap up The Random Oracle Model CCA security from TDFs and random oracles	[Slides] [Annotated]
7	5/8	Digital Signatures UF-CMA security Full-Domain Hash Signatures Authenticated Key Exchange	[Slides] [Annotated]
	5/10	Lattice-Based Cryptography A brief introduction to lattices and shortest vectors The LWE assumption Regev Encryption	[Slides]
8	5/15	Fully-Homomorphic Encryption The GSW Construction PIR from FHE	[Slides]
	5/17	Multi-Party Computation I 2PC Security Definition Garbled Circuits and OT	[Slides] [Homework 4]
9	5/22	Multi-Party Computation II 2PC Wrap-up: Point and permute Secret Sharing and the GWM Protocol Beaver Triples	[Slides]
	5/24	Zero-Knowledge I Proving Knowledge of Discrete Logarithms and the Schnorr Protocol General formalism Proofs of homomorphim	[Slides]
10	5/29	Memorial Day (No class)
	5/31	Zero-Knowledge II Zero-knowledge proofs for NP Commitment Schemes The Fiat-Shamir Transform and NIZKs	[Slides] [Exam]