A Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NP

on YouTube ↗53m

" summary

Constructs an adaptively-sound SNARG for NP in the CRS model from sub-exponential iO plus only sub-exponential one-way functions, removing the prior need for discrete-log / factoring / LWE. The construction actually builds obfuscated proof and verifier programs using puncturable PRFs, embeds a single one-way-function challenge everywhere via complexity leveraging (two-to-the-n hybrids and a longer CRS), and reduces any successful forgery to finding a preimage of an (effectively) injective one-way function, so the scheme works under the stated assumptions.

AI-written summary · about

" chapters (10)

1. 0:00SNARGs from iO
2. 2:50Non-adaptive vs adaptive security
3. 8:102014 SNARG limits
4. 13:31Subexponential hardness need
5. 21:33Adaptive SNARG overview
6. 23:40Off-path forgeries
7. 30:23One-way function challenges
8. 37:56Pure iO approach
9. 41:57Other SNARG works
10. 43:48Q&A

" related talks

• 01h 08mTowards SNARGs for NP from Standard AssumptionsZhengzhong Jin · Proofs (Simons Institute)
• 01h 15mProofs - TheoryYael Tauman Kalai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023
• 39mSNARGs Beyond Non-SignalingYael Tauman Kalai · Minimal Complexity Assumptions for Cryptography 2023
• 58mSNARGs for P/poly from SISHoeteck Wee · Proofs (Simons Institute)
• 45mNon-interactive Universal ArgumentsDana Shamir · Minimal Complexity Assumptions for Cryptography 2023
• 01h 02mSuccinct Non-interactive Arguments of ProximityDaniel Wichs · Proofs (Simons Institute)
• 01h 12mApplications of Obfuscation ICraig Gentry · Cryptography Boot Camp 2015