To interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristic
Talkat Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025 · 2025-05-19..05-23·
summary
Shows that zero-knowledge proofs for every NP language follow from one-way functions and that succinct arguments for NP use collision-resistant or vector commitments via a commit-and-open compiler applied to PCPs. Describes concrete tools (PCPs, vector commitments, GKR/Kilian-style compilers), recent stronger assumptions used in practice (LWE, IO, witness encryption), gaps left open—most notably SNARGs from LWE or short CRS and that Fiat–Shamir is sound in the random oracle yet can fail in the plain model.
AI-written summary · about
chapters (6)
- 0:00Workshop overview
- 1:03Cryptographic proof systems
- 26:54Classical interactive proofs
- 42:31Advancements since 1992
- 53:41Fiat-Shamir heuristic
- 1:07:02Future directions in noninteractive proofs
related talks
01h 08mTutorial on Proof Systems
01h 11mTalk by Alex Lombardi (Princeton University)
01h 13mA Zero-Knowledge PCP Theorem
57mThe Cryptographic Lens: Visions of our Past and Future
49mLattice-Based Zero Knowledge and Applications
28mZero Knowledge Proofs and Their Future Applications
33mAn Introduction to Zero Knowledge Proofs
01h 12mAn Introduction to Commitment-Based Succinct Arguments