## Verifiable Delegation of Computation over Large
Datasets

**
Siavosh Benabbas, Rosario Gennaro, and Yevgeniy Vahlis**

*
University of Toronto, Canada;
IBM Research, USA; and
Columbia University, USA*
**Abstract.** We study the problem of computing on large datasets that
are stored on an untrusted server. We follow the approach of *amortized
verifiable computation* introduced by Gennaro, Gentry, and Parno
in CRYPTO 2010. We present the first practical verifiable computation
scheme for high degree polynomial functions. Such functions can be used,
for example, to make predictions based on polynomials tted to a large
number of sample points in an experiment. In addition to the many noncryptographic
applications of delegating high degree polynomials, we use
our veriable computation scheme to obtain new solutions for verifiable
keyword search, and proofs of retrievability. Our constructions are based
on the DDH assumption and its variants, and achieve adaptive security,
which was left as an open problem by Gennaro *et al*
(albeit for general functionalities).

Our second result is a primitive which we call a *verifiable database
* (VDB). Here, a weak client outsources a large table to an untrusted
server, and makes retrieval and update queries. For each query, the
server provides a response and a proof that the response was computed
correctly. The goal is to minimize the resources required by the client.
This is made particularly challenging if the number of update queries
is unbounded. We present a VDB scheme based on the hardness of the
subgroup membership problem in composite order bilinear groups.