Access Restriction

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

   Open content in new tab
Source: ACM Digital Library