A secure and verifiable outsourcing scheme for matrix inverse computation

Matrix inverse computation is one of the most fundamental mathematical problems in large-scale data analytics and computing. It is often too expensive to be solved in resource-constrained devices such as sensors. Outsourcing the computation task to a cloud server or a fog server is a potential approach as the server is able to perform large-scale scientific computations on behalf of resource-constrained users with special software. However, outsourcing brings in new security concerns and challenges such as data privacy violations and result invalidation. In this paper, we propose a secure and verifiable outsourcing scheme to compute the matrix inverse in a server. In our scheme, the client generates two secret key sets based on two chaotic systems, which are utilized to create two sparse matrices whose permuted versions are used for matrix encryption and decryption to protect input and output privacy. The server computes the inverse over the ciphertext matrix and returns the result to the client who can verify the validity of the inverse. We analyze the proposed scheme in terms of correctness, security, verifiability, and attack resistance, and compare its performance (computation, storage, and communication overheads) with those of the state-of-the-art. Our theoretical results and comparison study demonstrate that the proposed scheme provides a secure and efficient outsourcing mechanism for matrix inverse computation.

I. Introduction

Computing the inverse of a matrix is one of the most basic algebraic problems in scientific research. Such a computation appears in many science and engineering fields such as traffic navigation [1], image encryption [2], [3], and image watermarking [4], [5]. When an end user has limited-restricted resources such as the smart phone used for lane-level navigation in [1], it is not practical to compute the matrix inverse in situ. An intuitive solution is for the user to outsource its heavy computational workloads to a server, which can help reduce the local computation overhead and avoid large capital outlays in hardware/software deployment and maintenance.