Catalog

Advanced Topics in Cryptography

Electrical Engineering and Computer Science MIT CC BY-NC-SA 4.0 17 lectures

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

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

Course materials