Research On Outsourcing Schemes Of Large-scale Linear Programming In Cloud Computing

With the rapid development of cloud computing, security and efficient outsourcing technologies are getting increasingly important, especially for the clients with resource-constraint devices. We study the secure outsourcing algorithms for large-scale linear programming systems. 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. Therefore, how to design a secure and practical outsouring algorithm for large-scale LP problems, which is considered as a prohibitively expensive computation for the clients with resource-constraint devices, is becoming more and more necessary. The main points of this paper are as follows:1. The paper studies the existing and secure outsouring schemes of large-scale LP problems, and focuses on the scheme based on transformation method, and then summarizes the advantages and disadvantages of the existing schemes.2. Under the fully malicious server model, in this paper, we first utilize the sparse matrix to investigate secure outsourcing for large-scale LP systems, and propose a secure and practical scheme which is suitable for any LP problem, including feasible, infeasible and unbounded cases. Compared with the state-of-the-art algorithm, our proposed algorithm only requires O(n2) computational overhead instead of O(nρ) for 2 < ρ ≤ 3.3. For the above three cases, we present a complete verification method which ensures that the client can detect the misbehavior of cloud server with the(optimal) probability1 under the computational complexity of O(n). Furthermore, we also provide a detailed comparison with Wang’s algorithm on the efficiency analysis and experimental evaluation which shows that the proposed algorithm is more practical for real-world applications.