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)