The Taub Faculty of Computer Science Events and Talks

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 correct? 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