The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.
Delegating Computation: Interactive Proofs for Muggles
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 d and input length n . The verifier runs in time n · poly( d , log( n )) and space O (log( n )), the communication complexity is poly( d , log( 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 1-round computationally sound arguments with polylog communication for any log-space uniform NC computation. The verifier runs in quasi-linear time. This result uses a recent transformation of Kalai and Raz from public coin interactive proofs to 1-round 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 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 witness length for any NP language verifiable in 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 NP language verifiable in NC , under computational assumptions, are provided.
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.
Integrity signals
Registry
Cites
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.
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
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806
Bitansky, N., Canetti, R., Chiesa, A., & Tromer, E. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090263 · Cited by 493
Cited by
Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS
Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., & Ward, N. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-45721-1_26 · Cited by 358
Aurora: Transparent Succinct Arguments for R1CS
Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., & Ward, N. P. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-17653-2_4 · Cited by 330
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup
Ames, S., Hazay, C., Ishai, Y., & Venkitasubramaniam, M. (2017) · Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3133956.3134104 · Cited by 305
Doubly-Efficient zkSNARKs Without Trusted Setup
Wahby, R. S., Tzialla, I., Shelat, A., Thaler, J., & Walfish, M. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00060 · Cited by 276
Planting Undetectable Backdoors in Machine Learning Models : [Extended Abstract]
Goldwasser, S., Kim, M. P., Vaikuntanathan, V., & Zamir, O. (2022) · 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) · doi:10.1109/focs54457.2022.00092 · Cited by 41
Self-citationAZR: Risk-Adaptive Verification for Decentralized AI Inference on Blockchain Rollups
Virani, A. (2026) · Zenodo · doi:10.5281/zenodo.20703363
Models That Prove Their Own Correctness
Amit, N., Goldwasser, S., Paradise, O., & Rothblum, G. (2024) · arXiv · doi:10.48550/arxiv.2405.15722
Self-citation
Metadata
- Authors
- Goldwasser, S., Kalai, Y. T., & Rothblum, G. N.
- Venue
- Journal of the ACM
- Published
- 2015-09-11
- Volume
- 62
- Issue
- 4
- Pages
- 1-64
- ISSN
- 0004-5411 (ISSN-L)
- 1557-735X
- OpenAlex
- W2071520502
- Cited by
- 216
- References
- 2
- FWCI
- 6.88
- Type
- journal article
- 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.