Paper 2013/469

Verifiable Delegation of Computation on Outsourced Data

Michael Backes, Dario Fiore, and Raphael M. Reischuk


We address the problem in which a client stores a large amount of data with an untrusted server in such a way that, at any moment, the client can ask the server to compute a function on some portion of its outsourced data. In this scenario, the client must be able to efficiently verify the correctness of the result despite no longer knowing the inputs of the delegated computation, it must be able to keep adding elements to its remote storage, and it does not have to fix in advance (i.e., at data outsourcing time) the functions that it will delegate. Even more ambitiously, clients should be able to verify in time independent of the input-size – a very appealing property for computations over huge amounts of data. In this work we propose novel cryptographic techniques that solve the above problem for the class of computations of quadratic polynomials over a large number of variables. This class covers a wide range of significant arithmetic computations – notably, many important statistics. To confirm the efficiency of our solution, we show encouraging performance results, e.g., correctness proofs have size below 1 kB and are verifiable by clients in less than 10 milliseconds.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2013
Verifiable Delegation of ComputationCloudComputingSecure Data OutsourcingHomomorphic MACsAmortized Closed-Form Efficient PRF
Contact author(s)
fiore @ mpi-sws org
2013-08-02: received
Short URL
Creative Commons Attribution


      author = {Michael Backes and Dario Fiore and Raphael M.  Reischuk},
      title = {Verifiable Delegation of Computation on Outsourced Data},
      howpublished = {Cryptology ePrint Archive, Paper 2013/469},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.