Paper 2013/469

Verifiable Delegation of Computation on Outsourced Data

Michael Backes, Dario Fiore, and Raphael M. Reischuk

Abstract

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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACM CCS 2013
Keywords
Verifiable Delegation of ComputationCloudComputingSecure Data OutsourcingHomomorphic MACsAmortized Closed-Form Efficient PRF
Contact author(s)
fiore @ mpi-sws org
History
2013-08-02: received
Short URL
https://ia.cr/2013/469
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/469,
      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{https://eprint.iacr.org/2013/469}},
      url = {https://eprint.iacr.org/2013/469}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.