Proofs - Theory
Talkat Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025 · 2025-05-19..05-23·
summary
Survey of concrete SNARG progress and remaining barriers: shows an iO-based construction that achieves SNARGs for NP but relies on iO with subexponential reductions and long structured CRS; describes an MIP+FHE route that yields designated-verifier succinct proofs but fails to handle general NP due to local assignment generator barriers; presents a new encrypt hash-&-BARG idea that combines somewhere-extractable hashing, BARGs and encrypted extensions to break some barriers (e.g., DDH) yet stops short of a full NP-from-polynomial LWE result.
AI-written summary · about
chapters (15)
- 0:00Introduction and logistics
- 0:26Succinct non-interactive arguments
- 2:38The quest for standard assumptions
- 3:24SNARGs from indistinguishability obfuscation
- 6:10Addressing impossibility barriers
- 10:06The three pillars of SNARG research
- 12:08Multi-prover interactive proofs with FHE
- 16:42Locally computable extensions
- 23:20Designated verifier SNARG construction
- 30:38Local assignment generator analysis
- 35:18Soundness for deterministic languages
- 40:31Limitations for NP languages
- 49:26The hash-and-BARG approach
- 57:21Summary of current limitations
- 1:03:36Encrypted hash-and-BARG and future outlook
related talks
01h 08mTutorial on Proof Systems
01h 08mTowards SNARGs for NP from Standard Assumptions
53mA Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP
58mSNARGs for P/poly from SIS
39mSNARGs Beyond Non-Signaling
44mCorrelation Intractability and SNARGs from Sub-exponential DDH
01h 10mBatch Arguments and Their Applications
45mNon-interactive Universal Arguments