Mariana Raykova
Columbia University

How to Delegate and Verify in Public: Verifiable Computation from Attribute-based Encryption

The wide variety of small, computationally weak devices, and the
growing number of computationally intensive tasks makes the
delegation of computation to large data centers a desirable solution.
However, computation outsourcing is useful only when the result
returned can be trusted, which makes verifiable computation (VC)
a must for such scenarios. In this work we extend the definition of
verifiable computation in two important directions: public delegation
and public verifiability, which have important applications in many
practical delegation scenarios. Yet, existing VC constructions
based on standard cryptographic assumptions fail to achieve
these properties. As the primary contribution of our work, 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~\cite{green2011outsource},
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.

Joint work with:
Bryan Parno and Vinod Vaikuntanathan