Verifiable Outsourced Computation joint work with Bryan Parno, Vinod Vaikuntanathan
Motivation: 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. From a practical point of view a VC scheme will be usable only
if it does not come with a big computation overhead, and most existing schemes for verifiable computation use fully homomorphic encryption, which is still too expensive for most practical applications. This makes the question
of constructing schemes that
achieve better efficiency even for a limited class of functions of particular interest.
Further the existing definition of verifiable computation does not exactly
fit all scenarios where VC is needed and for those some extensions of the
definition would be useful, two important directions for such extensions,
which have important applications in many
practical delegation scenarios, are: public delegation and
public verifiability. Yet, existing VC constructions based on standard
cryptographic assumptions fail to achieve these properties.
Results:
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 [GHW'11], 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.
Motivation: 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. From a practical point of view a VC scheme will be usable only
if it does not come with a big computation overhead, and most existing schemes for verifiable computation use fully homomorphic encryption, which is still too expensive for most practical applications. This makes the question
of constructing schemes that
achieve better efficiency even for a limited class of functions of particular interest.
Further the existing definition of verifiable computation does not exactly
fit all scenarios where VC is needed and for those some extensions of the
definition would be useful, two important directions for such extensions,
which have important applications in many
practical delegation scenarios, are: public delegation and
public verifiability. Yet, existing VC constructions based on standard
cryptographic assumptions fail to achieve these properties.