云计算中大型线性规划问题的外包方案研究
发布时间：2019-01-24 16:28
【摘要】：随着云计算的快速普及和广泛应用,如何安全高效的将繁重的计算任务外包给云服务器已经越来越受到人们的关注,尤其是那些计算资源有限的用户。本文中,我们探讨的是云计算中大型线性规划的安全外包问题。线性规划(LP)已经在科学领域的各种场景中得到了广泛的应用,比如,网络流问题、数据包路由、投资组合优化和财务数据管理等方面。对资源有限的用户来,求解大型的线性规划问题是一笔非常大的计算开销。因此,研究一种能够安全高效的大型线性规划问题的外包方案非常必要。本文主要有以下几个方面的工作:1.研究了现有的线性规划问题的外包方案,重点研究了基于转换方法的安全外包方案,总结了现有方案的不足之处。2.在完全恶意模型下,我们首次利用稀疏矩阵技术提出了一种大型线性规划的外包算法。该算法能够适用于任何类型的线性规划问题,包括有可行解、无可行解和无界等三种情况。与目前最优的算法相比(O(nρ),2ρ≤3),我们所提出的算法只需要复杂度为O(n2)的计算开销。3.对上述三种情况,提出了完整的验证算法,它使得客户能够在计算复杂度为O(n)的情况下,以100%(最优)的概率发现云服务器的作弊行为。证明了方案在一次一密的前提下是安全的。对方案进行了效率分析和仿真实验,与Wang提出的方案相比,我们的方案是高效且实用的。
[Abstract]:With the rapid popularity and wide application of cloud computing, how to safely and efficiently outsource heavy computing tasks to cloud servers has attracted more and more attention, especially for those users with limited computing resources. In this paper, we discuss the security outsourcing of large scale linear programming in cloud computing. Linear programming (LP) has been widely used in various scenarios in the field of science, such as network flow problem, packet routing, portfolio optimization and financial data management. For users with limited resources, solving large-scale linear programming problems is a huge computational overhead. Therefore, it is necessary to study an outsourcing scheme for large scale linear programming problems. This paper mainly has the following aspects of work: 1. In this paper, the outsourcing scheme of linear programming problem is studied, and the security outsourcing scheme based on transformation method is emphatically studied, and the shortcomings of the existing scheme are summarized. 2. Under the completely malicious model, we propose a large scale linear programming outsourcing algorithm using sparse matrix technique for the first time. The algorithm can be applied to any type of linear programming problems, including feasible solutions, unfeasible solutions and unbounded cases. Compared with (O (n 蟻, 2 蟻 鈮，
本文编号：2414625
[Abstract]:With the rapid popularity and wide application of cloud computing, how to safely and efficiently outsource heavy computing tasks to cloud servers has attracted more and more attention, especially for those users with limited computing resources. In this paper, we discuss the security outsourcing of large scale linear programming in cloud computing. Linear programming (LP) has been widely used in various scenarios in the field of science, such as network flow problem, packet routing, portfolio optimization and financial data management. For users with limited resources, solving large-scale linear programming problems is a huge computational overhead. Therefore, it is necessary to study an outsourcing scheme for large scale linear programming problems. This paper mainly has the following aspects of work: 1. In this paper, the outsourcing scheme of linear programming problem is studied, and the security outsourcing scheme based on transformation method is emphatically studied, and the shortcomings of the existing scheme are summarized. 2. Under the completely malicious model, we propose a large scale linear programming outsourcing algorithm using sparse matrix technique for the first time. The algorithm can be applied to any type of linear programming problems, including feasible solutions, unfeasible solutions and unbounded cases. Compared with (O (n 蟻, 2 蟻 鈮，
本文编号：2414625
本文链接：https://www.wllwen.com/kejilunwen/wltx/2414625.html
