joint works with Rosario Gennaro, Craig Gentry, Jon Howell, Bryan Parno, Vinod Vaikuntanathan |
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 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. Resources: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. |
|
Resources:
|