SNARGs Beyond Non-Signaling

on YouTube ↗39m

" summary

Constructs a SNARG for a subclass called monotone policy batch NP under the LWE assumption, yielding the first standard-assumption SNARG for a class not known to admit small-locality non-signaling PCPs. Technique replaces somewhere-extractable hashing with a new predicate-extractable hash (PEH) that lets the CRS extract a global predicate of the (hashed) tableau, producing an augmented quasi-argument that avoids the 2^depth error blow-up and yields succinct proofs for threshold-style policies; PEH is stated as a reusable primitive.

AI-written summary · about

" chapters (7)

1. 0:00Introduction to snarks
2. 1:52The classic blueprint
3. 6:26Challenges in scaling
4. 11:58Limitations of current methods
5. 17:23Monotone batch NP
6. 24:20A new framework proposal
7. 30:14Predicate extraction

" related talks

• 01h 08mTowards SNARGs for NP from Standard AssumptionsZhengzhong Jin · Proofs (Simons Institute)
• 01h 07mBatch Arguments for NP and SNARGs for P from LWEAbhishek Jain · Quantum and Lattices Joint Reunion Workshop
• 01h 15mProofs - TheoryYael Tauman Kalai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 53mA Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NPBrent Waters · Obfuscation
• 01h 10mBatch Arguments and Their ApplicationsOmer Paneth · Proofs (Simons Institute)
• 58mSNARGs for P/poly from SISHoeteck Wee · Proofs (Simons Institute)
• 49mSubquadratic SNARGs in the Random Oracle ModelEylon Yogev · Proofs, Consensus, and Decentralizing Society Reunion 2020
• 01h 02mSuccinct Non-interactive Arguments of ProximityDaniel Wichs · Proofs (Simons Institute)