@inproceedings{parno2013pinocchio,
author = {Parno, Bryan and Howell, Jon and Gentry, Craig and Raykova, Mariana},
title = {Pinocchio: Nearly Practical Verifiable Computation},
booktitle = {Proceedings of the IEEE Symposium on Security and Privacy},
year = {2013},
month = {May},
abstract = {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.

For the full version of our paper, including a correction to the verification procedure, see http://eprint.iacr.org/2013/279

Pinocchio's source code is also available! Visit https://vc.codeplex.com for more info.

Coverage from the MIT Technology Review: http://www.technologyreview.com/news/515081/microsoft-and-ibm-researchers-develop-a-lie-detector-for-the-cloud/},
publisher = {IEEE},
url = {http://approjects.co.za/?big=en-us/research/publication/pinocchio-nearly-practical-verifiable-computation/},
edition = {Proceedings of the IEEE Symposium on Security and Privacy},
note = {Best Paper Award},
}