Batch Arguments and Their Applications

on YouTube ↗01h 10m

" summary

Defines batch arguments (BARGs) as short proofs that jointly certify k NP statements with succinctness that grows with one instance but not k, and shows how hashing a machine tableau and proving local transitions via BARGs yields SNARGs for P. Security relies on somewhere soundness / somewhere extraction and an index-programmed CRS trick using two independent CRSs to enable extraction without breaking indistinguishability. Also covers per-configuration hashing for large-space RAM and quasi-arguments for CSPs (L-local extractors), plus open problems about replacing SNARGs, succinct malicious MPC, recursion, and simpler constructions.

AI-written summary · about

" chapters (13)

1. 0:00Batch Arguments intro
2. 1:09SNARGs and limitations
3. 5:12Batch Arguments middle ground
4. 9:30BARGs from assumptions
5. 15:01BARG syntax and properties
6. 20:11SNARGs for P using BARGs
7. 29:47BARG soundness and extraction
8. 40:52SNARG security analysis
9. 45:29Final protocol with two BARGs
10. 52:12Handling large configs with hashing
11. 57:39Hash-and-BARG technique
12. 1:00:06Quasi-arguments for CSP
13. 1:05:24Open questions

" related talks

• 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
• 39mSNARGs Beyond Non-SignalingYael Tauman Kalai · Minimal Complexity Assumptions for Cryptography 2023
• 46mRate-1 BARGs via fully-local SSB hash familiesLalita Devadas · Minimal Complexity Assumptions for Cryptography 2023
• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023
• 45mBatch Proofs are Statistically HidingPrashant Vadusevan · Minimal Complexity Assumptions for Cryptography 2023
• 44mCorrelation Intractability and SNARGs from Sub-exponential DDHZhengzhong Jin · Minimal Complexity Assumptions for Cryptography 2023
• 45mNon-interactive Universal ArgumentsDana Shamir · Minimal Complexity Assumptions for Cryptography 2023