Delegating Computation: Interactive Proofs for Muggles

Guy Rothblum (MIT)

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.

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. Our results are in the original interactive proof model and are unconditional.

These results allow us to make progress on other related questions, such as improving the length of zero-knowledge proofs for NP languages, characterizing the expressive power of public-coin interactive proofs with log-space verifiers, and constructing short efficiently verifiable non-interactive certificates of correctness for computations in the public key model without resorting to the random oracle model.

Joint work with Shafi Goldwasser and Yael Kalai.

Host: Shafi Goldwasser

(The Algorithms and Complexity Seminar series talks are usually held Thursdays 4:00-5:15pm in 32-G575.)