Tutorial on Proof Systems

on YouTube ↗01h 08m

" summary

Survey of recent work on making non‑interactive succinct proofs practical: shows how PCP+Kilian-style compilers and the Fiat‑Shamir heuristic are turned into SNARGs by building correlation‑intractable hash families, introduces Batch‑NP and a somewhere statistical soundness notion that hides one statistically binding index in the CRS, and explains folding/recursion to compress T instances to polylog verification. Covers iO/Sahai‑Waters routes around the Gentry‑Wichs barrier and the Waters‑Wu bilinear exception; constructions work but current CRS and cryptographic tools remain large.

AI-written summary · about

" chapters (11)

1. 0:00Welcome and logistics
2. 2:08Workshop introduction
3. 3:14Cryptographic proofs overview
4. 6:46Zero knowledge and connections
5. 10:41SNARKs and standard assumptions
6. 14:09The recipe for SNARKs
7. 23:04Batch NP and statistical soundness
8. 32:17Completeness for P
9. 39:18Interactive proofs and folding
10. 52:34Efficiency and alternative methods
11. 55:45SNARKs for NP and open problems

" related talks

• 01h 15mProofs - TheoryYael Tauman Kalai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristicAlex Lombardi · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 09mProofs - Practice 1Justin Thaler · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 12mAn Introduction to Commitment-Based Succinct ArgumentsAlessandro Chiesa · Proofs (Simons Institute)
• 52mFaster, Smaller, Weaker, DarkerBenedikt Bunz · Proofs, Consensus, and Decentralizing Society Reunion 2020
• 01h 02mIncremental proof systemsBenedikt Bunz · Proofs (Simons Institute)
• 53mA Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NPBrent Waters · Obfuscation
• 24mA Framework for Post-Quantum Succinct ArgumentsAlessandro Chiesa · Zcon1: Zero to Privacy Hero 2019