Practical and Secure Outsourcing Algorithms of Matrix Operations Based on a Novel Matrix Encryption Method

With the recent growth and commercialization of cloud computing, outsourcing computation has become one of the most important cloud services, which allows the resource-constrained clients to efficiently perform large-scale computation in a pay-per-use manner. Meanwhile, outsourcing large scale computing problems and computationally intensive applications to the cloud has become prevalent in the science and engineering computing community. As important fundamental operations, large-scale matrix multiplication computation (MMC), matrix inversion computation (MIC), and matrix determinant computation (MDC) have been frequently used. In this paper, we present three new algorithms to enable secure, verifiable, and efficient outsourcing of MMC, MIC, and MDC operations to a cloud that may be potentially malicious. The main idea behind our algorithms is a novel matrix encryption/decryption method utilizing consecutive and sparse unimodular matrix transformations. Compared to previous works, this versatile technique can be applied to many matrix operations while achieving a good balance between security and efficiency. First, the proposed algorithms provide robust confidentiality by concealing the local information of the entries in the input matrices. Besides, they also protect the statistic information of the original matrix. Moreover, these algorithms are highly efficient. Our theoretical analysis indicates that the proposed algorithms reduce the time overhead on the client side from O(n(2.3728639)) to O(n(2)). Finally, the extensive experimental evaluations demonstrate the practical efficiency and effectiveness of our algorithms.