Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers

Rosario Gennaro, IBM Research

Abstract:

In this talk I will present protocols that allow a computationally weak client to securely outsource arbitrary computations to a powerful server. Security in this context means that the client will receive an assurance that the computation performed by the server is correct, with the optional property that the client will be able to hide some of his data from the server. The problem of securely outsourcing computation has received widespreadattention due to the rise of cloud computing a paradigm where businesses lease computing resources from a service rather than maintain their own infrastructure. A crucial component of secure cloud computing is a mechanism that enforces the integrity and correctness of the computations done by the provider.Of course, the computation invested by the (weak) client in order to verify the result of the server's computation must be substantially smaller than the amount of computation required to perform the work to begin with. In the first part of the talk I will present a a protocol that allows the worker to return a computationally-sound, non-interactive proof for any computation that can be verified in linear time. The protocol requires a one-time expensive pre-processing stage by the client which can be amortized over several invocations of the protocol. Our scheme also provides privacy for the client, meaning that the server does not learn any information about the input to the computation. In the second part of the talk I willdiscuss a specific instance of this paradigm to the case of computations over large data-sets. I will present the first practical verifiable computation scheme for high degree polynomial functions. In addition to the many non-cryptographic applications of delegating high degree polynomials, we use our verifiable computation scheme to obtain new solutions for verifiable keyword search, proofs of retrievability and verifiable databases. First result is joint work with Craig Gentry and Bryan Parno. The second result is joint work with Yevgeniy Vahlis and Siavosh Benabbas

Time and Place

Nov 21 2011 (Monday) at 1630 hrs
Gates 463A