Date Added: Mar 2011
The authors study the problem of computing on large datasets that are stored on an untrusted server. They follow the approach of amortized verifiable computation introduced by Gennaro, Gentry, and Parno in CRYPTO 2010. They present the first practical verifiable computation scheme for high degree polynomial functions. Such functions can be used, for example, to make predictions based on polynomials fitted to a large number of sample points in an experiment. In addition to the many non-cryptographic applications of delegating high degree polynomials, they use the verifiable computation scheme to obtain new solutions for verifiable keyword search, and proofs of retrievability.