【摘要】：隨著云計算的快速普及和廣泛應用,如何安全高效的將繁重的計算任務外包給云服務器已經(jīng)越來越受到人們的關注,尤其是那些計算資源有限的用戶。本文中,我們探討的是云計算中大型線性規(guī)劃的安全外包問題。線性規(guī)劃(LP)已經(jīng)在科學領域的各種場景中得到了廣泛的應用,比如,網(wǎng)絡流問題、數(shù)據(jù)包路由、投資組合優(yōu)化和財務數(shù)據(jù)管理等方面。對資源有限的用戶來,求解大型的線性規(guī)劃問題是一筆非常大的計算開銷。因此,研究一種能夠安全高效的大型線性規(guī)劃問題的外包方案非常必要。本文主要有以下幾個方面的工作:1.研究了現(xiàn)有的線性規(guī)劃問題的外包方案,重點研究了基于轉換方法的安全外包方案,總結了現(xiàn)有方案的不足之處。2.在完全惡意模型下,我們首次利用稀疏矩陣技術提出了一種大型線性規(guī)劃的外包算法。該算法能夠適用于任何類型的線性規(guī)劃問題,包括有可行解、無可行解和無界等三種情況。與目前最優(yōu)的算法相比(O(nρ),2ρ≤3),我們所提出的算法只需要復雜度為O(n2)的計算開銷。3.對上述三種情況,提出了完整的驗證算法,它使得客戶能夠在計算復雜度為O(n)的情況下,以100%(最優(yōu))的概率發(fā)現(xiàn)云服務器的作弊行為。證明了方案在一次一密的前提下是安全的。對方案進行了效率分析和仿真實驗,與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