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. Notes and reading material will be posted here. The following is a list of great resources to reference to (most of these are available for free):


Grading

(This is subject to minor changes, as we adapt to the challenges of online teaching.) There will be four homework assignments, and one take-home final exam. Each student is responsible for scribing the note for one class, which will be posted online. Each homework accounts for 15% of points, the final accounts for 30% of points. Participation is 10%. Your final grade will be based on the weighted total points.


Schedule

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

WkDate Lecture contents Assignments / Reading
1 03/30 Introduction
  • Welcome / organizational details
  • What is cryptography?
  • Example applications
  • The provable security paradigm
[Slides Lecture 1]
04/01 Symmetric encryption: Perfect-secrecy, information-theoretic vs computational security
  • Syntax of symmetric encryption
  • Shannon secrecy and perfect secrecy
  • One-time pad and key-lengt lower bound for perfect secrecy
[Slides Lecture 2] [Scribed Notes]
2 04/06 Pseudorandom Generators I
  • Definition of PRGs
  • Asymptotic vs Concrete Security
[Slides Lecture 3] [Scribed Notes]
04/08 Pseudorandom Generators II
  • Refresher: Group theory and number theory
  • The Discrete Logarithm Problem
  • Blum-Micali PRG
[Slides Lecture 4] [Scribed Notes]
3 04/13 Pseudorandom Generators III
  • Hybrid arguments
  • Blum-Micali PRG - security proof
[Slides Lecture 5] [Scribed Notes]
04/15 Pseudorandom Functions I
  • One-way functions and PRGs
  • PRG expansion
  • PRF definition and the GGM construction
[Slides Lecture 6] [Scribed Notes]
4 04/20 Symmetric Encryption
  • Block ciphers
  • PRP security
  • The Switching Lemma
[Slides Lecture 7] [Scribed Notes]
04/22 Symmetric Encryption
  • Definition of IND-CPA security
  • Randomized counter-mode encryption
  • Proof of IND-CPA security for counter-mode
[Slides Lecture 8] [Scribed Notes]
5 04/27 Message Authentication & Authenticated Encryption
  • Padding Oracle Attacks
  • Message-authentication codes / UF-CMA security
  • PRFs and MACs
[Slides Lecture 9] [Scribed Notes]
04/29 Authenticated Encryption
  • Universal Hashing
  • MAC construction
  • INT-CTXT
  • Encrypt-then-MAC
[Slides Lecture 10] [Scribed Notes]
6 05/04 Public-key encryption I
  • Diffie-Hellman Key Exchange
  • The DDH assumption
  • ElGamal Encryption
[Slides Lecture 11] [Scribed Notes]
05/06 Public-key Encryption II
  • Trapdoor Functions
  • The RSA Trapdoor Function
  • Encryption from Trapdoor Functions
  • Definition of CCA security
[Slides Lecture 12] [Scribed Notes]
7 05/11 CCA-Secure Encryption
  • Trapdoor-function based CCA-secure encryption
  • The random oracle model
[Slides Lecture 13] [Scribed Notes]
05/13 Digital Signatures
  • Definition and UF-CMA security
  • The Full-Domain Hash (FDH)
  • Security of FDH in the random-oracle model
  • Introduction to Authenticated Key-Exchange
[Slides Lecture 14] [Scribed Notes]
8 05/18 Lattice-based cryptography I
  • Certificates via Digital Signatures
  • Introduction to LWE
  • Regev's scheme
[Slides Lecture 15]
05/20 Lattice-based cryptography II
  • Fully-homomorphic encrytpion
  • The GSW construction
  • Noise management and bootstrapping
[Slides Lecture 16]
9 05/25 No Class: Memorial Day!
05/27 Zero-knowledge Proofs
  • Definition of Interactive Proofs and Zero-Knowledge
  • The GMR protocol for 3-coloring
  • Schnorr Proof of Knowledge for Discrete Logarithm
[Slides Lecture 17] [Scribed Notes]
10 06/01 Multi-Party Computation I
  • Proof-of-knolwedge for Discrete Logarithm HVZK
  • The Fiat-Shamir Transform
  • Definition of two-party computation
  • Oblivious Transfer
  • A protocol for AND
[Slides Lecture 18] [Scribed Notes]
06/03 Multi-Party Computation II
  • Yao's Protocol
  • Introduction to Multi-Party Computation
[Scribed Notes]