Secure and Efficient Outsourcing of Large-Scale Overdetermined Systems of Linear Equations

We address overdetermined systems of linear equations, where the number of unknowns is smaller than the number of equations so that only approximate solutions exist instead of exact solutions. Such systems are prevalent in many areas of science and engineering, and finding the optimal solutions is mathematically known as the linear least squares (LLS) problem. Real-world overdetermined systems are often large-scale and computationally expensive to solve. Consequently, we are interested in connecting the LLS problem with cloud computing, where a resource-constrained client outsources the problem to a powerful but untrusted cloud. Among several security considerations is that the input of and solution to the LLS problem usually contain the client's private information, which necessitates privacy-preserving outsourcing. In this paper, we present a construction called Sells, which employs a mathematical method called QR decomposition to solve the above problem, in a masked yet verifiable manner. One advantage of adopting QR decomposition is that in certain circumstances, solving a batch of LLS problems only requires fully executing Sells once, where certain intermediate result can be reused and the overall efficiency is greatly improved. Theoretical analysis shows that our proposal is verifiable, recoverable, and privacy-preserving. Experiments demonstrate that a client can benefit from the scheme not only reduced computation cost but also accelerated problem solving.