云環境下矩陣乘法外包計算方案

聶恒太，王少輝

(1.南京郵電大學 計算機學院，江蘇 南京 210003；2.江蘇省無線傳感網高技術研究重點實驗室，江蘇 南京 210003;3.江蘇省大數據安全與智能處理重點實驗室，江蘇 南京 210023)

1 概 述

云計算作為一種新的計算模式，允許公司、組織和個人從服務提供商租用計算和云存儲資源[1-2]在云服務器完成對本地的計算任務。介于云計算強大的計算能力，計算能力薄弱的客戶端或設備可以外包它們繁重的計算任務和數據(例如，大矩陣乘法或代數計算)給云服務器計算，盡可能減少用戶端計算成本。近年來，外包計算[3-9]受到廣泛關注，已經成為一個熱門的研究課題。

與外包計算迅速發展相對應的是這種新的計算模型帶來的兩個主要安全挑戰。用戶面臨的第一個挑戰是數據隱私。外包計算的輸入和輸出數據通常包含用戶不想暴露在云服務器上的敏感信息，而云服務通常假定不完全可信。因此，需要對原始數據和計算結果采取諸如數據偽裝、問題轉化和加密等安全措施，以防止用戶的信息泄露。第二個挑戰是計算結果的正確性驗證。一般除了軟件錯誤或硬件故障外，云服務器可能不按照外包方案的具體程序執行，比如云服務器直接選擇難以區分的無效結果返回給用戶。所以，用戶必須具備進行結果正確性驗證或者委托第三方驗證機構進行結果正確性驗證的能力。

大矩陣運算[10-13]已被廣泛應用于當前的計算研究、電子應用和3D圖像處理等領域。因此，如何把高復雜度的矩陣相關運算安全外包給云服務器進行計算是外包計算領域的一個重要內容。矩陣相關算法主要包括矩陣乘法、矩陣求逆和線性方程組求解等，已經有了大量的研究成果。

Li Hongwei等[14]在2015年提出了一種可公開驗證的矩陣乘法外包算法，算法中采用了偽隨機函數方法，在得到計算結果的同時提高了算法效率，但是該方案的驗證算法過于復雜，用戶端計算量太大，無法達到實際應用的效果。2013年，Lei Xinyu等[15]提出了一種大規模矩陣求逆的外包計算方案，該方案利用置換矩陣和稀疏矩陣成功地保護了用戶的輸入和輸出隱私，但是用戶在整個算法執行過程中計算負載過高，也無法在實際中使用。2013年，Wang Cong等[16]利用數學中的迭代法設計了一種新型的計算大規模線性方程的方法。但是，初始迭代向量的選擇隨機性太大，具有很大的偶然性，而且用戶要與云端進行多次的交互致使用戶端的時間開銷依然很大，所以很難使用。

2016年，Zhang Jian等[17]提出了一種針對大規模線性方程組的外包方案，通過特殊的置換函數和系數矩陣保護原有矩陣不被竊取，但是同樣存在著用戶端計算負載過高的問題。不管如何設計外包方案，如果用戶端在整個協議執行過程中計算所消耗的時間接近或超過了自己直接解決問題所需的時間，那么這種外包方案是沒有多大意義的。

2016年，Gang Sheng等提出了一種矩陣乘法外包方案MD-VCMatrix[18]，該方案主要側重于驗證效率的改進，未對輸入和輸出信息的隱私性進行保護。文中在MD-VCMatrix方案的基礎上考慮數據隱私保護，提出了一個新的矩陣乘法外包方案，并在執行效率、算法的隱私性保護和可驗證性等方面與其他方案進行了綜合比較。

2 問題描述

2.1 系統模型

如圖1所示，可公開驗證的矩陣乘法計算外包方案由三方協作完成：外包用戶、云服務器和驗證方。外包用戶一般計算或存儲資源受限，將矩陣和向量的乘法運算外包給云服務器。云服務器利用其強大的計算能力執行來自外包用戶的外包計算業務。而驗證方主要驗證云服務器的臨時結果是否正確。如果結果正確，將臨時結果返回給用戶。

圖1 系統模型

該方案包括如下五個子算法：

(1)KeyGen(1λ)→PK：以安全參數λ作為輸入，算法輸出公共參數PK。

(2)ProbGen(M,x)→(BE,VE)：用戶對原始矩陣M和原始向量x進行盲化處理，將盲化結果BE發送給云服務器，驗證數據VE發送給驗證方。

(3)Compute(BE)→(y',v)：云服務器計算得到臨時結果y'和驗證信息v，這兩個信息都會發送給驗證方。

(4)Verify(VE,y',v)→true/false：驗證方接收到數據y'和v，利用VE，驗證方驗證結果的正確性，若正確則將結果發送給用戶，否則提示用戶結果有誤。

(5)Solve(y')→y：用戶接收到驗證方發送的信息y'，計算出矩陣運算的結果M·x。

2.2 攻擊模型

外包系統模型所面臨的安全威脅主要來自于云服務器的惡意行為。一般來說，有兩種常見的外包模型：半誠實模型和惡意模型[19]。在半誠實模型中，云服務器會忠實地執行協議流程，但其還會偵聽并分析協議中傳輸的信息，進而得到諸如用戶的輸入輸出等敏感信息。而在惡意模型中，云服務器是主動攻擊者，其很有可能會因為軟硬件錯誤或者商業利益的誘導等原因故意發送一個難以區分的無效結果給用戶，同時希望惡意行為不被檢測出來。因此，外包協議必須能夠進行結果驗證并具有高可驗證性。文中采用惡意模型即云服務器被假定為惡意的服務器，而驗證方認定為誠實服務器。

設計目標主要包括以下幾點：

(1)隱私性：在執行新方案時，云服務器在協議交互的過程中無法獲取到用戶的輸入和輸出信息。

(2)可驗證性：云服務器的計算結果必須通過驗證方驗證成功，否則不會發送給用戶。錯誤結果可以通過驗證的概率極低，文中方案可驗證概率接近于1。

(3)效率：無論執行效率和內在需求的要求都要盡可能低，以減少客戶端的計算負擔。

2.3 數學定義

定義1(非對稱雙線性對):設G1、G2和GT是階為大素數q的乘法循環群，若滿足以下條件，則稱e:G1×G2→GT是一個非對稱雙線性映射。

(1)雙線性：對于任意的a,b∈Zq,g∈G1和h∈G2,e(ga,hb)=e(g,h)ab。

(2)非退化性：對于任意的g∈G1，若h∈G2，e(g,h)=1，g=1。

(3)可計算性：對于g∈G1,h∈G2，存在有效算法計算得出e(g,h)。

3 新方案設計

新方案的每個子算法依次構建如下：

m=r·M'

x'=A2·x

VKx'=e(ρx',g2)

w=(w1,w2,…,wd)

計算結束后，用戶將M'、w和x'發送給云服務器，而將VKπ′發送給驗證方。

Verify(VKx'，PK，y'，v):驗證方驗證下面等式是否成立:

Solve(y')→y:若用戶接收到驗證方發來的信息y'，則通過以下公式解密出真正的結果y：

4 方案分析

4.1 正確性分析

定理1：如果數據PKM'、VKx′、y'和v被正確計算，那么文中的驗證方案是正確的。

由上面的推導過程可知，文中的驗證方案正確。

定理2:如果協議正確執行，那么用戶計算的y是矩陣乘法運算的正確結果。

證明：根據KenGen，ProbGen和Compute三個階段的算法，可知：

可以得出：

從而有：

因此，只要協議正確執行，計算結果y是矩陣乘法運算的正確結果。

4.2 安全性分析

(1)輸入信息的隱私性。

(2)輸出信息的隱私性。

(3)公開驗證的安全。

4.3 性能分析

文中協議涉及的運算主要包括整數的加減乘運算、雙線性運算和模冪運算。由于整數的加減運算復雜度較低，在計算算法效率方面只考慮乘法運算、雙線性運算和模冪運算。文中用BC表示雙線性運算，EC表示模冪運算，MC表示乘法運算。下面將文中算法與現有算法在執行效率、可驗證概率進行比較，由于云端計算能力強，速度快，只考慮用戶的計算負載。結果如表1所示。

從表1可以看出，文中算法的可驗證概率遠高于Lei Xinyu等和Fu Shaojing等提出算法的可驗證概率，但是效率低于后者；文中算法的效率高于Li Hongwei等提出的算法，而且可驗證概率接近于1。

表1 算法比較

5 結束語

提出了一種可驗證的安全有效的矩陣乘法外包計算方案，在提供高可驗證性的同時，能夠提供運算輸入輸出信息的隱私性保護。然而，由于在方案中考慮到了隱私性保護，在一定程度上增加了外包用戶的算法執行開銷，但這種開銷被控制在可接受的范圍內。與現存方案相比，在執行效率或可驗證概率等方面都有較好的表現。

下一步，將考慮盡量減少用戶的計算量，達到高效和高可驗證概率并存的目的，同時考慮在多服務器上進行運算外包。