How to Delegate Computations: The Power of No-Signaling Proofs
summary
Gives a concrete one-round delegation protocol that lets a weak verifier check any function f computable in time t: prover runs in poly(t), verifier runs in n · polylog t (or even just reads a few points of the low-degree extension), completeness 1 and computational soundness under standard cryptographic assumptions (uses fully homomorphic encryption). Builds a multiprover protocol with polylog(t) provers, no-signaling soundness, almost-linear verifier time, then compiles it to a one-round delegation using cryptography.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:45Delegation of Computation
- 2:54OneRound Delegation
- 8:10Previous Work
- 11:59Variants
- 13:09Approach
- 17:09Suggested Protocol
- 21:05NoSignaling Strategies
- 23:58NoSignaling Conditions
- 25:37NoSignaling Assumptions
- 27:19NoSignaling Strategy
- 30:33NoSignaling Powers
- 33:21NoSignaling Proofs
- 37:28Multiple Over Interactive Proof
- 44:28Delegate Computation to Mars
- 48:28NoSignaling Proof
related talks
29mEfficiently Verifying Quantum Programs with Few T Gates
45mClassical Verification of Quantum Computational Advantage
12mOne-Way Functions Imply Secure Computation in a Quantum World
32mBeating Classical Impossibility of Position Verification
21mInteractive Proofs for Synthesizing Quantum States and Unitaries
20mDistributed Quantum Proofs for Replicated Data
40mDemocratizing quantum formal verification: the path-sum way
41mOne-Way Functions Imply Secure Computation in a Quantum World