### Delegating Computation: Interactive Proofs for MugglesDelegating Computation: Interactive Proofs for Muggles

Access Restriction
Subscribed

 Author Goldwasser, Shafi ♦ Kalai, Yael Tauman ♦ Rothblum, Guy N Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Delegating computation ♦ Interactive proofs ♦ Verifiable computing Abstract In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time or, in other words, a “muggle”.1 The verifier should be super-efficient 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 et al. [1991b] in the argument setting under computational assumptions by Kilian, and in the random oracle model by Micali [1994]. 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 $\textit{d}$ and input length $\textit{n}.$ The verifier runs in time n · $poly(\textit{d},$ $log(\textit{n}))$ and space $\textit{O}(log(\textit{n})),$ the communication complexity is $poly(\textit{d},$ $log(\textit{n})),$ and the prover runs in time $poly(\textit{n}).$ In particular, for languages computable by log-space uniform $\textit{NC}$ (circuits of $polylog(\textit{n})$ depth), the prover is efficient, the verifier runs in time $\textit{n}$ · $polylog(\textit{n})$ and space $\textit{O}(log(\textit{n})),$ and the communication complexity is $polylog(\textit{n}).$ Using this theorem we make progress on several questions. --- We show how to construct 1-round computationally sound arguments with polylog communication for any log-space uniform $\textit{NC}$ computation. The verifier runs in quasi-linear time. This result uses a recent transformation of Kalai and Raz from public coin interactive $\textit{proofs}$ to 1-round $\textit{arguments}.$ The soundness of the argument system is based on the existence of a PIR scheme with polylog communication. --- We construct interactive proofs with public coin, log-space, poly-time verifiers for all of $\textit{P}$ are given. This settles an open question regarding the expressive power of proof systems with such verifiers. --- We construct zero-knowledge interactive proofs are given with communication complexity quasi-linear in the $\textit{witness}$ length for any $\textit{NP}$ language verifiable in $\textit{NC},$ based on the existence of 1-way functions. --- We construct probabilistically checkable arguments (a model due to Kalai and Raz) of size polynomial in the witness length (rather than instance length) for any $\textit{NP}$ language verifiable in $\textit{NC},$ under computational assumptions, are provided. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-09-11 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 62 Issue Number 4 Page Count 64 Starting Page 1 Ending Page 64

#### Open content in new tab

Source: ACM Digital Library