Delegating Computation: Interaction Proofs for Muggles
Guy Rothblum
Theory of Computation Group of the Computer Science and Artificial Intelligence Laboratory (CSAIL), MIT
Abstract: Delegating Computation: Interactive Proofs for Muggles
We consider the question of designing interactive proofs that can be used by real-world parties. Namely, the (honest) prover should be efficient and run in polynomial time, the verifier should be super-efficient and run in nearly-linear time. Such a proof system can be used for delegating computation: a server can run a computation for a client and prove the correctness of the result, where the client can verify the proof very quickly.
We construct, for many efficiently computable languages, public-coin interactive proofs where the verifier's running time is quasi-linear, the prover's running time is polynomial, and the communication is poly-logarithmic. In particular, we give such a proof system for any language in (uniform) NC. This result is in the (single prover) interactive proof model, and makes no assumptions on the computational power of the dishonest prover.
Our results allow us to make progress on other related questions, such as the length of zero-knowledge proofs for NP languages, the expressive power of public-coin interactive proofs with log-space verifiers, and constructing short efficiently verifiable
non-interactive certificates of correctness for computations without resorting to the random oracle model.
Previously, the question of efficiently proving the correctness of computations was addressed in the PCP model by BFLS and in computational settings (under assumptions) by Kilian and Micali.
Joint work with Shafi Goldwasser and Yael Kalai.