方陣冪安全外包云計(jì)算

本文格式為Word版，下載可任意編輯——方陣冪安全外包云計(jì)算

方案，在該方案中，用戶對(duì)U1和U2暗藏了模冪運(yùn)算中的底數(shù)和指數(shù)，且假設(shè)U1和U2互不通信，以保證數(shù)據(jù)的隱私性；Chen等[2]針對(duì)模冪運(yùn)算提出一個(gè)新的安好外包方案，與Hohenberger等[1]提出的外包方案不同的是，該算法建立在“單惡意”模型下，即U1和U2中至多有一個(gè)是惡意的；在雙云模型下，Ma等[3]針對(duì)底數(shù)固定指數(shù)變化和底數(shù)變化指數(shù)固定兩種情形的模冪運(yùn)算，分別提出了一個(gè)高效的批量安好外包云計(jì)算協(xié)議。

關(guān)于線性問(wèn)題安好外包協(xié)議的研究，其中，Wang等[4]針對(duì)大規(guī)模的線性方程組求解問(wèn)題，提出了一個(gè)安好可驗(yàn)證的單云模型下的外包協(xié)議；對(duì)于線性規(guī)劃問(wèn)題，Wang等[5]提出了一個(gè)安好可行的單云模型下的外包計(jì)算協(xié)議。

關(guān)于矩陣運(yùn)算安好外包的研究，Lei等[6]提出一個(gè)矩陣求逆運(yùn)算的安好可驗(yàn)證云計(jì)算外包協(xié)議，協(xié)議中利用克羅內(nèi)克（Kronecker）函數(shù)和隨機(jī)置換高明構(gòu)造密鑰矩陣并完成加密，利用蒙特卡羅（MonteCarlo）驗(yàn)證算法驗(yàn)證結(jié)果的正確性，以此將加密和驗(yàn)證結(jié)果的繁雜度均降低到O（n2）；胡杏等[7]利用盲化技術(shù)，為矩陣乘積、矩陣行列式、矩陣求逆分別設(shè)計(jì)了一個(gè)切實(shí)可行的安好可驗(yàn)證云計(jì)算外包協(xié)議。任曉霞等[8]也提出一個(gè)矩陣行列式安好外包協(xié)議，與文獻(xiàn)[7]的方案相比，該方案將待外包的矩陣作為一個(gè)整體加密后外包給云端計(jì)算，而文獻(xiàn)[7]的方案那么先根據(jù)行列式按行（列）開(kāi)展法那么，將待外包的矩陣分成多個(gè)矩陣后分別加密，再將加密后的矩陣外包給云端計(jì)算。

在實(shí)際的科學(xué)研究和工程計(jì)算中，方陣冪均有較廣泛的應(yīng)用，如求解馬爾可夫鏈問(wèn)題[9]、數(shù)值方法求時(shí)滯微分方程近似解問(wèn)題[10]、人口預(yù)料、經(jīng)濟(jì)數(shù)據(jù)分析與預(yù)料等。對(duì)于方陣冪的計(jì)算問(wèn)題，鄧勇[11]和王漢斌[12]均介紹了一些特殊方陣的冪運(yùn)算快速計(jì)算方法，而對(duì)于一般方陣的冪運(yùn)算，尚無(wú)通用的快捷之法，務(wù)必借助于計(jì)算機(jī)來(lái)完成計(jì)算。然而由于方陣冪的計(jì)算繁雜度較高，當(dāng)方陣階數(shù)較大或冪數(shù)較高時(shí)，計(jì)算才能受限的用戶仍不能夠自己完成計(jì)算，或者自己完成此計(jì)算所需要的時(shí)間超出了可采納的范圍，所以，面臨此類方陣冪計(jì)算的用戶務(wù)必借助于計(jì)算才能巨大的云計(jì)算平臺(tái)來(lái)完成相關(guān)計(jì)算。因此為此類云用戶設(shè)計(jì)一個(gè)安好的方陣冪云計(jì)算外包協(xié)議顯得特別必要。

1外包計(jì)算模型

圖1是本文提出的外包云計(jì)算單云模型，模型由云用戶和云服務(wù)端兩個(gè)實(shí)體構(gòu)成。其中：云用戶有大量昂貴的方陣冪計(jì)算任務(wù)需要處理，而云服務(wù)端有海量的計(jì)算資源可供云用戶使用。外包計(jì)算的概括流程為：1）用戶在本地將需要外包的計(jì)算任務(wù)T舉行加密，得到加密后的任務(wù)ET；2）用戶將加密后的任務(wù)ET經(jīng)由網(wǎng)絡(luò)發(fā)送給云服務(wù)端；3）云服務(wù)端接收到用戶發(fā)送的任務(wù)ET后，完成對(duì)任務(wù)ET的處理，得到相應(yīng)的處理結(jié)果ER；4）云服務(wù)端將處理結(jié)果ER返回給用戶；5）用戶接收到云服務(wù)端返回的處理結(jié)果ER后，對(duì)ER舉行解密，得到解密后的結(jié)果R；6）驗(yàn)證R的正確性，若正確那么采納服務(wù)端返回的結(jié)果ER，且原任務(wù)T的正確結(jié)果即為R，否那么拒絕服務(wù)端返回的結(jié)果ER。

正確性

只要用戶和云端均嚴(yán)格按照外包協(xié)議來(lái)工作，那么任務(wù)定能被云端正確處理，用戶最終能夠得到原任務(wù)的正確結(jié)果。

安好性

協(xié)議安好性包含輸入安好和輸出安好兩個(gè)方面。輸入安好是指協(xié)議能夠養(yǎng)護(hù)原任務(wù)的私有性，即云端無(wú)法從接收到的加密后的任務(wù)信息中知曉原任務(wù)的概括內(nèi)容；輸出安好是指云端無(wú)法從加密任務(wù)的處理結(jié)果中獲取原任務(wù)的正確結(jié)果。

可驗(yàn)證性

一個(gè)誠(chéng)信的云端返回的正確結(jié)果確定能通過(guò)用戶的驗(yàn)證，并被用戶采納；云端返回的任何不正確的結(jié)果均不能被用戶驗(yàn)證通過(guò)。

高效性

協(xié)議中用戶總的計(jì)算總量須大大小于用戶自身完成任務(wù)處理時(shí)的計(jì)算總量；同時(shí)，云端處理加密后任務(wù)的工作總量理應(yīng)與處理原任務(wù)的工作量相近，即加密過(guò)程沒(méi)有大幅增加任務(wù)處理的繁雜度。

②對(duì)于每個(gè)隨機(jī)整數(shù)對(duì)（r，c），計(jì)算與之對(duì)應(yīng)的驗(yàn)證元素er，c=A（r，：）AA…Am-2個(gè)A（：，c），即Am中第r行c列元素的值。其中，等式右邊的計(jì)算依次為從左往右依次計(jì)算，概括為A（r，：）依次左乘方陣A，共循環(huán)m-2次，所得結(jié)果再左乘A（：，c）。此計(jì)算由用戶自身完成，因此用戶認(rèn)為此結(jié)果是正確穩(wěn)當(dāng)?shù)?，無(wú)需再驗(yàn)證其正確性。

③對(duì)于l個(gè)不同的e（r，c），由用戶判斷是否均得志er，c=R（r，c）。若均得志，那么采納云端結(jié)果，解密所得R為Am的正確結(jié)果；否那么，拒絕云端返回的結(jié)果。

3.4協(xié)議證明

定義1假設(shè)用戶和云端均嚴(yán)格遵守協(xié)議要求完成相關(guān)計(jì)算任務(wù)，最終用戶定能得到任務(wù)Am的正確結(jié)果，那么稱協(xié)議SMP是一個(gè)正確的方陣冪外包計(jì)算協(xié)議。

定理1單云模型下，協(xié)議SMP是一個(gè)正確的方陣冪外包計(jì)算協(xié)議。

證明如協(xié)議中所述，云端接收的方陣為X=PAP-1，那么云端計(jì)算得到的R′=（X）m=PAmP-1，因此只要云端嚴(yán)格按照協(xié)議要求完成計(jì)算，那么經(jīng)用戶解密后的結(jié)果R=P-1R′P=Am，即為用戶所求。故SMP協(xié)議是一個(gè)正確的方陣冪外包計(jì)算協(xié)議。

定義2假設(shè)云端不能從其已知的信息（包括矩陣X，次數(shù)m和結(jié)果R′）中破譯出原始矩陣A或任務(wù)最終結(jié)果R，那么稱協(xié)議SMP是一個(gè)安好的方陣冪外包計(jì)算協(xié)議。

定理2單云模型下，協(xié)議SMP是一個(gè)安好的方陣冪外包計(jì)算協(xié)議。

證明假設(shè)云服務(wù)端試圖獲取原方陣A的內(nèi)容，那么需要從已知的方陣X中破譯出P或P-1；假設(shè)試圖獲取最終的結(jié)果R，亦需要從R′中破譯出P或P-1。由于隨機(jī)置換π有n！種可能，集合α有（κα）n種可能，因此告成破譯P或P-1的概率小于[n！（κα）n]-1，而外包計(jì)算時(shí)方陣階數(shù)n通常較大，故云服務(wù)端告成獲取原方陣A或最終結(jié)果R的概率幾乎為零。因此，SMP協(xié)議是一個(gè)安好性的方陣冪外包計(jì)算協(xié)議。

定義3假設(shè)用戶能夠切實(shí)采納云端返回的正確結(jié)果，精確識(shí)別云端返回的錯(cuò)誤結(jié)果，并拒絕此錯(cuò)誤結(jié)果，那么稱協(xié)議SMP是一個(gè)可驗(yàn)證的方陣冪外包計(jì)算協(xié)議。

定理3單云模型下，協(xié)議SMP是一個(gè)可驗(yàn)證的方陣冪外包計(jì)算協(xié)議。

證明1）假設(shè)云服務(wù)端返回正確結(jié)果，那么用戶隨機(jī)選取l個(gè)元素舉行驗(yàn)證時(shí)，確定都得志驗(yàn)證條件er，c=R（r，c），因此解密所得結(jié)果R將被用戶采納。

2）無(wú)論云服務(wù)端是為了謀取更多的利益而返回一個(gè)任意的結(jié)果，還是由于發(fā)生故障而返回一個(gè)錯(cuò)誤的結(jié)果，對(duì)于字長(zhǎng)為w位的系統(tǒng)，用戶隨機(jī)選取l個(gè)結(jié)果元素舉行驗(yàn)證時(shí)，此結(jié)果被用戶驗(yàn)證通過(guò)并采納的概率僅為2-wl，而目前64位系統(tǒng)越來(lái)越普及，且參數(shù)l的取值至少為2，因此有（2-wl≤2-128），此概率幾乎為零，即用戶采納一個(gè)錯(cuò)誤結(jié)果的概率幾乎為零。

綜合1）和2）可得，SMP協(xié)議是一個(gè)可驗(yàn)證的方陣冪外包計(jì)算協(xié)議。

定義4與用戶自身完成計(jì)算相比，假設(shè)此協(xié)議能夠大幅降低用戶的計(jì)算繁雜度，同時(shí)，與計(jì)算原任務(wù)Am相比，計(jì)算加密后的任務(wù)Xm的繁雜度沒(méi)有明顯增加，那么稱議SMP是一個(gè)高效的方陣冪外包計(jì)算協(xié)議。

定理4單云模型下，協(xié)議SMP是一個(gè)高效的方陣冪外包計(jì)算協(xié)議。

證明根據(jù)Williams[15]的研究，矩陣乘法運(yùn)算的時(shí)間繁雜度最低能夠達(dá)成O（n2.373）左右，因此對(duì)于方陣冪Am的計(jì)算問(wèn)題，其時(shí)間繁雜度約為O（（m-1）n2.373）。而本文設(shè)計(jì)的SMP協(xié)議中用戶端各個(gè)階段的時(shí)間繁雜度概括為：產(chǎn)生密鑰的時(shí)間繁雜度為O（2n2+ts），其中ts為構(gòu)造隨機(jī)置換和非零隨機(jī)數(shù)集合的線性時(shí)間；加密環(huán)節(jié)的時(shí)間繁雜度為O（n2），解密環(huán)節(jié)的時(shí)間繁雜度為O（n2），驗(yàn)證環(huán)節(jié)的時(shí)間繁雜度為O（l（（m-2）n2+n）+l）；故用戶總的時(shí)間繁雜度為O（（l（m-2）+4）n2+ln+l+ts）。因此，對(duì)于用戶來(lái)說(shuō)，相對(duì)于自身計(jì)算Am，外包方式下切實(shí)降低了用戶總計(jì)算量的數(shù)量級(jí)。同時(shí)，對(duì)于云端來(lái)說(shuō)，計(jì)算Xm與計(jì)算Am的繁雜度均為O（（m-1）n2.373），因而加密過(guò)程沒(méi)有增加問(wèn)題處理的繁雜度。所以SMP協(xié)議是一個(gè)高效的方陣冪外包計(jì)算協(xié)議。

4仿真測(cè)驗(yàn)及結(jié)果分析

4.1測(cè)驗(yàn)背景

為了驗(yàn)證SMP協(xié)議的可行性，并評(píng)估其實(shí)際性能，研究中利用Matlab對(duì)SMP協(xié)議舉行了仿真。仿真主要測(cè)算了協(xié)議方式下用戶和云端各自的時(shí)間消耗，以及用戶自身完成Am計(jì)算時(shí)的時(shí)間消耗。

仿真測(cè)驗(yàn)針對(duì)方陣階數(shù)n固定、次數(shù)m變化，和方陣階數(shù)n變化、次數(shù)m固定這兩種情形分別舉行了仿真。兩種情形下的結(jié)果驗(yàn)證環(huán)節(jié)，參數(shù)l均取值為2，即隨機(jī)選擇2個(gè)校驗(yàn)元素來(lái)校驗(yàn)解密后的結(jié)果。

仿真測(cè)驗(yàn)的測(cè)驗(yàn)環(huán)境為：InterCorei3702.4GHzCPU，4GB內(nèi)存（2.5GB可用）；Windows7（32位）操作系統(tǒng)（Windows經(jīng)典主題），Matlab2022a。

測(cè)驗(yàn)結(jié)果分析：由表1可知，在方陣階數(shù)n固定時(shí)，隨著冪指數(shù)m的增大，外包計(jì)算的加速比也隨之增大；由表2可知，在冪指數(shù)m固定時(shí)，隨著方陣階數(shù)n的增大，外包計(jì)算的加速比也隨之增大。由此可見(jiàn)，方陣階數(shù)越大，冪指數(shù)越高，方陣冪云計(jì)算外包的效果越好。同時(shí)，由表1和表2可知，兩種情形下的效率均趨近于1，這說(shuō)明加密過(guò)程沒(méi)有明顯增加任務(wù)處理的繁雜度。因此，此方陣冪云計(jì)算外包協(xié)議具有較好的性能，達(dá)成了外包的預(yù)期目標(biāo)。

5結(jié)語(yǔ)

本文利用云計(jì)算平臺(tái)，針對(duì)計(jì)算才能有限的對(duì)象（用戶）所面臨的大維數(shù)方陣的高次