Verifiable Algorithm for Secure Outsourcing of Systems of Linear Equations in the Case of No Solution

摘要

Systems of linear equations, as a fundamental topic in the development of the computational sciences, have been well studied in the scientific community. In this paper, we investigate secure outsourcing for large-scale systems of linear equations, which is considered as a prohibitively expensive computation for the clients with limited computational resources. Based on Chen's work, we propose a verifiable algorithm for secure outsourcing of large-scale systems of linear equations in the case of no solution under the fully malicious model. We uniquely utilize linear programming, which is another well studied scientific computing problem, to help the client to verify the correctness of results returned by the server. Compared with the state-of-the-art algorithm (Chen et al' scheme), the proposed algorithm is suitable not only for any nonsingular dense matrix A, but for a set of singular matrixes that lead the system of linear equations has no solution. Besides, the computational complexity for the verification of no solution in our scheme is still O (n2). Therefore, our proposed algorithm is more suitable for real applications.