Delegating Computation I

on YouTube ↗59m

" summary

Constructs a practical path from multiprover proofs to a single-cloud protocol: a two-message delegation scheme for RAM-style computations whose verifier time does not depend on huge outsourced data and whose prover runs near the RAM runtime, proved under the LWE assumption. Key technical fix is replacing the naive FHE-encrypted two-query trick with MIPs resilient to no-signaling strategies, avoiding the Duco et al. attack and yielding quasi-linear verifier time and near-linear prover overhead.

AI-written summary · about

" chapters (11)

1. 0:00Introduction and welcome
2. 0:30Delegating computation
3. 2:55Defining the delegation goal
4. 7:00Memory delegation settings
5. 10:24Two-message RAM delegation
6. 12:53History of delegation schemes
7. 19:34Landscape of delegation work
8. 27:27Pre-processing and snarks
9. 36:14Multi-prover interactive proofs
10. 42:31Converting MIP to one prover
11. 48:20No-signaling strategies

" related talks

• 01h 09mProofs - Practice 1Justin Thaler · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 00mSecure Computation 3Peter Scholl · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 08mSecure Computation 1Peter Scholl · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 59mDoubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWEDaniel Wichs · Minimal Complexity Assumptions for Cryptography 2023
• 01h 07mProofs - Practice 2Justin Thaler · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 23mProgram PresentationsSanjam Garg, Jim Demmel, Umesh Vazirani, Kirk Pruhs, Nati Srebro, JM Landsberg · Eleventh Annual Industry Day
• 57mThe Cryptographic Lens: Visions of our Past and FutureShafi Goldwasser · Symposium on Visions of the Theory of Computing 2013
• 01h 08mTutorial on Proof SystemsAbhishek Jain · Minimal Complexity Assumptions for Cryptography 2023