Advanced Topics in Cryptography - Fall 2023

The course studies interactive proofs, multi-prover proofs, and probabilistically checkable proofs, then uses cryptography to build computationally sound non-interactive arguments. Topics include the Fiat–Shamir paradigm, zero-knowledge proofs, and SNARGs from LWE.

Syllabus

Lecture 1: Interactive Proofs and the Sum-Check Protocol, Part 1
Lecture 1: Interactive Proofs and the Sum-Check Protocol, Part 2
Lecture 2: Doubly Efficient Interactive Proofs, Part 1
Lecture 2: Doubly Efficient Interactive Proofs, Part 2
Lecture 3: Continuation of the GKR Protocol and Corollaries
Lecture 4: PCP via GKR and Interactive Arguments, Part 1
Lecture 4: PCP via GKR and Interactive Arguments, Part 2
Lecture 5: The Kilian-Micali Protocol, Part 1
Lecture 5: The Kilian-Micali Protocol, Part 2
Lecture 6: Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 1
Lecture 6: Fiat-Shamir Paradigm and Zero-Knowledge Proofs, Part 2
Lecture 7: Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 1
Lecture 7: Soundness of the Fiat-Shamir Paradigm in the Standard Model, Part 2
Lecture 8: Succinct Non-Interactive Arguments for Batch NP (BARGs) from LWE, Part 1
Lecture 8: Succinct Non-Interactive Arguments for Batch NP (BARGs) from LWE, Part 2
Lecture 9: BARGs Implies SNARGs and Connection to Non-Signaling PCPs, Part 1
Lecture 9: BARGs Implies SNARGs and Connection to Non-Signaling PCPs, Part 2