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