Efficient Verifiable Computation and Applications to a System for Nearly Practical Verifiable Computation, Pinocchio
Efficient Verifiable Computation and Applications to a System for Nearly Practical Verifiable Computation, Pinocchio.
Speaker: Mariana Raykova, Columbia University
Time and Place: Monday, 12/15, at 11am in 10.099 (2 MetroTech)
To instill greater confidence in computations outsourced to the cloud, clients should be able to verify the correctness of the results returned. Verifiable computation (VC) offers a solution to this problem providing functionality that allows a client to ask a server to compute F(x) for a given function F and an input x and then verify the correctness of the returned result in considerably less time than it would take to compute F from scratch.
We propose a new solution for verifiable computation that achieves improved efficiency both for the client and the server. As a main ingredient for our construction we introduce a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs), which is a natural extension of span programs defined by Karchmer and Wigderson. We also construct Quadratic Arithmetic Programs (QAPs), that “naturally” compute arithmetic circuits over large fields. Using QSPs and QAPs we obtain a scheme for verifiable computation that attains the shortest proof, most efficient prover, and most efficient verifier of previous techniques.
Our verifiable computation protocol from QAPs exhibits efficiency also in practical terms. To demonstrate this we introduce
Pinocchio, a built system for efficiently verifying general computations, which implements our VC construction from QAPs.
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-60×.
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 tool chain that compiles a subset of C into programs that implement the verifiable
computation protocol.
Joint work with Rosario Gennaro, Craig Gentry, Jon Howell, Bryan Parno
Bio:
Mariana Raykova is a Computer Scientist at SRI International. She received her PhD from Columbia University in 2012
advised by Tal Malkin and Steven Bellovin. After that she spent a year as a postdoc at the crypto group of IBM Research Watson.
Her work, which includes obfuscation, secure computation, verifiable computation and others, has been published in leading theory,
cryptography and security venues. She is an author of the paper "Candidate Obfuscation Indistinguishability Obfuscation and
Functional Encryption for All Circuits" that introduced the first general obfuscation construction. Her work "Pinocchio: Nearly Practical
Verifiable Computation" received best paper award at the IEEE Symposium on Privacy and Security, 2013.