Bren Hall, Room 1420, 1pm

June 1, 2012:

We introduce *Signatures of Correct Computation* (SCC), a new
model for verifying computation in cloud settings. In an SCC model, a
trusted *source* outsources a function *f* to an untrusted
*server*, along with a public key for that function. The server
can then produce a succinct signature σ vouching for the
correctness of the computation of *f*, i.e., that some result *v* is
indeed the correct outcome of the function *f* evaluated on some point
**a**. Moreover, the signature verification must take
asymptotically less time than evaluating the function *f*. We
construct efficient SCC schemes supporting expressive manipulations
over multivariate polynomials, including polynomial evaluation and
differentiation, and we prove that our constructions are
adaptively-secure in the random oracle model.

We also show that signatures of correct computation imply
*Publicly Verifiable Computation* (PVC), a model recently
introduced by the research community. Roughly speaking, in the SCC
model, *any client* can verify the signature σ and be
convinced of some computation result, whereas in the PVC model only
the client that issued a query (or anyone who trusts this client) can
verify that the server returned a valid signature (proof). Our
techniques can be readily adapted to construct publicly verifiable
computation schemes with adaptive security and *without the
random oracle model*.

(Joint work with Elaine Shi of UC Berkeley and University of Maryland and Roberto Tamassia of Brown University)