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.
| Wk | Date | 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]
|
|