@InProceedings{goldwasser2008delegating,
author = {Goldwasser, Shafi and Kalai, Yael Tauman and Rothblum, Guy},
title = {Delegating computation: interactive proofs for muggles},
booktitle = {STOC},
year = {2008},
month = {January},
abstract = {In this work we study interactive proofs for tractable languages. The (honest) prover should be eﬃcient and run in polynomial time, or in other words a “muggle”.1 The veriﬁer should be super-eﬃcient and run in nearly-linear time. These proof systems can be used for delegating computation: a server can run a computation for a client and interactively prove the correctness of the result. The client can verify the result’s correctness in nearly-linear time (instead of running the entire computation itself). Previously, related questions were considered in the Holographic Proof setting by Babai, Fortnow, Levin and Szegedy, in the argument setting under computational assumptions by Kilian, and in the random oracle model by Micali. Our focus, however, is on the original interactive proof model where no assumptions are made on the computational power or adaptiveness of dishonest provers. Our main technical theorem gives a public coin interactive proof for any language computable by a log-space uniform boolean circuit with depth d and input length n. The veriﬁer runs in time (n+d)·polylog(n) and space O(log(n)), the communication complexity is d·polylog(n), and the prover runs in time poly(n). In particular, for languages computable by log-space uniform NC (circuits of polylog(n) depth), the prover is eﬃcient, the veriﬁer runs in time n · polylog(n) and space O(log(n)), and the communication complexity is polylog(n).},
url = {https://www.microsoft.com/en-us/research/publication/delegating-computation-interactive-proofs-for-muggles/},
pages = {113-122},
edition = {STOC},
}