Publicly Verifiable Delegation of Large Polynomials and Matrix Computations, with Applications

Dario Fiore; Rosario Gennaro

Paper 2012/281

Publicly Verifiable Delegation of Large Polynomials and Matrix Computations, with Applications

Dario Fiore and Rosario Gennaro

Abstract

Outsourced computations (where a client requests a server to perform some computation on its behalf) are becoming increasingly important due to the rise of Cloud Computing and the proliferation of mobile devices. Since cloud providers may not be trusted, a crucial problem is the verification of the integrity and correctness of such computation, possibly in a {\em public} way, i.e., the result of a computation can be verified by any third party, and requires no secret key -- akin to a digital signature on a message. We present new protocols for publicly verifiable secure outsourcing of {\em Evaluation of High Degree Polynomials} and {\em Matrix Multiplication}. Compared to previously proposed solutions, ours improve in efficiency and offer security in a stronger model. The paper also discusses several practical applications of our protocols.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. This is the full version of the paper that appears in the proceedings of ACM CCS 2012
Keywords: verifiable computation PRF
Contact author(s): fiore @ cs nyu edu
History: 2012-07-23: revised; 2012-05-29: received; See all versions
Short URL: https://ia.cr/2012/281
License: CC BY

BibTeX

@misc{cryptoeprint:2012/281,
      author = {Dario Fiore and Rosario Gennaro},
      title = {Publicly Verifiable Delegation of Large Polynomials and Matrix Computations, with Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/281},
      year = {2012},
      url = {https://eprint.iacr.org/2012/281}
}