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
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.
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
How To Prove Yourself: Practical Solutions to Identification and Signature Problems
Fiat, A., & Shamir, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_12 · Cited by 3,943
The knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
Self-citationProceedings of the International Congress of Mathematicians: August 3–11, 1994 Zürich, Switzerland
(1995) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-9078-6 · Cited by 2,042
BOINC: A System for Public-Resource Computing and Storage
Anderson, D. P. (2005) · Fifth IEEE/ACM International Workshop on Grid Computing · doi:10.1109/grid.2004.14 · Cited by 1,924
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
Goldreich, O., Micali, S., & Wigderson, A. (1991) · Journal of the ACM · doi:10.1145/116825.116852 · Cited by 1,349
Probabilistic checking of proofs: a new characterization of NP
Arora, S., & Safra, S. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,153
The random oracle methodology, revisited
Canetti, R., Goldreich, O., & Halevi, S. (2004) · Journal of the ACM · doi:10.1145/1008731.1008734 · Cited by 978
Replication is not needed: single database, computationally-private information retrieval
Kushilevitz, E., & Ostrovsky, R. (2002) · Proceedings 38th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1997.646125 · Cited by 932
Agrawal, M., Kayal, N., & Saxena, N. (2004) · Annals of Mathematics · doi:10.4007/annals.2004.160.781 · Cited by 931
Research works printed but not linked: 16
- ET , phone SETI@home!. Science@NASA headlines , 1999 . ET, phone SETI@home!. Science@NASA headlines, 1999.
- 10.5555/872747.873184 · doi:10.5555/872747.873184
- 10.1109/SFCS.1991.185343 · DOI
- 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.
- 10.5555/1756123.1756163 · doi:10.5555/1756123.1756163
- 10.1145/103516.128681 · doi:10.1145/103516.128681
- 10.1016/0022-0000(88)90038-4 · doi:10.1016/0022-0000(88)90038-4
- 10.1109/SFCS.1989.63519 · doi:10.1109/sfcs.1989.63519
- 10.1145/1236457.1236459 · doi:10.1145/1236457.1236459 · Paper page
- 10.1145/950620.950623 · doi:10.1145/950620.950623
- 10.1145/146585.146599 · doi:10.1145/146585.146599
- 10.1145/146585.146601 · doi:10.1145/146585.146601
- 10.1145/258533.258644 · doi:10.1145/258533.258644
- 10.5555/1760749.1760790 · doi:10.5555/1760749.1760790
- 10.1109/SFCS.1988.21918 · doi:10.1109/sfcs.1988.21918
- 10.5555/795663.796363 · doi:10.5555/795663.796363
Cited by
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
“[40] and has been studied under various terms in the literature: checking computations [40], certified computation [295], delegating computations [185], as well as verifiable computing [173].”
BackgroundNon-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
Gennaro, R., Gentry, C., & Parno, B. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_25 · Cited by 1,145
Bulletproofs: Short Proofs for Confidential Transactions and More
Bunz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., & Maxwell, G. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00020 · Cited by 1,154
On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption
López-Alt, A., Tromer, E., & Vaikuntanathan, V. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2214086 · Cited by 910
Pinocchio: Nearly Practical Verifiable Computation
Parno, B., Howell, J., Gentry, C., & Raykova, M. (2013) · 2013 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2013.47 · Cited by 864
Quadratic Span Programs and Succinct NIZKs without PCPs
Gennaro, R., Gentry, C., Parno, B., & Raykova, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-38348-9_37 · Cited by 724
Universal Blind Quantum Computation
Broadbent, A., Fitzsimons, J., & Kashefi, E. (2009) · 2009 50th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.36 · Cited by 521
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
Secure attribute-based data sharing for resource-limited users in cloud computing
Li, J., Zhang, Y., Chen, X., & Xiang, Y. (2018) · Computers & Security · doi:10.1016/j.cose.2017.08.007 · Cited by 461
Securely Outsourcing Attribute-Based Encryption with Checkability
Li, J., Huang, X., Li, J., Chen, X., & Xiang, Y. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2013.271 · Cited by 429
Zero-knowledge from secure multiparty computation
Ishai, Y., Kushilevitz, E., Ostrovsky, R., & Sahai, A. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250794 · Cited by 412
Attribute-based encryption for circuits
Gorbunov, S., Vaikuntanathan, V., & Wee, H. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488677 · Cited by 406
Improved Delegation of Computation Using Fully Homomorphic Encryption
Chung, K.-M., Kalai, Y., & Vadhan, S. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_26 · Cited by 403
Self-citationVerifiable Delegation of Computation over Large Datasets
Benabbas, S., Gennaro, R., & Vahlis, Y. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22792-9_7 · Cited by 379
How to Delegate and Verify in Public: Verifiable Computation from Attribute-Based Encryption
Parno, B., Raykova, M., & Vaikuntanathan, V. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-28914-9_24 · Cited by 355
New Algorithms for Secure Outsourcing of Modular Exponentiations
Chen, X., Li, J., Ma, J., Tang, Q., & Lou, W. (2014) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2013.180 · Cited by 307
Homomorphic Signatures for Polynomial Functions
Boneh, D., & Freeman, D. M. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20465-4_10 · Cited by 307
Recursive composition and bootstrapping for SNARKS and proof-carrying data
Bitansky, N., Canetti, R., Chiesa, A., & Tromer, E. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488623 · Cited by 304
Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings
Maller, M., Bowe, S., Kohlweiss, M., & Meiklejohn, S. (2019) · Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3319535.3339817 · Cited by 290
Succinct Non-interactive Arguments via Linear Interactive Proofs
Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., & Ostrovsky, R. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-36594-2_18 · Cited by 274
Spartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup
Setty, S. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-56877-1_25 · Cited by 262
Verifiable Computation over Large Database with Incremental Updates
Chen, X., Li, J., Weng, J., Ma, J., & Lou, W. (2016) · IEEE Transactions on Computers · doi:10.1109/tc.2015.2512870 · Cited by 257
Parno (2016) · doi:10.1145/2856449 · Cited by 212
“[20] (GKR), which draw on many techniques from the PCP literature.”
BackgroundzkLLM: Zero Knowledge Proofs for Large Language Models
Sun, H., Li, J., & Zhang, H. (2024) · Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3658644.3670334 · Cited by 55
zkDL: Efficient Zero-Knowledge Proofs of Deep Learning Training
Sun, H., Bai, T., Li, J., & Zhang, H. (2025) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3520863 · Cited by 33
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.