Advanced Topics in Cryptography - Fall 2023

Explore the evolution of proofs in computer science through this advanced graduate-level course that delves into interactive proofs, multi-prover interactive proofs, and probabilistically checkable proofs. Master the Sum-Check Protocol and understand how interactive proof systems work in practice. Examine doubly efficient interactive proofs and learn about the GKR protocol along with its applications and corollaries. Discover how to construct probabilistically checkable proofs (PCPs) using GKR and understand the transition to interactive arguments. Study the Kilian-Micali protocol and its significance in cryptographic proof systems. Investigate the Fiat-Shamir paradigm for converting interactive proofs into non-interactive ones, and explore zero-knowledge proofs and their properties. Analyze the soundness of the Fiat-Shamir paradigm in the standard model and understand its theoretical foundations. Learn about Succinct Non-Interactive Arguments for Batch NP (BARGs) constructed from Learning With Errors (LWE) assumptions. Understand how BARGs can be used to construct SNARGs (Succinct Non-Interactive Arguments) and explore their connection to non-signaling PCPs. Gain deep insights into how cryptographic techniques can transform powerful interactive proof systems into computationally sound non-interactive arguments, bridging theoretical computer science and practical cryptographic applications.

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