Batch Proofs are Statistically Hiding

on YouTube ↗45m

" summary

Shows that any statistically-sound batch proof for a language L (communication < t^{1−ε}) yields Statistically Witness Indistinguishable (SWI) proofs for L with inverse-polynomial soundness and SWI error and a non-uniform honest prover, by transforming batch protocols into SWI ones using a shrinking-function compression lemma plus min–max sampling. For computational soundness, batch arguments for NP plus one-way functions give interactive SZK arguments with similar rounds and inverse-polynomial error; non-interactive BARGs with somewhere-extractability amplify via lossy PKE to NISZKA with negligible errors.

AI-written summary · about

" chapters (9)

1. 0:00Introduction to batch proofs
2. 3:50Statistical witness hiding
3. 7:36Complexity and implications
4. 12:36Batch arguments for NP
5. 16:53Constructions and assumptions
6. 20:52Distributional witness hiding
7. 24:15Compression techniques
8. 33:58Scaling and generalizing
9. 39:43Open questions and outlook

" related talks

• 01h 07mBatch Arguments for NP and SNARGs for P from LWEAbhishek Jain · Quantum and Lattices Joint Reunion Workshop
• 01h 09mProofs - Practice 1Justin Thaler · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 06mLattice-based Zero-knowledge ProofsVadim Lyubashevsky · Quantum and Lattices Joint Reunion Workshop
• 01h 10mBatch Arguments and Their ApplicationsOmer Paneth · Proofs (Simons Institute)
• 01h 13mA Zero-Knowledge PCP TheoremNicholas Spooner · Proofs (Simons Institute)
• 01h 01mLocal Proofs Approaching the Witness LengthRon D. Rothblum · Proofs, Consensus, and Decentralizing Society Reunion 2020
• 28mSample-based Proofs of ProximityGuy Goldberg, Guy N. Rothblum · ITCS 2022
• 56mCollaborative zk-SNARKs: Proving as One over Distributed SecretsAarushi Goel · Proofs (Simons Institute)