安全高效的大矩陣行列式計算云外包協(xié)議

任曉霞，黃宏宇

REN Xiaoxia1,HUANG Hongyu2

1.重慶醫(yī)科大學(xué)附屬第一醫(yī)院 信息中心，重慶 400000

2.重慶大學(xué) 計算機學(xué)院，重慶 400044

1.Information Center,The First Affiliated Hospital of Chongqing Medical University,Chongqing 400000,China

2.College of Computer Science,Chongqing University,Chongqing 400044,China

1 引言

云計算已經(jīng)成為當(dāng)前IT產(chǎn)業(yè)界的熱門研究領(lǐng)域并且吸引了大量學(xué)者的目光。云計算存在的經(jīng)濟意義是將大量的計算資源，存儲資源，軟件資源鏈接在一起，形成規(guī)模經(jīng)濟效應(yīng)。一些計算能力薄弱或者計算資源不足的客戶端都可以將自己的計算任務(wù)發(fā)送給云服務(wù)端或計算能力相對較強的計算節(jié)點進行計算，這種計算架構(gòu)比客戶自己購買和維護一個運算設(shè)備更能充分利用CPU的運算空閑，提高運算設(shè)備的利用率，從而降低設(shè)備的成本[1-2]。因此，云計算被認為是IT產(chǎn)業(yè)未來一個重要的產(chǎn)業(yè)增長點。

盡管云計算看上去是充滿希望的發(fā)展領(lǐng)域，但是它的發(fā)展依賴于許多重要工程技術(shù)問題的有效解決，安全問題便是首當(dāng)其沖需要考慮的。根據(jù)云計算安全聯(lián)盟和IDC（互聯(lián)網(wǎng)數(shù)據(jù)中心）的調(diào)查，超過50%的企業(yè)認為安全和隱私問題是他們尚未使用云計算服務(wù)的主要原因。因此，密碼學(xué)和安全研究團體不約而同地將研究的目光和重心轉(zhuǎn)向了云安全的研究。密碼學(xué)的研究由此轉(zhuǎn)向了同態(tài)加密[3]，見圖1。

圖1 密碼學(xué)新的發(fā)展

由于目前提出的同態(tài)加密方案效率比較低，距離實際的應(yīng)用層面還有很長的路要走。在解決實際工程和科學(xué)計算工程中，計算安全學(xué)家提出了許多新技術(shù)來實現(xiàn)在計算外包中支持對密文進行可控的、有意義的以及高效操作的加密算法。例如Atallah等人在文獻[4]中通過使用多種有效的技術(shù)手段來偽裝掩蓋原問題來實現(xiàn)外包數(shù)據(jù)的私密性，實現(xiàn)了關(guān)于安全外包許多科學(xué)計算問題的研究；但文獻中方法存在兩個方面的缺陷：一是協(xié)議的效率沒有被仔細討論，二是返回的計算結(jié)果沒有得到正確性的驗證。最近，Wang等人[5-6]提出了一個安全外包線性規(guī)劃運算的協(xié)議和一個安全外包求解線性方程組的協(xié)議，這兩個協(xié)議效率相當(dāng)高并且能夠立即在現(xiàn)實中部署使用，他們所提出的架構(gòu)有著很強的現(xiàn)實指導(dǎo)意義；Atallah等人在文[7-8]中提出了一個安全外包序列比較的協(xié)議和一個安全代數(shù)計算協(xié)議；但是，兩個協(xié)議的共同缺陷是：都需要效率不高的同態(tài)加密算法或者不經(jīng)意傳送協(xié)議[11]，使得協(xié)議對大規(guī)模運算問題效率很低。

大矩陣行列式計算是一個很基礎(chǔ)的科學(xué)計算問題，在工程和科學(xué)上有著大量的應(yīng)用。例如，利用矩陣行列式值和Cramer法則可以實現(xiàn)對線性方程組的求解。此外，行列式計算在數(shù)學(xué)物理分析[9]，拉格朗日插值分析[10]等領(lǐng)域有著廣泛的用途。

針對此類科學(xué)計算問題，本文構(gòu)建了一個關(guān)于大矩陣行列式計算外包的協(xié)議，此協(xié)議可以使得計算能力薄弱的客戶端將大矩陣求行列式值的計算外包給計算能力強大的云計算端服務(wù)器，并且實現(xiàn)正確性、安全性以及高效性的設(shè)計目標(biāo)。

2 相關(guān)模型、設(shè)計目標(biāo)以及外包協(xié)議的框架描述

圖2 安全行列式計算外包系統(tǒng)模型

系統(tǒng)模型：本文研究的整體系統(tǒng)模型如圖2所示，其中Determinant Computation（DC）代表行列式計算。客戶端在將計算外包之前，為了保護輸入私密性，先利用密鑰K將原始的計算問題DC，加密成一個新的計算問題DCK；隨后，客戶端將DCK傳輸給云服務(wù)端進行運算；云服務(wù)端接收到新的計算問題DCK計算出相應(yīng)的運算結(jié)果；云服務(wù)端將DCK的結(jié)果傳送給客戶端，客戶端利用密鑰K解密從云服務(wù)端收到的結(jié)果，得到原始計算問題DC的結(jié)果。這樣一個安全外包計算DC行列式值的流程就完成了。

威脅模型：本計算模型所面臨的安全威脅主要來自于云服務(wù)端。本文假設(shè)云服務(wù)端是半誠實的（semi-honest）。完整定義如下：

定義1（半誠實模型[11]）云服務(wù)器總會忠實地執(zhí)行協(xié)議，但是會記錄所有信息，用以推導(dǎo)客戶端的敏感信息。

這個安全模型考慮了如下兩種安全威脅：（1）云服務(wù)器端會分析客戶端發(fā)送的加密數(shù)據(jù)以及返回給客戶端的運算結(jié)果來獲取客戶端的敏感信息；（2）云服務(wù)器端被第三方入侵而導(dǎo)致內(nèi)部信息的泄露。針對這兩種威脅，本文所設(shè)計的協(xié)議可以實現(xiàn)在一個半誠實的云服務(wù)器下安全運行。

設(shè)計目標(biāo)：本協(xié)議需要現(xiàn)實如下三個目標(biāo)：

（1）正確性

如果客戶端和云服務(wù)端都按照協(xié)議運行，則云服務(wù)端能夠返回給客戶端一個正確的計算結(jié)果。

（2）輸入/輸出私密性

①輸入私密性：云服務(wù)器不能從加密后的DCK獲得原始的計算問題DC；②輸出私密性：云服務(wù)器不能從DCK的計算結(jié)果中得到DC問題的運算結(jié)果。

（3）高效性

①客戶端本地的總運算量要明顯少于自己運行DC的運算量；②云服務(wù)端計算DCK的運算量要和計算原問題DC的運算量盡量地保持一樣。

協(xié)議架構(gòu)：根據(jù)本文提出的系統(tǒng)模型可以得出，一個安全外包DC的協(xié)議應(yīng)包含四個子算法：（1）密鑰產(chǎn)生算法KeyGen；（2）客戶端 DC加密算法DCEnc；（3）云服務(wù)器端運算DCK的算法DCSolve；（4）客戶端解密算法DCDec。一旦明確了協(xié)議的基本架構(gòu)，下面只需要在協(xié)議構(gòu)建中將各個子算法一一實現(xiàn)即可。

3 協(xié)議構(gòu)建

置換函數(shù)在群論[12]和組合論[13]中被廣泛地研究，利用柯西的兩行表示法，一個置換函數(shù)可以表示成：

本文利用一個置換函數(shù) π(i)=pi，i=1，2，…，n表示式（1）。同時，利用sign(π)來表示置換函數(shù)π的奇偶性：如果π是偶置換函數(shù)則sign(π)=-1；如果π是奇置換函數(shù)則sign(π)=1。置換函數(shù)的奇偶性的詳細定義，參見文獻[12]?？肆_內(nèi)克函數(shù)定義為：

對于一個矩陣 X∈?n×n，使用 X(i，j)，xi，j，或者是xij來表示矩陣X中第i行第 j列的元素，det(X)表示矩陣X的行列式值。

考慮一個非奇異的矩陣 X∈?n×n，客戶端想要將計算det(X)外包給一個半誠實的云服務(wù)器端。協(xié)議的每個子算法依次構(gòu)建如下。

（1）密鑰產(chǎn)生算法KeyGen：輸入一個安全參數(shù)λ，客戶端調(diào)用算法1來生成密鑰K：π，{α1，α2，…，αn}。

算法1生成密鑰

輸入：一個安全參數(shù)λ。

輸出：密鑰 K ：π，{α1，α2，…，αn}。

第一步：安全參數(shù)λ規(guī)定密鑰空間Kα。客戶端選擇 n個隨機數(shù){α1，α2，…，αn}←Kα，這里 0?Kα。

第二步：客戶端調(diào)用算法2來產(chǎn)生一個1，2，…，n的隨機置換函數(shù)π。

算法2生成隨機函數(shù)

第一步：設(shè)置π=In，這里In表示恒等置換

第二步：fori=n:2

第三步：設(shè)置 j在1≤j≤i中的隨機數(shù)

第四步：交換π[j]和π[i]

第五步：end for

（2）客戶端DC的加密算法DCEnc(X，K)：輸入一個原始矩陣X和密鑰K，客戶端調(diào)用算法3來加密原來的矩陣X得到加密后矩陣Y。

算法3 DC加密

輸入：原始矩陣 X 和密鑰 K:π，{α1，α2，…，αn}。

輸出：Y=PX。

第二步：客戶端計算Y=PX。根據(jù)定理2，客戶端可以快速地利用公式（4）來計算Y（使用時間復(fù)雜度O(n2)）。

第三步：隨后，加密的矩陣Y將被傳送給云服務(wù)器端進行相關(guān)計算。

證明 由于 P(i，j)= αiδπ(i)，j，不難得出：矩陣 P 總可以通過基本行列式變換為一個新的矩陣P′，使得P′所有對角線元素為 {α1，α2，…，αn}，而其他位置元素全為0。交換的次數(shù)的奇偶性由置換函數(shù)π決定。由引理1可得到交換次數(shù)為偶數(shù)時有 ；交換次數(shù)為奇數(shù)時有 。綜上所述容易得到，證畢。

定理2 在算法3中，P(i，j)= αiδπ(i)，j，則矩陣 Y 滿足

證明 矩陣X被表示為：

因為Y=αiX(π(i)，j)，可以得到：

公式（6）可以進一步簡寫為

Y(i，j)=PX= αiX(π(i)，j)

（3）云服務(wù)器端運算DCK的算法DCSolve(Y)：輸入一個加密后的矩陣Y，云服務(wù)端調(diào)用算法4得到矩陣Y的行列式值DY。

算法4DCK計算

輸入：Y。

輸出：DY。

第一步：從客戶端接收到密鑰后的矩陣Y，云服務(wù)器端調(diào)用任何存在的算法計算Y的行列式值DY，即DY=det(Y)。

第二步：云服務(wù)器返回DY給客戶端。

（4）客戶端解密算法DCDec(DY，K)：輸入返回的運算結(jié)果DY和密鑰K，客戶端調(diào)用算法5便得到原始矩陣X的行列式值DX。

算法5 DC解密

輸入：密鑰 K:π，{α1，α2，…，αn}和 DY。

輸出：DX。

第一步：根據(jù)密鑰 π，{α1，α2，…，αn} ，客戶端計算。

第二步：從云服務(wù)器端接收到DY。客戶端計算DX=DY/DP?？蛻舳吮愕玫皆季仃嘪的行列式值DX。

根據(jù)第一章中的系統(tǒng)模型要求，一個完整的協(xié)議已經(jīng)構(gòu)建完成，下面需要分析本協(xié)議是否可以達到正確性、輸入/輸出私密性和高效性的目標(biāo)。

4 協(xié)議分析

4.1 正確性分析

定理3本文的協(xié)議滿足正確性。

證明 在此只需要證明如果客戶端和云服務(wù)器端都誠實地執(zhí)行了本文的協(xié)議，則DX總是原始矩陣X的行列式值。因為Y=PX，所以det(Y)=det(P)det(X)，即DY=det(P)DX。進一步由公式（3），便得到DX=DY/DP，這就保證了在DC解密運算中DX總是原始矩陣X的行列式值。

4.2 輸入/輸出私密性分析

輸入私密性：客戶端數(shù)據(jù)在半誠實的云服務(wù)器端所面臨的威脅之一是，云端試圖從加密后的矩陣Y還原出原始的矩陣X。原始的矩陣通過以下2個步驟進行了加密。

步驟1原始矩陣X的每行的元素被隨機的置換，即 T(i，j)=X(π(i)，j)。

步驟2被置換后的矩陣進一步通過乘一個因子來加密，即Y(i，j)=αiT(i，j)。

在步驟1中由于π是隨機產(chǎn)生的置換函數(shù)，所以有一共n!種情況，云端即使得到了矩陣T，利用蠻力搜索法從矩陣T中得到正確的X期望時間是n!/2。當(dāng)n足夠大的時候此方法不可行。在步驟2中T被進一步通過乘以一個因子來加密，如果密鑰空間Kα足夠大，則從Y中還原出T攻擊是很困難的。進一步考慮到協(xié)議中對于每一個外包的DC實例，密鑰都會重新產(chǎn)生一次，如果云服務(wù)器端沒有密鑰K，從加密后的矩陣Y還原出原始的矩陣X是非常困難的。因此，輸入私密性得到保證。

輸出私密性：客戶端數(shù)據(jù)在半誠實的云服務(wù)器端所面臨的另外一個威脅是，云端試圖從運算結(jié)果DY中去還原出DX。由于DX=DY/DP，由公式（3），，如果選取適當(dāng)?shù)拿艽a空間 Kα，可以使得DP的取值范圍非常大。在這種情況下，考慮每次加密DP的取值會變化，DY中去還原出DX也是困難的。因此，輸出私密性得到保證。

5 效率評估

5.1 理論分析

客戶端的計算量包含：密鑰產(chǎn)生，DC的加密，DCK的解密算法三部分，分別對應(yīng)于KeyGen，DCEnc和DCDec算法；而云服務(wù)器端的計算量僅由運行DCSolve產(chǎn)生。實驗假設(shè)云服務(wù)器端采用了最為常見的矩陣LU分解法[14]來計算行列式值，則DCSolve運行的時間復(fù)雜度為O(n3)。表1總結(jié)了各個算法理論上的時間復(fù)雜度。由表1可知，客戶端總的時間復(fù)雜度為O(n2)，而云服務(wù)器端為O(n3)。根據(jù)計算復(fù)雜性中的大O符號的定義[15]，可以得到當(dāng)問題規(guī)模n足夠大的時候，客戶端的運算量會遠遠小于云服務(wù)器端的運算量。

表1 協(xié)議的理論開銷

5.2 實驗結(jié)果

理論分析已經(jīng)證明，協(xié)議能夠節(jié)省客戶端的運算量。本節(jié)通過實驗來評估協(xié)議的實際效率。實驗中將客戶端和云服務(wù)器端部署在同一個工作站上來測量它們的運行時間，這樣客戶端和云服務(wù)器端的計算量可以通過時間的比例來客觀地反應(yīng)（參見下一段客戶端加速比的定義），如果將客戶端和云服務(wù)器端部署在兩個不同的服務(wù)器上，則客戶端加速比將變得不穩(wěn)定，取決于兩個服務(wù)器的運算速度的差距。因此，實驗采用一個服務(wù)器的實驗?zāi)Ｊ?。實驗中，客戶端和云服?wù)器計算都是在同一個工作站上執(zhí)行，這個工作站的配置為：英特爾（R）賽揚1.8 GHz的CPU，1 GB RAM。實驗將忽略掉客戶端和云服務(wù)器端的通信延遲，因為本實驗中計算時間占整個運行時間的主要部分。

實驗的目的是計算外包后客戶端的性能增益。本協(xié)議可行的前提條件是以下公式滿足：

換而言之，客戶端在運行密鑰生成，DC加密，以及DC解密所花費的總時間要比自己去解決原始的DC計算問題本身所耗費的時間要少。根據(jù)表2中參數(shù)的定義，不等式（7）所闡述的意義，可以用toriginal/tclient來測定，即本地計算時間和外包計算時間的比值。此比值定義為客戶端的加速比，這個值理論上應(yīng)該為一個大于1的正數(shù)，表示本協(xié)議獲得了一個很可觀的性能增益。除此之外，在實驗中，云端效率是需要考慮的另外一個指標(biāo)，公式表示為toriginal/tcloud。此指標(biāo)反映處理加密后的計算問題和處理原始問題時間的比值。理想情況下，處理DCK不能增加解決原始DC的時間，理想的云端效率值應(yīng)接近1。

表2 協(xié)議實驗參數(shù)

實驗由Matlab實現(xiàn)，云服務(wù)器端使用的是Matlab所提供的函數(shù)來計算矩陣的行列式值。本質(zhì)上是通過Matlab所提供的接口調(diào)用線性代數(shù)包LAPACK[16]中的函數(shù)。所有的矩陣是隨機產(chǎn)生保證其是非奇異的。實驗中使用 Kα={1，2，…，n}。實驗的數(shù)據(jù)由表3所示。從中可以看出，客戶端的加速比隨著問題的規(guī)模單調(diào)遞增?？蛻舳嗽趎=2500時，能夠獲得約10倍的客戶端加速比?？蛻舳思铀俦群途仃囈?guī)模n的關(guān)系如圖3所示。圖4表示了云端效率和矩陣規(guī)模n的關(guān)系，可以看出云端的效率始終保持在1左右。結(jié)果表明加密矩陣沒有使得對應(yīng)的行列式計算復(fù)雜度變得更高。這是一個非常理想的結(jié)果。

表3 DC外包的實驗數(shù)據(jù)

圖3 客戶端加速比和矩陣維數(shù)的關(guān)系

圖4 云端效率和矩陣維數(shù)的關(guān)系

由實驗得出：當(dāng)問題規(guī)模足夠大時，本文協(xié)議是非常高效的。

6 總結(jié)

本文設(shè)計了一個實現(xiàn)了安全性和高效性的行列式計算的云外包協(xié)議。理論和實驗分析顯示，此協(xié)議同時滿足正確性，輸入/輸出私密性以及高效性。由于行列式的計算是一個在工程以及科學(xué)計算上廣泛應(yīng)用的基本運算，故該協(xié)議可被廣泛使用；另外也可以利用此協(xié)議為基礎(chǔ)構(gòu)建設(shè)計更高層的計算外包協(xié)議，或者為其他的工程和科學(xué)計算問題設(shè)計安全的云外包協(xié)議。

[1]Wang Cong，Ren Kui，Wang Jia.Secure and practical outsourcing of linear programming in cloud computing[J].IEEE Transactions on Cloud Computing，2011，4：10-15.

[2]羅軍舟，金嘉暉，宋愛波，等.云計算：體系結(jié)構(gòu)與關(guān)鍵技術(shù)[J].通信學(xué)報，2011，32（7）：4-21.

[3]Gentry C.A fully homomorphic encryption scheme[D].Proquest，Umi Dissertation Publishing，2011.

[4]Atallah M，Pantazopoulos K，Rice J，et al.Secure outsourcing of scientif i c computations[J].Advances in Computers，2002，54：215-272.

[5]Wang C，Ren K，Wang J.Secure and practical outsourcing of linear programming in cloud computing[C]//INFOCOM，2011 Proceedings.[S.l.]：IEEE，2011，4：820-828.

[6]Wang C，Ren K，Wang J，et al.Harnessing the cloud for securely solving large-scale systems of linear equations[C]//31st International Conference on Distributed Computing Systems（ICDCS）.[S.l.]：IEEE，2011，11：549-558.

[7]Atallah M，Li J.Secure outsourcing of sequence comparsion[J].Int J Inf Secur，2005，4：227-287.

[8]Benjamin D，Atallah M J.Private and cheating-free outsourcing of algebraic computations[C]//Proc of 6th Conf on Privacy，Security，and Trust（PST），2008，12：240-245.

[9]Vein R，Dale P.Determinants and their applications in mathematical physics[M].New York：Spriger-Verlag，1999.

[10]Chui C K，Lai M J.Vandermonde determinant and lagrange interpolation in rs[J].Nonlinear and Convex Analysis，1987，107：23-35.

[11]肖倩，羅守山，陳萍，等.半誠實模型下安全多方排序問題的研究[J].電子學(xué)報，2008（4）：709-714.

[12]赫爾.群論[M].北京：科學(xué)出版社，1981.

[13]布魯?shù)?組合數(shù)學(xué)[M].北京：機械工業(yè)出版社，2012.

[14]王開榮，楊大地.應(yīng)用數(shù)值分析[M].北京：高等教育出版社，2010.

[15]戈德賴希.計算復(fù)雜性[M].北京：人民郵電出版社，2010.

[16]巴克.LAPACK95 users’guide[M].北京：清華大學(xué)出版社，2011.