Towards SNARGs for NP from Standard Assumptions

on YouTube ↗01h 08m

" summary

Constructs a SNARG that, under LWE, handles any NP instance whose non‑membership has a polynomial‑size Extended Frege (propositional) proof: uses FHE of the relation, Merkle hashes plus a batch‑ARG to certify taped gate evaluations, and a puncturing/hybrid argument over a polynomial sequence of circuits derived from the EF proof to get SNARGs from LWE for NP with propositional non‑membership proofs. Soundness is non‑adaptive, CRS is uniform but grows with the proof, and the scheme reduces to witness encryption or dv‑SNARGs to extend security to all NP (does not achieve adaptive soundness or avoid large CRS).

AI-written summary · about

" chapters (7)

1. 0:00SNARGs without random oracles
2. 1:34SNARGs and standard assumptions
3. 7:04SNARGs for NP non-membership
4. 17:51SNARGs from witness encryption
5. 37:45Construction overview
6. 48:52Overcoming Gentry-Wichs impossibility
7. 1:02:51Summary and open problems

" related talks

• 01h 15mProofs - TheoryYael Tauman Kalai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 39mSNARGs Beyond Non-SignalingYael Tauman Kalai · Minimal Complexity Assumptions for Cryptography 2023
• 53mA Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NPBrent Waters · Obfuscation
• 01h 07mBatch Arguments for NP and SNARGs for P from LWEAbhishek Jain · Quantum and Lattices Joint Reunion Workshop
• 45mNon-interactive Universal ArgumentsDana Shamir · Minimal Complexity Assumptions for Cryptography 2023
• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023
• 44mCorrelation Intractability and SNARGs from Sub-exponential DDHZhengzhong Jin · Minimal Complexity Assumptions for Cryptography 2023
• 26mPCPs and Instance Compression from a Cryptographic LensLiron Bronfman, Ron D. Rothblum · ITCS 2022