CS 59200-STC: Special Topics in Cryptography (Fall 2024)
Course Overview
Zero-knowledge proofs are cryptographic protocols that enable a prover to convince a verifier of the truth of an NP statement without disclosing the secret witness. These protocols play a crucial role in the design of larger cryptographic systems. Since the foundational work of Goldreich, Micali, and Wigderson, which established their feasibility for all NP languages, significant efforts have been devoted towards improving their practical efficiency. The goal of this course is to study state-of-the-art techniques for designing efficient zero-knowledge proofs, understand their practical implications and trade-offs. We will also explore their applications in different domains.
This seminar-style course will include lectures, paper discussions, short quizzes, and a course project. Lectures will introduce key concepts, while paper discussions will delve into state-of-the-art techniques. Each paper will be presented by designated student(s). Additionally, students will be expected to collaborate on a group project, which may involve a literature survey or original research addressing open problems in the field.
Basic Information
-
Instructor: Aarushi Goel
Class Time: 11:30 PM - 2:20 PM, Monday
Class Location: LWSN B134
Office Hours: 11:30 AM - 12:30 PM, Friday (LWSN 2142D)
Pre-Requisites
CS 35500/55500 (or an equivalent course).
Grading Policy
10% Class Participation
10% Quizzes
40% Presentation
40% Project
Class Schedule
| Date | Topics | Papers | Presenter |
|---|---|---|---|
| Aug 19 | Introduction and Definitions | Aarushi Goel | |
| Aug 26 | Sigma Protocols and MPC-in-the-Head (Part 1) | IKOS07 | Aarushi Goel |
| Sep 9 | MPC-in-the-Head (Part 2) | KKW18, Ligero | Albert Yu |
| Sep 16 | VOLE Based ZK (Part 1) | LPZK | Xiuyu Ye |
| Sep 23 | VOLE Based ZK (Part 2) | Wolverine | Arun Yeragudipati |
| Sep 30 | Probabilistically Checkable Proofs | Killian92, Micali94 | Jimmy Hwang |
| Oct 14 | Interactive Oracle Proofs | IOPs, RRR16, Aurora | Colten Brunner |
| Oct 21 | Linear PCP based SNARKs | BCIO13, Groth16 | Jacob White |
| Oct 28 | Inner Product Arguments | Bulletproofs | Satvinder Singh |
| Nov 4 | IVCs and Folding Arguments | Nova | Justin Zhang |
| Nov 11 | ZK for RAM Programs | Dora | Aarushi Goel |
| Nov 18 | Polynomial Commitments | KZG, FRI | Aarushi Goel |
| Nov 25 | Project Presentations | ||
| Dec 2 | Project Presentations |