SNARGs for P/poly from SIS

on YouTube ↗58m

" summary

New lattice construction gives SNARGs for P/poly from SIS (no random oracles) by building functional commitments that compress GSW-style encryptions into a small CRS and then open to f(x) via low-norm SIS preimages. Concrete guarantees: constant-sized transparent CRS, constant-sized commitments, O(d)-sized openings and proofs (d = circuit depth), online verification after circuit-dependent preprocessing runs in time linear in |x|, and proofs are computationally unique; security reduces to standard SIS via an algebraic relaxation and Merkle-style recursion.

AI-written summary · about

" chapters (11)

1. 0:00SNARGs for P/poly intro
2. 1:23SNARGs for deterministic computation
3. 8:23Functional commitments core
4. 15:49SIS assumption variants
5. 20:03Warm-up functional commitments
6. 31:09Relaxing SIS verification
7. 36:30Homomorphic multiplication with relaxations
8. 41:39Chainable commitments for circuits
9. 47:19Merkle recursion for openings
10. 51:57Summary of results
11. 53:47Related works and future

" related talks

• 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 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023
• 39mSNARGs Beyond Non-SignalingYael Tauman Kalai · Minimal Complexity Assumptions for Cryptography 2023
• 45mNon-interactive Universal ArgumentsDana Shamir · Minimal Complexity Assumptions for Cryptography 2023
• 01h 32mThe Short Integer Solutions Problem and Cryptographic ApplicationsDaniele Micciancio · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 07mBatch Arguments for NP and SNARGs for P from LWEAbhishek Jain · Quantum and Lattices Joint Reunion Workshop
• 37mPPP-completeness with connections to CryptographyAikaterini Sotiraki​​​​ · Lattices: Geometry, Algorithms and Hardness 2020