Course Title: Cryptographic Proof Systems
Location and Time: Wednesday 1:30-4:20pm in Wallace Hall 006 (note the room change)
Course Head: Alex Lombardi (contact)
Course Description: The notion of a proof in computer science has been radically re-imagined over the last forty years, now allowing for "proof systems" that make crucial use of the following resources: (1) randomization, (2) interaction, and (3) computational hardness. We study proof systems in the cryptographic setting, focusing on two fundamental properties: "zero-knowledge," which is the ability to prove a statement without conveying any information beyond its validity, and "succinctness," which is the ability to provide extremely short and easy-to-check proofs of complicated claims.
Scribe Notes: Each student must write up scribe notes (in LaTeX) for one lecture. These notes will be posted on the course website.
Reading Project: Each student must read a paper or group of papers related to the course topic and write an exposition on the contained results. A list of papers for potential projects will be posted below (although you are more than welcome to pick papers that are not on the list).
Students may substitute the reading project with a research project -- if you are interested in doing this, please email me with a (vague or specific) topic proposal.
The following schedule is very tentative and subject-to-change.
List of topics is in progress
In Fall 2019, I taught a related course at MIT that focused on zero-knowledge proofs. Lecture notes are available on the course website.
In Fall 2023, Yael Kalai taught a seminar at MIT on succinct proof systems. Lecture notes are available here.