Efficient Verifiable Outsourcing of Solving Large-Scale Linear Equations with Low Storage Overhead

This paper studies the secure outsourcing problem of large-scale linear equations, and proposes a new secure outsourcing scheme of large-scale linear equations in the fully malicious model. First, we construct a pseudo-random invertible sparse matrix generation algorithm involving pseudo-random number generator and the property of strictly diagonally dominant matrix. Then we combine this algorithm with the process of encoding/decoding dense matrix with sparse matrix and give the new outsourcing scheme. The client in our scheme only needs 1 round interaction with the server and can detect the misbehavior of the server with an overwhelming probability (fully verifiable). In addition, compared with the previous schemes which require expensive storage overhead, our scheme reduces the overhead of storage to a constant level for the first time. We give the theoretical proof of the correctness, privacy and unforgeability of our scheme. Besides, the scheme can successfully handle the equations with no solution with enough privacy in our model. We compare the scheme with others and indicate the proposed scheme is superior to the existing ones in terms of efficiency, verifiability and storage overhead and finally provide the experimental evaluation that demonstrates the efficiency of our algorithms and the storage overhead the client needs.