Succinct Non-interactive Arguments of Proximity

on YouTube ↗01h 02m

" summary

Constructs succinct noninteractive arguments of proximity (SNAPs) with tight parameters: adaptive SNAPs for P achieve O(n^{1/2}) proof length, verifier query complexity, and verification time under lattice assumptions (e.g., LWE), and extend to NP using indistinguishability obfuscation (joint work with Liyan Chen and Zhengzhong Jin, STOC 2025); an unconditional lower bound shows Ω(n^{1/2}) is necessary for adaptive security; nonadaptive SNAPs for NP are fully succinct (poly(λ)) from LWE+iO, and a reduction shows nonadaptive SNAPs for P with better parameters would imply SNARGs for NP. Central primitive is a new commitment of proximity that enables sublinear-time verification and is instantiated and proven to work.

AI-written summary · about

" chapters (21)

1. 0:00SNAPs introduction and motivation
2. 1:26Why SNARGs fail for huge objects
3. 3:54Succinct non-interactive proximity
4. 6:43Approximate soundness in SNAPs
5. 8:13Prior work and open questions
6. 10:45SNAPs results after 10 years
7. 11:25Lower bound for adaptive SNAPs for P
8. 12:26Adaptive SNAPs for NP from P
9. 13:35Nonadaptive SNAPs for NP efficiently
10. 14:40Negative result for nonadaptive SNAPs for P
11. 15:46Summary of results and problems
12. 16:08Key difficulty in adaptive SNAPs
13. 20:23Commitment of proximity as primitive
14. 25:42Simple commitment of proximity
15. 31:07From commitment to SNAPs
16. 33:12Extractable commitment of proximity
17. 40:43Syndrome decoding for commitments
18. 46:23Somewhere extractable hash functions
19. 50:45Lower bound proof for SNAPs
20. 57:17Future directions and applications
21. 59:44Q&A

" related talks

• 53mA Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for NPBrent Waters · Obfuscation
• 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
• 26mPCPs and Instance Compression from a Cryptographic LensLiron Bronfman, Ron D. Rothblum · ITCS 2022
• 39mSNARGs Beyond Non-SignalingYael Tauman Kalai · Minimal Complexity Assumptions for Cryptography 2023
• 01h 07mBatch Arguments for NP and SNARGs for P from LWEAbhishek Jain · Quantum and Lattices Joint Reunion Workshop
• 18mA Selection of Pairing Based zk-SNARKsMary Maller · Zcon1: Zero to Privacy Hero 2019
• 45mNon-interactive Universal ArgumentsDana Shamir · Minimal Complexity Assumptions for Cryptography 2023