Valerio Pastro

Verifiable Computation over Encrypted Data in the Presence of
Verification Queries


We consider the problem of a client who outsources the computation of
a function f over an input x to a server, who returns y=f(x).
The client wants to be assured of the correctness of the computation
and wants to preserve confidentiality of the input x and possibly of
the function f as well.

This is the problem of secure outsourced computation over encrypted
data. Most of the work on outsourced computation in the literature
focuses on either privacy of the data, using Fully Homomorphic
Encryption (FHE), or the integrity of the computation. Previous
solutions which achieve both do so in a very limited security model
where the server is not allowed to
issue verification queries to the client: i.e. is not allowed to
``see'' if the client accepts or rejects the value y.

In this paper we present:

1. A formal definition of private and secure outsourced
computation in the presence of verification queries;

2. A protocol based on FHE that achieves the above definition for
arbitrary poly-time computations;

3. Some additional protocols for the computation of ad-hoc
functions (such as the computation of polynomials and linear
combinations) over encrypted data. These protocols do not use the
power of FHE, and therefore are much more efficient than the generic
approach. We point out that existing protocols in the literatures for
these tasks
become insecure in the presence of verification queries,
while our protocols can be proven in the stronger security model where
verification queries are allowed.