Motivation: The wide variety of small, computationally weak devices, and the growing number of computationally intensive tasks makes the delegation of computation to large data centers a desirable solution. However, computation outsourcing is useful only when the result returned can be trusted, which makes verifiable computation (VC) a must for such scenarios. From a practical point of view a VC scheme will be usable only if it does not come with a big computation overhead, and most existing schemes for verifiable computation use fully homomorphic encryption, which is still too expensive for most practical applications. This makes the question of constructing schemes that achieve better efficiency even for a limited class of functions of particular interest. Further the existing definition of verifiable computation does not exactly fit all scenarios where VC is needed and for those some extensions of the definition would be useful, two important directions for such extensions, which have important applications in many practical delegation scenarios, are: public delegation and public verifiability. Yet, existing VC constructions based on standard cryptographic assumptions fail to achieve these properties.

Results:

Quadratic Programs and Succinct NIZK. 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. Our main motivation is the quick construction of succinct, easily verified arguments for NP statements.

To achieve this goal, QSPs use a new approach to the well-known technique of arithmetization of Boolean circuits. Our new approach yields dramatic performance improvements. Using QSPs, we construct a NIZK argument - in the CRS model - for Circuit-SAT consisting of just 7 group elements. The CRS size and prover computation are quasi-linear, making our scheme seemingly quite practical, a result supported by our implementation. Indeed, our NIZK argument attains the shortest proof, most efficientcient prover, and most establishfficient verifier of any known technique.

We also present a variant of QSPs, called Quadratic Arithmetic Programs (QAPs), that naturally compute arithmetic circuits over large fields, along with succinct NIZK constructions that use QAPs. Finally, we show how QSPs and QAPs can be used to establishfficiently and publicly verify outsourced computations, where a client asks a server to compute F(x) for a given function F and must verify the result provided by the server in considerably less time than it would take to compute F from scratch. The resulting schemes are the most efficient, general-purpose publicly verifiable computation schemes.

Pinoccio: System for Verifiable Computation. 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.

VC from ABE. We establish an important (and somewhat surprising) connection between verifiable computation and attribute-based encryption (ABE), a primitive that has been widely studied. Namely, we show how to construct a VC scheme with public delegation and public verifiability from any ABE scheme. The VC scheme verifies any function in the class of functions covered by the permissible ABE policies. This scheme enjoys a very efficient verification algorithm that depends only on the output size. We show a similar construction from ABE with outsourced decryption [GHW'11], which gives us a multi-function VC scheme that allows the verifiable evaluation of multiple functions on the same preprocessed input. We also explore the opposite direction of the ABE-VC relationship and show an ABE construction from a modified VC scheme.