Sunday, 23.12.2007, 10:30
Suppose you are a user with a weak computational device connected to a
network, e.g. a cell phone, and you need to perform a computation beyond
your abilities. A natural solution is for you to *delegate* the
expensive computation to a stronger computational device on the same
network, say a server. The problem is that you may not trust the answer
of this server: it may be unreliable or malicious. Can the server give
you the output of the computation and *prove* to you that the output is
The main challenge we consider in this work is:
"How can you verify that a computation was run correctly, using less
resources than it would take to run the computation, and without the
server having to work too hard?"
We address this problem in the /Interactive Proof setting/. We
construct, for many efficiently computable languages, public-coin
interactive proofs where the verifier's (or user's) running time is
quasi-linear, the prover's (or server's) running time is polynomial, and
the communication is poly-logarithmic. More specifically, we give such a
proof system for any language in (uniform) NC.
Previously, the question of verifying the correctness of computations
was addressed in the PCP model by Babai, Fortnow, Levin and Szegedi, in
the argument model under computational assumptions by Kilian, and in the
random oracle model by Micali. Our 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.
Joint work with Shafi Goldwasser and Yael Kalai