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.)


There is no mandatory textbook. Reading materials will be posted throughout the class. Hower, the following are good references: A good overview on secure multi-party computation is available in this free textbook


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%)


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.

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