- Instructors: Chaya Ganesh Course credits: 3:1 Lecture time: MW 9:30 - 11am Venue: Microsoft Teams.
- TAs: Prajval Koul (prajvalkoul AT iisc DOT ac DOT in)
- Office Hours: By appointment.
- Objective:
This is a graduate level course intended to introduce interactive proof systems, succinct arguments, zero-knowledge proofs, with the goal of getting students up to speed for research in the area.
- Syllabus: (tentative)
- Interactive proofs: Class IP, Sumcheck protocol, doubly efficient proofs, Delegating computation, interactive proofs for muggles.
- Zero Knowledge: Definitions, ZK for NP, Round complexity, Non-black-box Zero-knowledge, Sequential and Parallel composition, Limitations and lower bounds, Witness indistinguishability.
- More ZK: Honest verifier zero-knowledge, Malicious verifier zero-knowledge, proof of knowledge, zero-knowledge arguments, Sigma protocols, Fiat Shamir, Groth-Sahai, MPC and zero-knowledge, MPC-in-the head.
- SNARKs (Succinct Non-interactive ARguments of Knowledge): PCP, Succinct arguments, separations, Preprocessing SNARKs with trusted setup, SNARKs from linear PCP, Polynomial commitments, universal updatable SNARK.
- Interactive Oracle Proof (IOP): Model and definitions, IP,PCP as a special case of IOP, Applications of IOP in delegation of computation, Transparent SNARKs.
- Recent developments: Confidential transactions, ZCash, Recursive composition theorem for SNARK, Proof-carrying data, Applications in succinct blockchain, Research directions.
- References:
The course does not have a required textbook. Since this is an advanced course, references for most of the material will be research papers. There will be specific references given for each lecture. The following resources would be helpful:
- Foundations of Cryptography, Oded Goldreich. [Link]
- Efficient Secure Two-Party Protocols — Techniques and Constructions, Carmit Hazay and Yehuda Lindell. [Link]
- Computational Complexity, Barak and Arora. [Link]
- Surveys by Oded Goldreich on doubly efficient proofs and PCP. [Link]
Prerequisites: Intro to Cryptography, basic algorithms, and basic complexity would be helpful.
Course Policy:
Students will present a research paper in class, and will work on a research project as part of the course. Suggestions for papers to be presented will be given. Lectures will often contain open problems for class projects.
Grading policy:
- Class participation - 20%
- Paper presentation - 40%
- Class project - 40%
Academic Integrity:
You are expected to adhere to the highest standards of academic conduct. Please review the Institute academic policy here.
Announcements:
Paper suggestions:
Lectures:
This is a list of lectures delivered in the course (for reference purposes). Actual lectures and notes are available on Teams to the course attendees.
- Lecture 0 (Feb 23): Introduction and motivation
- Lecture 1 (Mar 3): Interactive Proofs, IP contained in PSPACE
- Lecture 2 (Mar 8): Sumcheck protocol, IP for coNP
- Lecture 3 (Mar 10): IP for counting problems, public coin protocol for GNI
- Lecture 4 (Mar 15): Low degree extension, GKR protocol for bounded depth circuits
- Lecture 5 (Mar 17): Zero-knowledge, HVZK IP for GI
- Lecture 6 (Mar 22): Computational soundness, proofs of knowledge, simple sigma protocols, Maurer's unifying framework
- Lecture 7 (Mar 24): Zero-knowledge argument of knowledge for arithmetic circuit satisfiability based on sigma protocols
- Lecture 8 (Mar 29): Limitations of proofs, Succint arguments, non-falsifiable assumptions
- Lecture 9 (Mar 31): Student presentation
- Lecture 10 (April 5): Student presentation