[發(fā)明專利]一種高效求解大尺度矩陣行列式的可驗(yàn)證外包計算方法、客戶端及云計算系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201910020443.X
• 申請日: 2019-01-09
• 公開（公告）號: CN109684603B
• 公開（公告）日: 2019-09-03
• 發(fā)明（設(shè)計）人: 趙亮;陳澤;王興鳳
• 申請（專利權(quán)）人: 四川大學(xué)
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 成都頂峰專利事務(wù)所(普通合伙) 51224
• 代理人: 何紅信

本發(fā)明涉及云計算技術(shù)領(lǐng)域，公開了一種高效求解大尺度矩陣行列式的可驗(yàn)證外包計算方法、客戶端及云計算系統(tǒng)。通過所提供的新外包計算協(xié)議，可使擁有較少計算資源/計算能力弱的客戶端在面臨求解大尺度矩陣行列式時，可以將整個行列式的計算任務(wù)外包給計算能力強(qiáng)大的云計算服務(wù)器，并提供有給客戶端可靠的驗(yàn)證方法，從而滿足當(dāng)前在隱私性(云側(cè)不可得知明文矩陣的數(shù)據(jù))、正確性(在云側(cè)是半誠實(shí)模型或惡意模型時，依然能夠保證客戶端能夠檢測返回結(jié)果是否正確)、高效性(客戶端計算量遠(yuǎn)小于計算明文矩陣行列式所需的計算量)和可驗(yàn)證性(能夠確定地而非以某個不可忽略的概率得出服務(wù)器所返結(jié)果的正確與否)等方面的要求，便于實(shí)際應(yīng)用和推廣。

技術(shù)領(lǐng)域

本發(fā)明屬于云計算技術(shù)領(lǐng)域，具體涉及一種高效求解大尺度矩陣行列式的可驗(yàn)證外包計算方法、客戶端及云計算系統(tǒng)。

背景技術(shù)

云計算的概念一經(jīng)提出，就受到了廣泛的關(guān)注。云計算將計算分布在大量的分布式計算機(jī)上，而非本地計算機(jī)或遠(yuǎn)程服務(wù)器中。一方面，云計算提供了強(qiáng)大的計算能力，使客戶免去了購買和維護(hù)設(shè)備之苦；另一方面，云可以使用極其廉價的節(jié)點(diǎn)構(gòu)造云，云的通用性使資源利用率大幅提升。然而，隨著云計算的快速發(fā)展，相關(guān)的安全問題成為了一大難題。同態(tài)加密是一種有效的手段，但就目前來看，其效率較低，難以投入到實(shí)際使用中來。

外包計算是云計算中的重要應(yīng)用，通過云計算，客戶端將計算密集型任務(wù)托付給計算能力強(qiáng)大的云。大尺度矩陣行列式(即大規(guī)模矩陣行列式)的計算是一種對計算能力要求很高的計算，其計算復(fù)雜度為Ο(n³)，在矩陣的尺寸n很大時，計算會變得很繁雜，然而它在科研、通訊、工程等領(lǐng)域都是一個經(jīng)常性的問題。外包計算的出現(xiàn)可以幫助客戶快捷且方便地解決該難題。然而，在利用外包計算方式來解決大尺度矩陣行列式計算前，有兩個至關(guān)重要的問題需要解決：(1)客戶端應(yīng)當(dāng)能夠知道自己得到的結(jié)果是否正確。即一方面，硬件的故障或者軟件的漏洞可能導(dǎo)致計算結(jié)果錯誤；另一方面，敵對的或者自私的服務(wù)端可能會有意將錯誤注入到計算中，或者發(fā)送回一個似乎正確的結(jié)果，來減少對計算資源的使用。(2)另一個關(guān)鍵的問題是數(shù)據(jù)的隱私性。即用戶的數(shù)據(jù)可能是敏感且貴重的，但在外包計算過程中，這些數(shù)據(jù)的輸入和結(jié)果的輸出會被對方出于好奇或者有預(yù)謀地獲得。比如一些公司的商業(yè)機(jī)密，或者研究所內(nèi)重要的觀察數(shù)據(jù)，云端可以將這些信息賣給客戶的競爭對手，或者存儲起來以備后用。這些都屬于外包計算的隱私性問題。雖然正確性與隱私性對外包計算至關(guān)重要，隱私對個體和商業(yè)公司來說，更是至關(guān)重要的問題。

基于上面的兩個問題，一個能夠保護(hù)客戶數(shù)據(jù)隱私、可驗(yàn)證結(jié)果和高效率的大尺度矩陣行列式外包計算協(xié)議就顯得尤為重要。目前針對矩陣行列式的外包計算協(xié)議主要有以下幾種。

(1)2014年版協(xié)議，該協(xié)議在2014年由任曉霞等人提出，協(xié)議的威脅模型(其一般可分為兩種：半誠實(shí)模型和惡意模型，目的在于將來自云計算服務(wù)器等的威脅模型化；半誠實(shí)模型——云計算服務(wù)器會忠實(shí)地執(zhí)行協(xié)議，計算客戶的需求，但是它會記錄所有的信息，并以此來推測出客戶的隱私信息；另外，云計算服務(wù)器自身也有被攻擊和竊取信息的可能；惡意模型——可以不遵從協(xié)議的規(guī)定，云計算服務(wù)器甚至可以任意發(fā)送一個值作為計算結(jié)果來節(jié)省自己的計算資源，同時不希望客戶檢測到)是半誠實(shí)模型，協(xié)議利用了置換函數(shù)，對原矩陣進(jìn)行盲化加密(任曉霞，黃宏宇，《安全高效的大矩陣行列式計算云外包協(xié)議.計算機(jī)工程與應(yīng)用》，2014，50(10)，82-86)。所述2014年版協(xié)議的子算法如下：(a)密鑰生成算法KeyGen(1^λ)→(K,P)；(b)問題產(chǎn)生算法(即論文中的加密算法Enc，可以理解為對要外包的問題進(jìn)行保密)ProbGen(X,K,P)→Y；(c)矩陣計算算法DCSol(Y)→det(Y)；(d)解密算法Dec(det(Y))→det(X)。

所述2014年版協(xié)議的實(shí)現(xiàn)過程如下：假設(shè)明文矩陣X∈R^n×n，置換函數(shù)利用柯西的兩行表示法，可以表示為：