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
Trading group theory for randomness
Babai, L. (1985) · Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85 · doi:10.1145/22145.22192 · Cited by 772
Proof verification and hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1992) · Proceedings., 33rd Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1992.267823 · Cited by 741
Algebraic methods for interactive proof systems
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992) · Journal of the ACM · doi:10.1145/146585.146605 · Cited by 711
Shamir, A. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 662
Checking computations in polylogarithmic time
Babai, L., Fortnow, L., Levin, L. A., & Szegedy, M. (1991) · Proceedings of the twenty-third annual ACM symposium on Theory of computing - STOC '91 · doi:10.1145/103418.103428 · Cited by 616
A note on efficient zero-knowledge proofs and arguments (extended abstract)
Kilian, J. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129782 · Cited by 606
Computationally Private Information Retrieval with Polylogarithmic Communication
Cachin, C., Micali, S., & Stadler, M. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_28 · Cited by 579
Constant depth circuits, Fourier transform, and learnability
Linial, N., Mansour, Y., & Nisan, N. (1993) · Journal of the ACM · doi:10.1145/174130.174138 · Cited by 572
Interactive proofs and the hardness of approximating cliques
Feige, U., Goldwasser, S., Lovász, L., Safra, M., & Szegedy, M. (1996) · Journal of the ACM · doi:10.1145/226643.226652 · Cited by 525
Self-citationThe PCP theorem by gap amplification
Dinur, I. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132553 · Cited by 501
Multi-prover interactive proofs: how to remove intractability
Ben-Or, M., Goldwasser, S., Kilian, J., & Widgerson, A. (1988) · Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 · doi:10.1145/62212.62223 · Cited by 468
Self-citationZero-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
Designing programs that check their work
Blum, M., & Kannan, S. (1995) · Journal of the ACM · doi:10.1145/200836.200880 · Cited by 393
On the (In)security of the Fiat-Shamir paradigm
Goldwasser, S., & Kalai, Y. T. (2004) · 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. · doi:10.1109/sfcs.2003.1238185 · Cited by 311
Self-citationMicali, S. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365746 · Cited by 293
An Oblivious Transfer Protocol with Log-Squared Communication
Lipmaa, H. (2005) · Lecture Notes in Computer Science · doi:10.1007/11556992_23 · Cited by 271
Universal arguments and their applications
Barak, B., & Goldreich, O. (2003) · Proceedings 17th IEEE Annual Conference on Computational Complexity · doi:10.1109/ccc.2002.1004355 · Cited by 244
Evaluating Branching Programs on Encrypted Data
Ishai, Y., & Paskin, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-70936-7_31 · Cited by 228
Bit Commitment Using Pseudo-Randomness
Naor, M. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_13 · Cited by 206
Everything Provable is Provable in Zero-Knowledge
Ben-Or, M., Goldreich, O., Goldwasser, S., Håstad, J., Kilian, J., Micali, S., & Rogaway, P. (1990) · Lecture Notes in Computer Science · doi:10.1007/0-387-34799-2_4 · Cited by 192
Self-citationNearly-linear size holographic proofs
Polishchuk, A., & Spielman, D. A. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195132 · Cited by 191
Nondeterministic exponential time has two-prover interactive protocols
Babai, L., Fortnow, L., & Lund, C. (2002) · Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science · doi:10.1109/fscs.1990.89520 · Cited by 188
Short PCPs Verifiable in Polylogarithmic Time
Ben‐Sasson, E., Goldreich, O., Harsha, P., Sudan, M., & Vadhan, S. (2005) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2005.27 · Cited by 128
Robust pcps of proximity, shorter pcps and applications to coding
Ben‐Sasson, E., Goldreich, O., Harsha, P., Sudan, M., & Vadhan, S. (2004) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1007352.1007361 · Cited by 110
Public Computing: Reconnecting People to Science
Anderson, D. P. (2003) · Cited by 102
Kalai, Y. T., & Raz, R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70583-3_44 · Cited by 67
Self-citationProbabilistically Checkable Arguments
Kalai, Y. T., & Raz, R. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03356-8_9 · Cited by 59
Self-citationImproved Efficient Arguments (Preliminary Version)
Kilian, J. (1995) · International Cryptology Conference · Cited by 56
Verifying and decoding in constant depth
Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., & Rothblum, G. N. (2007) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1250790.1250855 · Cited by 37
Self-citationInteractive proof systems and alternating time—space complexity
Fortnow, L., & Lund, C. (1993) · Theoretical Computer Science · doi:10.1016/0304-3975(93)90210-k · Cited by 36
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
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.