The DOI matches its Crossref record; 67 of the 72 references it cites were found in a registry or an index.
Pinocchio: Nearly Practical Verifiable Computation
Open accessAbstract
To instill greater confidence in computations outsourced to the cloud, clients should be able to verify the correctness of the results returned. To this end, we introduce Pinocchio, a built system for efficiently verifying general computations while relying only on cryptographic assumptions. With Pinocchio, the client creates a public evaluation key to describe her computation; this setup is proportional to evaluating the computation once. The worker then evaluates the computation on a particular input and uses the evaluation key to produce a proof of correctness. The proof is only 288 bytes, regardless of the computation performed or the size of the inputs and outputs. Anyone can use a public verification key to check the proof. Crucially, our evaluation on seven applications demonstrates that Pinocchio is efficient in practice too. Pinocchio's verification time is typically 10ms: 5-7 orders of magnitude less than previous work; indeed Pinocchio is the first general-purpose system to demonstrate verification cheaper than native execution (for some apps). Pinocchio also reduces the worker's proof effort by an additional 19-60x. As an additional feature, Pinocchio generalizes to zero-knowledge proofs at a negligible cost over the base protocol. Finally, to aid development, Pinocchio provides an end-to-end toolchain that compiles a subset of C into programs that implement the verifiable computation protocol.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“In this direction, [118] proposed a multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK [95], which is the baseline for Zcash [17].”
From Privacy-Preserving Solutions for Blockchain: Review and Challenges (2019) · cites this paper as [95]
The cited source says what the claim attributes to it.
In the citing paper
“Pinocchio by Parno et al. in 2013 which applies ZKP to reallife use cases [128]”
From A Survey of Self-Sovereign Identity Ecosystem (2021) · cites this paper as [128]
In the citing paper
“Man-in-the-Middle attacks [84], [85] intercept the models exchanged between the clients and the server and replace them with malicious model updates.”
From Vulnerabilities in federated learning (2021) · cites this paper as [85]
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
Adomavičius, G., & Tuzhilin, A. (2005) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2005.99 · Cited by 10,539
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,098
Identity-Based Encryption from the Weil Pairing
Boneh, D., & Franklin, M. (2003) · SIAM Journal on Computing · doi:10.1137/s0097539701398521 · Cited by 3,540
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
Practical byzantine fault tolerance and proactive recovery
Castro, M., & Liskov, B. (2002) · ACM Transactions on Computer Systems · doi:10.1145/571637.571640 · Cited by 2,475
A fully homomorphic encryption scheme
Boneh, D., & Gentry, C. (2009) · Cited by 2,341
Self-citationLattice Gas Cellular Automata and Lattice Boltzmann Models
Wolf-Gladrow, D. A. (2000) · Lecture notes in mathematics · doi:10.1007/b72010 · Cited by 1,623
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,449
Short Signatures Without Random Oracles
Boneh, D., & Boyen, X. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-24676-3_4 · Cited by 1,448
Hierarchical Identity Based Encryption with Constant Size Ciphertext
Boneh, D., Boyen, X., & Goh, E.-J. (2005) · Lecture notes in computer science · doi:10.1007/11426639_26 · Cited by 1,342
SETI@home: an experiment in public-resource computing
Anderson, D. P., Cobb, J., Korpela, E., Lebofsky, M., & Werthimer, D. (2002) · Communications of the ACM · doi:10.1145/581571.581573 · Cited by 1,302
Probabilistic checking of proofs
Arora, S., & Safra, M. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,158
Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
Gennaro, R., Gentry, C., & Parno, B. J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14623-7_25 · Cited by 1,156
Self-citationProofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols
Cramer, R., Damgård, I., & Schoenmakers, B. (2007) · Springer eBooks · doi:10.1007/3-540-48658-5_19 · Cited by 1,148
Efficient Non-interactive Proof Systems for Bilinear Groups
Groth, J., & Sahai, A. (2008) · Springer eBooks · doi:10.1007/978-3-540-78967-3_24 · Cited by 1,078
Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys
Boneh, D., Gentry, C., & Waters, B. R. (2005) · Lecture notes in computer science · doi:10.1007/11535218_16 · Cited by 1,051
Self-citationDesign and implementation of a TCG-based integrity measurement architecture
Sailer, R., Zhang, X., Jaeger, T., & van Doorn, L. (2004) · USENIX Security Symposium · Cited by 1,041
Pairing-Friendly Elliptic Curves of Prime Order
Barreto, P. S. L. M., & Naehrig, M. (2006) · Lecture notes in computer science · doi:10.1007/11693383_22 · Cited by 880
Homomorphic Evaluation of the AES Circuit
Gentry, C., Halevi, S., & Smart, N. P. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32009-5_49 · Cited by 828
Self-citationFairplay—a secure two-party computation system
Malkhi, D., Nisan, N., Benny Pinkas, B., & Sella, Y. (2004) · Cited by 791
Quadratic Span Programs and Succinct NIZKs without PCPs
Gennaro, R., Gentry, C., Parno, B. J., & Raykova, M. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38348-9_37 · Cited by 751
Self-citationA note on efficient zero-knowledge proofs and arguments (extended abstract)
Kilian, J. (1992) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/129712.129782 · Cited by 611
Architectural support for copy and tamper resistant software
Lie, D., Codesourcery, M. M., Lincoln, P. D., Boneh, D., Mitchell, J. C., & Horowitz, M. (2000) · ACM SIGARCH Computer Architecture News · doi:10.1145/378995.379237 · Cited by 597
Faster Secure Two-Party Computation Using Garbled Circuits
Huang, Y., Evans, D., Katz, J. I., & Malka, L. (2011) · doi:10.18130/v3hj5c · Cited by 566
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374396 · Cited by 484
Separating succinct non-interactive arguments from all falsifiable assumptions
Gentry, C., & Wichs, D. (2011) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1993636.1993651 · Cited by 456
Self-citationShort Pairing-Based Non-interactive Zero-Knowledge Arguments
Groth, J. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-17373-8_19 · Cited by 454
Blum, M., Santis, A. D., Micali, S. M., & Persiano, G. (1991) · SIAM Journal on Computing · doi:10.1137/0220068 · Cited by 427
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
Improved Delegation of Computation Using Fully Homomorphic Encryption
Chung, K.-M., Kalai, Y. T., & Vadhan, S. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14623-7_26 · Cited by 404
Relations Among Complexity Measures
Pippenger, N. J., & Fischer, M. J. (1979) · Journal of the ACM · doi:10.1145/322123.322138 · Cited by 388
On Cryptographic Assumptions and Challenges
Naor, M. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45146-4_6 · Cited by 364
Towards Practical Public Key Systems Secure Against Chosen Ciphertext attacks
Damgård, I. (2007) · Springer eBooks · doi:10.1007/3-540-46766-1_36 · Cited by 358
How to Delegate and Verify in Public: Verifiable Computation from Attribute-Based Encryption
Parno, B. J., Raykova, M., & Vaikuntanathan, V. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28914-9_24 · Cited by 355
Self-citationPrivacy-preserving smart metering
Rial, A., & Danezis, G. (2011) · ACM Workshop on Privacy in the Electronic Society (WPES) · doi:10.1145/2046556.2046564 · Cited by 314
Uncheatable Distributed Computations
Golle, P., & Mironov, I. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45353-9_31 · Cited by 256
The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols
Bellare, M., & Palacio, A. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-28628-8_17 · Cited by 236
Architectural Support for Copy and Tamper Resistant Software
Lie, D., Thekkath, C. A., Codesourcery, M. M., Lincoln, P. D., & Boneh, D. (2000) · doi:10.21236/ada419599 · Cited by 210
Practical verified computation with streaming interactive proofs
Cormode, G., Mitzenmacher, M., & Thaler, J. (2012) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2090236.2090245 · Cited by 201
A protocol for property-based attestation
Chen, L., Landfermann, R., Löhr, H., Rohe, M., Sadeghi, A., & Stüble, C. (2006) · Scalable Trusted Computing · doi:10.1145/1179474.1179479 · Cited by 192
Architecture for Protecting Critical Secrets in Microprocessors
Lee, R. B.-L., Kwan, P. C. S., McGregor, J. P., Dwoskin, J. S., & Wang, Z. (2005) · ACM SIGARCH Computer Architecture News · doi:10.1145/1080695.1069971 · Cited by 168
Making argument systems for outsourced computation practical (sometimes)
Setty, S., McPherson, R., Blumberg, A. J., & Walfish, M. (2012) · Cited by 151
Sadeghi, A., Schneider, T. H., & Winandy, M. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13869-0_30 · Cited by 146
Query execution assurance for outsourced databases
Sion, R. (2005) · Cited by 142
A Hybrid Architecture for Interactive Verifiable Computation
Vu, V., Setty, S., Blumberg, A. J., & Walfish, M. (2013) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2013.48 · Cited by 140
Architecture for Protecting Critical Secrets in Microprocessors
Lee, R. B.-L., Kwan, P. C. S., McGregor, J. P., Dwoskin, J. S., & Wang, Z. (2005) · Proceedings - International Symposium on Computer Architecture/Proceedings · doi:10.1109/isca.2005.14 · Cited by 138
Taking proof-based verified computation a few steps closer to practicality
Setty, S., Vu, V., Panpalia, N., Braun, B., Blumberg, A. J., & Walfish, M. (2012) · Cited by 131
Resolving the conflict between generality and plausibility in verified computation
Setty, S., Braun, B., Vu, V., Blumberg, A. J., Parno, B. J., & Walfish, M. (2013) · European Conference on Computer Systems · doi:10.1145/2465351.2465359 · Cited by 128
Self-citationSecure two-party computations in ANSI C
Holzer, A., Franz, M., Katzenbeisser, S., & Veith, H. (2012) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2382196.2382278 · Cited by 125
Efficient Arguments without Short PCPs
Ishai, Y., Eyal Kushilevitz, Z., & Ostrovsky, R. (2007) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2007.10 · Cited by 123
Gennaro, R. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-28628-8_14 · Cited by 106
New Software Speed Records for Cryptographic Pairings
Naehrig, M., Niederhagen, R., & Schwabe, P. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-14712-8_7 · Cited by 106
Secure Computation on Floating Point Numbers.
Aliasgari, M., Blanton, M., Zhang, Y., & Steele, A. (2012) · Cited by 98
Distributed Execution with Remote Audit.
Monrose, F., Wyckoff, P., & Rubin, A. D. (1999) · Cited by 97
Bootstrapping Trust in Modern Computers
Parno, B. J., McCune, J. M., & Perrig, A. (2011) · SpringerBriefs in computer science · doi:10.1007/978-1-4614-1460-5 · Cited by 69
Self-citationSecure Distributed Computing in a Commercial Environment
Golle, P., & Stubblebine, S. G. (2002) · Lecture notes in computer science · doi:10.1007/3-540-46088-8_23 · Cited by 68
Chen, Y., & Sion, R. (2011) · ACM Symposium on Cloud Computing (SoCC) · doi:10.1145/2038916.2038945 · Cited by 67
Proofs of partial knowledge and simplified design of witness hiding protocols
Cramer, R., Damgård, I., & Schoenmakers, L. B. (1995) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · Cited by 56
A Certifying Compiler for Zero-Knowledge Proofs of Knowledge Based on Σ-Protocols
Almeida, J. B., Bangerter, E., Barbosa, M., Krenn, S., Sadeghi, A., & Schneider, T. H. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-15497-3_10 · Cited by 52
Billion-Gate Secure Computation with Malicious Adversaries
Kreuter, B., Shelat, A. A., & Shen, C.-H. (2012) · Cited by 52
ZKPDL: A Language-Based System for Efficient Zero-Knowledge Proofs and Electronic Cash
Meiklejohn, S., Erway, C. C., Küpçü, A., Hinkle, T., & Lysyanskaya, A. (2010) · doi:10.13140/rg.2.1.2367.9767 · Cited by 51
Searching for High-Value Rare Events with Uncheatable Grid Computing
Du, W. K., & Goodrich, M. T. (2005) · Lecture notes in computer science · doi:10.1007/11496137_9 · Cited by 32
On the Evaluation of Powers and Related Problems (Preliminary Version)
Pippenger, N. J. (1976) · Cited by 27
Verifiable Computation with Massively Parallel Interactive ProofsPreprint
Thaler, J., Roberts, M., Mitzenmacher, M., & Pfister, H. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1202.1350 · Cited by 27
Secure Remote Execution of Sequential Computations
Karame, G., Strasser, M., & Čapkun, S. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-11145-7_15 · Cited by 26
Uncheatable Reputation for Distributed Computation Markets
Cărbunar, B., & Sion, R. (2006) · Lecture notes in computer science · doi:10.1007/11889663_7 · Cited by 12
Cited by
Sorted by citations
Zerocash: Decentralized Anonymous Payments from Bitcoin
Ben‐Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., & Virza, M. (2014) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2014.36 · Cited by 1,987
Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts
Kosba, A., Miller, A., Shi, E., Wen, Z., & Papamanthou, C. (2016) · 2016 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2016.55 · Cited by 2,227
A Survey on the Edge Computing for the Internet of Things
Yu, W., Liang, F., He, X., Hatcher, W. G., Lu, C., Lin, J., & Yang, X. (2018) · IEEE Access · doi:10.1109/access.2017.2778504 · Cited by 1,520
On the Size of Pairing-Based Non-interactive Arguments
Groth, J. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49896-5_11 · Cited by 1,271
On Scaling Decentralized Blockchains
Croman, K., Decker, C., Eyal, I., Gencer, A. E., Juels, A., Kosba, A. E., Miller, A. E., Saxena, P., Shi, E., Sirer, E. G., et al. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53357-4_8 · Cited by 1,199
Metadata
- Authors
- Parno, B., Howell, J., Gentry, C., & Raykova, M.
- Affiliations
- Microsoft (United States) (US)
- IBM (United States) (US)
- Venue
- 2013 IEEE Symposium on Security and Privacy
- Publisher
- IEEE
- Published
- 2013-05
- Pages
- 238-252
- ISSN
- 1081-6011 (ISSN-L)
- OpenAlex
- W2018746447
- Cited by
- 864
- References
- 72
- Citations by year
- 2026: 40 · 2025: 44 · 2024: 68 · 2023: 70 · 2022: 101 · 2021: 95 · 2020: 82 · 2019: 68 · 2018: 54 · 2017: 52 · 2016: 55 · 2015: 51 · 2014: 54 · 2013: 25
- FWCI
- 39.83
- Type
- conference paper
- Language
- en
- Open access
- bronze
- doi.org
- Locations
- IEEE Symposium on Security and Privacy (S&P) (publishedVersion)
- Funders
- National Science Foundation (1017660)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Computer Science › Information Systems › Cloud Data Security Solutions
- Physical Sciences › Computer Science › Hardware and Architecture › Security and Verification in Computing
- Keywords
- verifiable computation, outsourced computation, cloud computing, correctness proofs, cryptographic assumptions, verification efficiency, zero-knowledge proofs, Pinocchio
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
