CoChat
Cited by 484

The DOI matches its Crossref record; 40 of the 40 references it cites were found in a registry or an index.

Delegating computation: interactive proofs for muggles

Goldwasser, Shafi, Kalai, Yael Tauman, Rothblum, Guy N. · 2008 · Proceedings of the fortieth annual ACM symposium on Theory of 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". 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, 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 verifier 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 efficient, the verifier runs in time n • polylog(n) and space O(log(n)), and the communication complexity is polylog(n). Using this theorem we make progress on several questions: We show how to construct short (polylog size) computationally sound non-interactive certificates of correctness for any log-space uniform NC computation, in the public-key model. The certificates can be verified in quasi-linear time and are for a designated verifier: each certificate is tailored to the verifier's public key. This result uses a recent transformation of Kalai and Raz from public-coin interactive proofs to one-round arguments. The soundness of the certificates is based on the existence of a PIR scheme with polylog communication. Interactive proofs with public-coin, log-space, poly-time verifiers for all of P. This settles an open question regarding the expressive power of proof systems with such verifiers. Zero-knowledge interactive proofs with communication complexity that is quasi-linear in the witness, length for any NP language verifiable in NC, based on the existence of one-way functions. Probabilistically checkable arguments (a model due to Kalai and Raz) of size polynomial in the witness length (rather than the instance length) for any NP language verifiable in NC, under computational assumptions.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/1374376.1374396

Cites

40 of 40 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Research works printed but not linked: 16

  1. ET , phone SETI@home!. Science@NASA headlines , 1999 . ET, phone SETI@home!. Science@NASA headlines, 1999.
  2. 10.5555/872747.873184 · doi:10.5555/872747.873184
  3. 10.1109/SFCS.1991.185343 · DOI
  4. M. Blum . How to prove a theorem so no-one else can claim it . In Proceedings of the International Congress of Mathematicians , pages 1444 -- 1451 , 1987 . M. Blum. How to prove a theorem so no-one else can claim it. In Proceedings of the International Congress of Mathematicians, pages 1444--1451, 1987.
  5. 10.5555/1756123.1756163 · doi:10.5555/1756123.1756163
  6. 10.1145/103516.128681 · doi:10.1145/103516.128681
  7. 10.1016/0022-0000(88)90038-4 · doi:10.1016/0022-0000(88)90038-4
  8. 10.1109/SFCS.1989.63519 · doi:10.1109/sfcs.1989.63519
  9. 10.1145/1236457.1236459 · doi:10.1145/1236457.1236459 · Paper page
  10. 10.1145/950620.950623 · doi:10.1145/950620.950623
  11. 10.1145/146585.146599 · doi:10.1145/146585.146599
  12. 10.1145/146585.146601 · doi:10.1145/146585.146601
  13. 10.1145/258533.258644 · doi:10.1145/258533.258644
  14. 10.5555/1760749.1760790 · doi:10.5555/1760749.1760790
  15. 10.1109/SFCS.1988.21918 · doi:10.1109/sfcs.1988.21918
  16. 10.5555/795663.796363 · doi:10.5555/795663.796363

Cited by

See all 484

Metadata

Authors
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N.
Venue
Proceedings of the fortieth annual ACM symposium on Theory of computing
Publisher
ACM
Published
2008-05-17
Pages
113-122
OpenAlex
W2146099890
Cited by
484
References
40
FWCI
9.92
Type
conference paper
Language
en
Open access
closed

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.