A Secure Algorithm for Outsourcing Matrix Multiplication Computation in the Cloud

Matrix multiplication computation (MMC) is a common scientific and engineering computational task. But such computation involves enormous computing resources for large matrices, which is burdensome for the resource-limited clients. Cloud computing enables computational resource-limited clients to economically outsource such problems to the cloud server. However, outsourcing matrix multiplication to the cloud brings great security concerns and challenges since the matrices and their products often usually contains sensitive information. In a previous work, Lei et al. [1] proposed an algorithm for secure outsourcing MMC by using permutation matrix and the authors argued that it can achieve data privacy. In this paper, we first review the design of Lei's scheme and find a security vulnerability in their algorithm that it reveals the number of zero element in the input matrix to cloud server. Then we present a new verifiable, efficient, and privacy preserving algorithm for outsourcing MMC, which can protect the number privacy of zero elements in original matrices. Our algorithm builds on a series of carefully-designed pseudorandom matrices and well-designed privacy-preserving matrix transformation. Security analysis shows that our algorithm is practically-secure, and offers a higher level of privacy protection than the state-of-the-art algorithm.