Paper 2014/133

Efficient Secure and Verifiable Outsourcing of Matrix Multiplications

Yihua Zhang and Marina Blanton

Abstract

With the emergence of cloud computing services, a resource-constrained client can outsource its computationally-heavy tasks to cloud providers. Because such service providers might not be fully trusted by the client, the need to verify integrity of the returned computation result arises. The ability to do so is called verifiable delegation or verifiable outsourcing. Furthermore, the data used in the computation may be sensitive and it is often desired to protect it from the cloud throughout the computation. In this work, we put forward solutions for verifiable outsourcing of matrix multiplications that favorably compare with the state of the art. The cost of verifying the result of computation consists of a single modulo exponentiation and can be further reduced if the cloud is rational (or lazy). A lazy cloud tries to minimize its work by skipping the computation, but does not maliciously corrupt the data. Our solutions achieve several desired features such as data protection, public verifiability, and computation chaining.