Efficient and Publicly Verifiable Outsourcing of Large-scale Matrix Multiplication

Abstract

Matrix multiplication is an important operation, whose computation overhead is large for the matrix with big size. The researchers seek to delegate the computation to the cloud service provider with abundant resources. The security issues arise because the user loses direct control on the data, such as privacy preservation, result verification, etc. We investigate the problem of publicly verifiable matrix multiplication, where the third party verifier can verify the correctness of the returned result from the service provider with public key. The state-of-the-art schemes work inefficiently in practice because a number of computationally expensive operations are utilized for the purpose of public verification. We introduce the notion of matrix digest, on which an efficient scheme MD- VCMatrix is presented. A one-dimensional vector is used for the verification-related computing, which is inverted from the original two-dimensional matrix. The computing on the verification-related computing is decreased significantly, thus the running efficiency of the related algorithms is promoted. We further present a fast algorithm for computing the batch of exponentiations. The security analysis demonstrates the security of our proposed outsourcing scheme, and the performance analysis shows the running efficiency of the scheme.