Sample-based Proofs of Proximity

on YouTube ↗28m

" summary

Shows how query-based interactive proofs of proximity convert to sample-based ones with only Q samples and about Q + C communication, using k‑wise independent permutations (implemented via k‑wise hash functions) and a permutation-sampling trick; equality gets a one‑round sample‑based IPP with 1/epsilon samples and log n communication versus the sample-only tester’s √n requirement. Proves noninteractive proofs of sublinear length force ≥√n samples for equality, and public-coin sample verifiers with S < √n must satisfy S·C ≥ n.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 0:19Warm-up Equality Testing
3. 4:00Interactive Proof of Proximity (IPP)
4. 6:47Sample-Based IPP for Equality Testing
5. 11:13Applications of the Reduction
6. 12:20Lower Bounds for Equality Testing
7. 14:32Proof Sketch of Main Result Theorem: Query-Based IPP = Sample-Based IPP
8. 17:21The Reduction Protocol
9. 20:32Issues with the protocol
10. 25:15Conclusions
11. 26:26Open Questions

" related talks

• 01h 09mProofs - Practice 1Justin Thaler · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 45mBatch Proofs are Statistically HidingPrashant Vadusevan · Minimal Complexity Assumptions for Cryptography 2023
• 57mThe Cryptographic Lens: Visions of our Past and FutureShafi Goldwasser · Symposium on Visions of the Theory of Computing 2013
• 01h 06mLattice-based Zero-knowledge ProofsVadim Lyubashevsky · Quantum and Lattices Joint Reunion Workshop
• 01h 01mLocal Proofs Approaching the Witness LengthRon D. Rothblum · Proofs, Consensus, and Decentralizing Society Reunion 2020
• 01h 02mSuccinct Non-interactive Arguments of ProximityDaniel Wichs · Proofs (Simons Institute)
• 33mDistributed Interactive ProofsRotem Oshman · Interactive Complexity 2018
• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023