Batch Arguments for NP and SNARGs for P from LWE

on YouTube ↗01h 07m

" summary

Claims a construction of SNARKs for P and for Batch NP using LWE by combining LWE-based correlation-intractable hash functions with SSV commitments that support local openings and a no‑signaling extraction property. The plan: make a dual‑mode interactive batch argument (CRS can be programmed at an index), compress via Fiat–Shamir plus CIH to a NIZK, and transform Batch NP → P by committing Turing‑machine states; asymptotic costs are polylog(T) verification and poly(log T) proof size, with adaptive soundness caveats and reliance on LWE for the CIH.

AI-written summary · about

" chapters (9)

1. 0:00Introduction to SNARKs
2. 3:27Defining the problem space
3. 8:08Theoretical foundations
4. 14:08The role of hash functions
5. 21:30Challenges in construction
6. 27:45Dual mode batch arguments
7. 37:31Transformation methods
8. 45:48Construction of SNARKs
9. 55:38Future directions

" related talks

• 01h 10mBatch Arguments and Their ApplicationsOmer Paneth · Proofs (Simons Institute)
• 01h 08mTowards SNARGs for NP from Standard AssumptionsZhengzhong Jin · Proofs (Simons Institute)
• 45mBatch Proofs are Statistically HidingPrashant Vadusevan · Minimal Complexity Assumptions for Cryptography 2023
• 39mSNARGs Beyond Non-SignalingYael Tauman Kalai · Minimal Complexity Assumptions for Cryptography 2023
• 44mCorrelation Intractability and SNARGs from Sub-exponential DDHZhengzhong Jin · Minimal Complexity Assumptions for Cryptography 2023
• 01h 15mProofs - TheoryYael Tauman Kalai · 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)
• 58mSNARGs for P/poly from SISHoeteck Wee · Proofs (Simons Institute)