Efficient and Verifiable Algorithm for Secure Outsourcing of Large-scale Linear Programming

摘要

Linear programming (LP) has been well studied in the scientific community for various engineering applications such as network flow problems, packet routing, portfolio optimization, and financial data management, etc. In this paper, we first utilize the sparse matrix to investigate secure outsourcing for large-scale LP systems, which is considered as a prohibitively expensive computation for the clients with resource-constraint devices. Besides, we propose a secure and practical scheme which is suitable for any LP problem (feasible, infeasible or unbounded) even in the fully malicious model. Compared with the state-of-the-art algorithm Wanglp, our proposed algorithm only requires O(n^2) computational overhead instead of O(n^rho) for 2