Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
Speaker
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 widespread attention 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 will discuss a specific instance of this paradigm to the case of computations over large datasets. 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.
About the Speaker
Rosario Gennaro's research interests are in cryptography and network security. More specifically, he works on the design of efficient and provably secure cryptographic algorithms, secure distributed protocols, and the theoretical foundations of cryptography. Other interests are machine learning, number theory, computational geometry, algorithms, and data structures. Before joining IBM Research, he received a PhD in Electrical Engineering and Computer Science from MIT, where he was a member of the Theory of Computation group at the Laboratory for Computer Science. His PhD advisor was Prof. Silvio Micali.