Advanced Topics in Cryptography

This course is about the evolution of proofs in computer science. We will learn about the power of interactive proofs, multi-prover interactive proofs, and probabilistically checkable proofs. We will then show how to use cryptography to convert these powerful proof systems into computationally sound non-interactive arguments (SNARGs).

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