Delegating Computation II
summary
Constructs a no-signaling MIP for deterministic time-T computations that yields a two-message delegation protocol after composing with fully homomorphic encryption. The prover’s work is roughly prover time ≈ T^2, the verifier runs in quasi-linear verifier time, and communication scales with the security parameter. Core tools are PCPs with amplified consistency checks and Merkle-tree commitments for RAM; security is statistical no-signaling (robust to tiny signaling) and computational for delegation (breaks only if hash/LWE/FHE assumptions fail).
AI-written summary · about
chapters (20)
- 0:00Start
- 12:06The Power of No-Signaling MIP [KRR14]
- 13:162-Message Delegation of Arbitrary Computations
- 14:50Our No-Signaling MIP Construction
- 15:40Our Construction
- 17:47The Verifier
- 21:40"Reading" a Point
- 22:41Classic Analysis
- 24:13No-Signaling Analysis
- 26:33Local to Global Consistency
- 34:58First Attempt
- 38:02Second Attempt
- 40:54Third Attempt
- 42:44Summary
- 47:44Delegating Memory and Computation
- 49:36Prior Work on Sub-linear Delegation Memory delegation Chung-K-Liu-Raz11
- 50:31Delegating RAM Computations [K-Paneth15]
- 52:13No-Signaling Multi-Prover Argument for RAM
- 57:06Analysis (Cont.)
- 58:35Applications of No-Signaling
