Delegating Computation: Interactive Proofs for Muggles, by Guy Rothblum, IAS
Abstract: 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.
Joanne Talbot Hanley
Last modified: Mon Aug 16 11:10:43 EDT 2010