Advisor-Verifier-Prover Games and the Hardness of Information Theoretic Cryptography
summary
Introduces a single hypothesis: prover-laconic AVP (trusted advisor gives one-time advice, verifier gets x, prover may send constant bits) requires superpolynomial complexity; from that follows superpolynomial impossibility for several information-theoretic tasks. Shows reductions: single-round PIR, generalized secret sharing, and fully decomposable randomized encodings all yield such AVPs. Gives concrete gaps: PIR upper 2^{√n} vs trivial n lower bound, secret sharing upper ~1.5^n vs n/ log n lower bound, decomposable RE upper 2^{n/2} vs n/ log n lower bound. Uses the multilinear extension trick and counting arguments.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 1:40Algorithmica
- 3:45Private Information
- 7:58SQL Sharing
- 10:23Goblin Schemes
- 16:33Model Comparison
- 24:23Interactive Proof
- 27:24Poly and Communication
- 34:40Conclusion
related talks
57mThe Cryptographic Lens: Visions of our Past and Future
01h 08mIncrementally Verifiable Computation for NP from Standard Assumptions
01h 13mA Zero-Knowledge PCP Theorem
01h 09mCrypto + ML 1
01h 09mProofs - Practice 1
33mGeometry of Secure Computation
01h 02mIncremental proof systems
01h 15mTo interact or not to interact: Cryptographic proof systems and the Fiat-Shamir heuristic