張勝霞，田呈亮,2+

1.青島大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院，山東 青島266071

2.中國(guó)科學(xué)院 信息工程研究所，信息安全國(guó)家重點(diǎn)實(shí)驗(yàn)室，北京100093

1 引言

安全外包計(jì)算，作為一個(gè)非常重要的服務(wù)，已經(jīng)變得越來(lái)越流行。資源受限的客戶(hù)端獨(dú)立求解是非常困難且代價(jià)昂貴，云計(jì)算[1-2]對(duì)于資源有限的客戶(hù)端進(jìn)行大規(guī)模的數(shù)據(jù)計(jì)算提供了一個(gè)高效且經(jīng)濟(jì)的服務(wù),因此客戶(hù)端需要將大量的計(jì)算任務(wù)外包給云服務(wù)器[3-5]。安全外包計(jì)算的最終目標(biāo)是使客戶(hù)端的計(jì)算成本最小化，并保持原始數(shù)據(jù)的機(jī)密性和完整性。一般來(lái)說(shuō)，云服務(wù)器并不是完全安全可靠的，如果將包含敏感信息的原始數(shù)據(jù)發(fā)送到云端，將會(huì)危及原始數(shù)據(jù)的完整性。因此，安全外包計(jì)算方法至少應(yīng)該滿(mǎn)足以下要求：（1）正確性，對(duì)于一個(gè)誠(chéng)實(shí)的云服務(wù)器，該算法可以使客戶(hù)端正確地獲得想要的結(jié)果。（2）輸入/輸出隱私性，算法應(yīng)保證計(jì)算任務(wù)的實(shí)際輸入和輸出對(duì)云服務(wù)器是不可見(jiàn)的。（3）可驗(yàn)證性，算法必須確?？蛻?hù)端能夠以不可忽略的概率驗(yàn)證從云服務(wù)器返回的結(jié)果的正確性。（4）高效性，在外包算法中，客戶(hù)端的本地計(jì)算開(kāi)銷(xiāo)應(yīng)該遠(yuǎn)遠(yuǎn)小于其自身對(duì)原始任務(wù)的計(jì)算開(kāi)銷(xiāo)。

矩陣作為一種基本的數(shù)學(xué)對(duì)象，廣泛應(yīng)用于科學(xué)和工程計(jì)算領(lǐng)域。許多不同的實(shí)際問(wèn)題可以歸結(jié)為矩陣計(jì)算問(wèn)題。在物理的每一個(gè)分支，包括經(jīng)典力學(xué)、光學(xué)、電磁學(xué)、量子力學(xué)和量子電動(dòng)力學(xué)，矩陣被用來(lái)研究物理現(xiàn)象，如剛體的運(yùn)動(dòng)[6]。在計(jì)算機(jī)圖形學(xué)中，它們被用來(lái)操作3D 模型并投射到二維平面上。在圖像處理中[7-8]，通過(guò)矩陣操作對(duì)圖像進(jìn)行去除噪聲、增強(qiáng)、復(fù)原、分割、提取特征等處理。在概率論和統(tǒng)計(jì)學(xué)中，隨機(jī)矩陣被用來(lái)描述概率集合，例如，它們被用在谷歌搜索系統(tǒng)中對(duì)頁(yè)面進(jìn)行排序的PageRank 算法中[9]。矩陣在經(jīng)濟(jì)學(xué)中被用來(lái)描述經(jīng)濟(jì)數(shù)據(jù)關(guān)系模型。因此，對(duì)于基本矩陣運(yùn)算的算法，如矩陣乘法計(jì)算（matrix multiplication computation，MMC）、矩陣求逆計(jì)算（matrix inversion computation，MIC）和矩陣行列式計(jì)算（matrix determinant computation，MDC），已成為現(xiàn)代科學(xué)計(jì)算的重要組成部分。從復(fù)雜性的角度來(lái)看，MMC、MIC 和MDC 等基本算法具有相同的時(shí)間復(fù)雜度O(n3)（對(duì)于n×n的矩陣），并且已知最快的算法的漸近時(shí)間復(fù)雜度為O(n2.373)。然而，隨著大數(shù)據(jù)時(shí)代數(shù)據(jù)生成量的指數(shù)增長(zhǎng)，現(xiàn)實(shí)問(wèn)題中需要處理的矩陣往往非常大，通常有數(shù)十萬(wàn)個(gè)條目[10-12]。因此，為矩陣操作設(shè)計(jì)安全、可驗(yàn)證、高效的外包協(xié)議成為資源受限客戶(hù)的迫切需求。

近年來(lái)，由于大規(guī)模矩陣運(yùn)算在各個(gè)領(lǐng)域的廣泛應(yīng)用，許多學(xué)者提出了大量將矩陣相乘[13-15]、矩陣特征多項(xiàng)式[16-17]等不同矩陣操作外包的協(xié)議。

首先，關(guān)于矩陣乘法，在1998 年，Atallah 等人[18]最先提出了MMC 和MIC 的外包方案，他們采用了隨機(jī)置換矩陣來(lái)加密。在2008 年，Benjamin 和Atallah[19]利用同態(tài)加密的性質(zhì)又設(shè)計(jì)了MMC 的外包協(xié)議。在2010 年，Atallah 和Frikken[20]設(shè)計(jì)了一個(gè)基于Shamir秘密共享的矩陣乘法外包協(xié)議，該方案只需要一臺(tái)云服務(wù)器。在他們的協(xié)議中，運(yùn)行的時(shí)間成本為O(t2n2)，其中t是Shamir 秘密共享方案的一個(gè)閾值。換句話(huà)說(shuō)，客戶(hù)端計(jì)算至少需要4t+2 次矩陣乘法，這會(huì)增加客戶(hù)端計(jì)算負(fù)擔(dān)。在2012 年，Mohassel[21]利用多種現(xiàn)有的同態(tài)加密方案設(shè)計(jì)了MMC 的外包算法，并設(shè)計(jì)了一種通用的驗(yàn)證方法。Fiore 等人[22]和Zhang 等人[23]設(shè)計(jì)了公開(kāi)驗(yàn)證的方法，讓第三方來(lái)驗(yàn)證云返回結(jié)果的正確性。最近，Lei 等人[24]提出了一種利用蒙特卡洛驗(yàn)證的方法安全外包MMC 的協(xié)議，該方案采用與文獻(xiàn)[18]相同的隨機(jī)置換矩陣?？蛻?hù)端的計(jì)算時(shí)間是O(n2)，但是原矩陣的零元素的數(shù)目會(huì)暴露給云服務(wù)器。

其次，關(guān)于安全外包MIC 的協(xié)議，Lei等人[25]利用與外包矩陣乘法方案[20]相同的加密方法來(lái)設(shè)計(jì)MIC的協(xié)議。這樣，原始矩陣的每個(gè)元素的位置都被隨機(jī)地重新排列，并進(jìn)一步受到多個(gè)隨機(jī)值的保護(hù)。但是，原矩陣的零元素的數(shù)目同樣會(huì)暴露給云服務(wù)器。

最后，行列式計(jì)算在科學(xué)和工程領(lǐng)域有著極其廣泛的應(yīng)用。Lei 等人[26]通過(guò)LU（lower-upper）分解給出了一個(gè)方案，作者通過(guò)添加零矩陣塊來(lái)保護(hù)零元素的數(shù)目。雖然零元素的數(shù)目得到了保護(hù)，但是原矩陣的維數(shù)從n增加到了n+m，其中m×n是零矩陣塊的維數(shù)，這樣客戶(hù)端本地的計(jì)算量會(huì)變大。

本文針對(duì)上述保護(hù)輸入矩陣中零元素?cái)?shù)目的問(wèn)題，提出了一種新穎的加密方法。更具體地說(shuō)，本文的協(xié)議通過(guò)使用幺模矩陣來(lái)保護(hù)零元素的數(shù)目，同時(shí)維護(hù)數(shù)據(jù)的輸入輸出隱私，實(shí)現(xiàn)結(jié)果的可驗(yàn)證性。此外，本地端的計(jì)算開(kāi)銷(xiāo)得到了很大的節(jié)省，就復(fù)雜度而言，客戶(hù)端的計(jì)算開(kāi)銷(xiāo)從O(n3) 降低到了O(n2)。本文所提出的幺模矩陣的加密方法有很廣泛的適用性，除了本文所討論的MMC、MIC 和MDC 加密外，還可以應(yīng)用到外包其他矩陣操作中。

2 問(wèn)題描述

2.1 系統(tǒng)模型

如圖1 所示，安全外包計(jì)算模型包括兩個(gè)實(shí)體：資源受限的客戶(hù)端和有著強(qiáng)大計(jì)算資源和特殊軟件的云服務(wù)器?？蛻?hù)端想要通過(guò)外包給云端進(jìn)行大規(guī)模的矩陣運(yùn)算，為了保護(hù)輸入隱私，首先必須使用密鑰加密原始矩陣。然后，把加密后的矩陣發(fā)送給云。云通過(guò)調(diào)用大量的資源完成計(jì)算后，將計(jì)算結(jié)果返回給客戶(hù)端。客戶(hù)端一旦收到返回的結(jié)果，將會(huì)使用密鑰解密。同時(shí)，客戶(hù)端必須檢查結(jié)果是否正確。如果是，則接受；否則，拒絕。

2.2 安全性定義

安全外包算法需要滿(mǎn)足以下四個(gè)要求：

（1）正確性：只要云服務(wù)器是誠(chéng)實(shí)的，客戶(hù)端就會(huì)收到一個(gè)有效的輸出，通過(guò)解密和驗(yàn)證，得到正確的結(jié)果。

Fig.1 System model圖1 系統(tǒng)模型

（2）輸入輸出隱私性：算法需要隱藏原始數(shù)據(jù)的隱私信息。一方面，云不能獲得任何原始數(shù)據(jù)的隱私信息；另一方面，正確的結(jié)果對(duì)云也是保密的。

（3）可驗(yàn)證性：客戶(hù)端必須成功驗(yàn)證云服務(wù)的正確結(jié)果，準(zhǔn)確檢測(cè)錯(cuò)誤結(jié)果。

（4）高效性：客戶(hù)端外包的計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)小于其不外包時(shí)在本地的計(jì)算時(shí)間。

3 預(yù)備知識(shí)

3.1 置換映射

置換[27]在群理論和組合學(xué)中有著廣泛的應(yīng)用。置換映射是有限集上的雙射，可寫(xiě)成如下：

其中，ai是一個(gè)從1到n的整數(shù)，且ai≠aj,i,j=1,2,…,n。置換映射可以寫(xiě)成輪換和對(duì)換兩種形式。根據(jù)對(duì)換的數(shù)目，置換分為奇置換和偶置換。給定一個(gè)置換Π，sgn(Π)定義為：

3.2 置換矩陣

給定一個(gè)有限集S={1,2,…,n}和一個(gè)置換映射Π，所產(chǎn)生的置換矩陣[28]P為，其中αi為隨機(jī)數(shù)，Kronecker delta 函數(shù)δx,y被定義為：

置換矩陣P的行列式為：

注：當(dāng)置換矩陣P為時(shí)，det(P)=sgn(Π)=±1。

3.3 幺模矩陣

定義 一個(gè)n×n的矩陣U是幺模矩陣[29]當(dāng)且僅當(dāng)且其行列式的絕對(duì)值模q同余1，表示為|det(U)|=1 modq。

幺模矩陣的一個(gè)簡(jiǎn)單性質(zhì)[30]是，一個(gè)幺模矩陣的逆也是幺模矩陣。本文中幺模矩陣U的結(jié)構(gòu)為：

其中，對(duì)角位置上的(u1,u2,…,ut-1)是一系列2×2 的幺模矩陣。當(dāng)n是偶數(shù)，ut也是2×2 的幺模矩陣；當(dāng)n是奇數(shù)，ut是一個(gè)3×3 的幺模矩陣。本文設(shè)計(jì)的協(xié)議中，ut的行列式均為1，在預(yù)處理階段，利用擴(kuò)展的歐幾里德算法快速地生成了這些幺模矩陣ut。

3.4 相關(guān)符號(hào)

本文所提到的縮寫(xiě)形式的定義如表1 所示。

Table 1 Definition of abbreviation表1 縮寫(xiě)定義

4 外包矩陣操作的算法

4.1 計(jì)算任務(wù)描述及基本思想

給定一個(gè)矩陣，客戶(hù)想要計(jì)算行列式、逆陣和與另一個(gè)矩陣相乘。解決這些問(wèn)題的經(jīng)典方法是用高斯消去法、凱萊-哈密頓法等[31]。這些算法一般都需要O(n3)的時(shí)間復(fù)雜度。由于密碼應(yīng)用中涉及的維度通常非常大，資源有限的客戶(hù)很難進(jìn)行如此昂貴的操作。在這種情況下，客戶(hù)端可以通過(guò)安全外包計(jì)算來(lái)完成這一任務(wù)。

一般來(lái)說(shuō)，如果對(duì)于兩個(gè)n×n的矩陣相乘，其復(fù)雜度為O(n3)，但是如果其中有一個(gè)是稀疏矩陣，那么復(fù)雜度為O(n2)。基于這種啟發(fā)，本文通過(guò)引入置換矩陣和幺模矩陣來(lái)加密原始矩陣。任何一個(gè)n×n的矩陣和一個(gè)n×n置換矩陣相乘復(fù)雜度為O(n2)，同樣和一個(gè)n×n的幺模矩陣相乘復(fù)雜度仍然為O(n2)。利用這一特性，實(shí)現(xiàn)對(duì)原始矩陣的加密。然而，對(duì)于安全外包協(xié)議來(lái)說(shuō)，矩陣中零元素的位置和數(shù)目是非常重要的。如果兩者都不受保護(hù)，云可能會(huì)獲取大量的敏感信息，進(jìn)而通過(guò)自身強(qiáng)大的資源獲得正確的結(jié)果。

通過(guò)對(duì)輸入矩陣乘隨機(jī)置換矩陣，每個(gè)元素的位置將會(huì)被隨機(jī)打亂。換句話(huà)說(shuō)，零元素的位置也被打亂。然而，零元素的數(shù)目仍然保持不變。因此，進(jìn)一步通過(guò)乘隨機(jī)幺模矩陣來(lái)改變零的數(shù)目，同時(shí)仍然保持一定的高效性。密鑰是隨機(jī)置換矩陣和幺模矩陣。密鑰幺模矩陣的一般結(jié)構(gòu)如式（1）所示。

4.2 安全外包矩陣相乘（MMC）的算法

給定兩個(gè)矩陣X,，外包矩陣相乘的算法包含以下5 個(gè)步驟：

（1）密鑰生成

①客戶(hù)端隨機(jī)地生成3個(gè)幺模矩陣U1、U2和U3。

②客戶(hù)端生成3 個(gè)隨機(jī)置換矩陣P1、P2和P3，,k=1,2,3，Πk是一個(gè)隨機(jī)置換。

（2）加密

①客戶(hù)端使用隨機(jī)置換矩陣，首先計(jì)算X′和Y′。

②客戶(hù)端使用密鑰幺模矩陣，然后計(jì)算X″和Y″。

客戶(hù)端隨機(jī)地發(fā)送X″和Y″給云服務(wù)。

（3）云計(jì)算

當(dāng)云接收到加密后的矩陣X″ 和Y″ 時(shí)，計(jì)算Z″=X″Y″，并將結(jié)果Z″返回給客戶(hù)端。

（4）解密

當(dāng)客戶(hù)端接收到云返回的結(jié)果Z″，客戶(hù)端進(jìn)行解密：

則Z是X和Y相乘的結(jié)果。

（5）結(jié)果驗(yàn)證

客戶(hù)端對(duì)于解密后的結(jié)果Z進(jìn)行驗(yàn)證，通過(guò)計(jì)算P=X×(Y×r)-Z×r，r是一個(gè)隨機(jī)0-1 列向量，任意非零向量P意味著驗(yàn)證失敗。

4.3 安全外包矩陣逆陣（MIC）的算法

（1）密鑰生成

①客戶(hù)端生成兩個(gè)幺模矩陣U1和U2。

②客戶(hù)端生成兩個(gè)隨機(jī)置換矩陣P1和P2，,k=1,2,3，Πk是一個(gè)隨機(jī)置換。

（2）加密

①客戶(hù)端使用隨機(jī)置換矩陣，首先計(jì)算X′。

②客戶(hù)端使用幺模矩陣，計(jì)算X″。

客戶(hù)端發(fā)送X″給云服務(wù)端。

（3）云計(jì)算

當(dāng)云接收到加密后的矩陣X″時(shí)，計(jì)算其逆矩陣Z″=(X″)-1，并將其返回給客戶(hù)端。

（4）解密

當(dāng)客戶(hù)端收到來(lái)自云端的Z″時(shí)，進(jìn)行解密：

則Z為原始矩陣X的逆矩陣。

（5）結(jié)果驗(yàn)證

客戶(hù)端對(duì)解密后的矩陣進(jìn)行驗(yàn)證，通過(guò)計(jì)算P=X×(Z×r)-Ι×r，r是一個(gè)隨機(jī)0-1 列向量。I是一個(gè)單位矩陣。任何非零向量P意味著驗(yàn)證失敗。

4.4 安全外包矩陣行列式（MDC）的算法

（1）密鑰生成

①客戶(hù)端生成4 個(gè)幺模矩陣U1、U2、U3和U4。

②客戶(hù)端生成4 個(gè)隨機(jī)置換矩陣：

其中，Πk是隨機(jī)置換，αi、βi、γi和δi是隨機(jī)數(shù)。

（2）加密

（3）云計(jì)算

（4）結(jié)果驗(yàn)證和解密

如果等式成立，視等式右邊或者左邊的結(jié)果為正確結(jié)果。否則，客戶(hù)端輸出“⊥”。

5 安全性分析

定理1在單個(gè)云服務(wù)器模型中，安全外包MMC協(xié)議是正確的、安全的和可驗(yàn)證的。

證明（1）MMC 協(xié)議是正確的。

如果云是誠(chéng)實(shí)的，那么客戶(hù)端可以成功解密收到的結(jié)果Z″并且得到的結(jié)果Z總是正確的。值得一提的是X″和Y″由給出。誠(chéng)實(shí)的云在收到客戶(hù)端發(fā)送的X″ 和Y″ 時(shí)會(huì)計(jì)算Z″=X″Y″。然而：

（2）MMC 協(xié)議是安全的。

MMC 協(xié)議可以保護(hù)輸入隱私，因?yàn)樵撇荒軓募用芎蟮木仃嘪″和Y″中獲得原始矩陣的任何信息。原始矩陣X（Y）的加密分為兩個(gè)階段。

階段1 原始矩陣X盲化成X′ 乘以置換矩陣，。

階段2 矩陣X′盲化成X″乘以幺模矩陣，X″=。

①在階段1 中，矩陣X中每個(gè)元素的位置在隨機(jī)置換矩陣的作用下重新排列了。如果惡意的云想從X′中恢復(fù)X需要猜中2n!種情況的排列。

②在階段2 中，由于階段1 僅盲化了零元素的位置，因此這一步需要盲化零元素的數(shù)目。通過(guò)在兩邊乘幺模矩陣，X″ 和X的零元素的數(shù)目會(huì)隨之改變，有可能增加也有可能減少。這樣，即使是擁有強(qiáng)大的計(jì)算能力的惡意的云也無(wú)法再獲得它的數(shù)目，因?yàn)樵诰仃嘪″中零元素的分布沒(méi)有任何規(guī)律。

根據(jù)上面的分析，如果沒(méi)有每個(gè)階段密鑰，云是無(wú)法從X″中獲得原始輸入矩陣X的任何數(shù)據(jù)。這樣，MMC 協(xié)議被認(rèn)為實(shí)現(xiàn)了安全性，因此輸入隱私得到了保護(hù)。

（3）MMC 協(xié)議是可驗(yàn)證的。

解密后的結(jié)果進(jìn)行第5 步的驗(yàn)證，驗(yàn)證算法重復(fù)l次。在本文的協(xié)議中l(wèi)=50，這個(gè)值是在強(qiáng)抵抗性和高效率之間的一個(gè)閾值。 □

定理2在單個(gè)云服務(wù)器模型中，安全外包MIC協(xié)議是正確的、安全的和可驗(yàn)證的。

證明（1）MIC 協(xié)議是正確的。

如果云是誠(chéng)實(shí)的，那么客戶(hù)端可以成功解密收到結(jié)果Z″并且得到的原始結(jié)果X-1（相當(dāng)于Z-1）總是正確的。值得一提的是X″是由給出。誠(chéng)實(shí)的云會(huì)計(jì)算其逆矩陣。然而，(X″)-1=。把(X″)-1記作Z″?？蛻?hù)端解密通過(guò)計(jì)算，可以立即得到Z-1=X-1。也就是說(shuō)MIC 協(xié)議是正確的。

（2）MIC 協(xié)議是安全的。

MIC 協(xié)議可以保護(hù)輸入隱私，因?yàn)樵撇荒軓募用芎蟮木仃嘪″中得到原始矩陣的任何信息。原始矩陣X的加密分為兩個(gè)階段。

階段1原始矩陣X盲化成X′ 乘以置換矩陣，。

階段2矩陣X′盲化成X″乘以幺模矩陣，X″=。

①在階段1 中，矩陣X′中每個(gè)元素的位置在隨機(jī)置換矩陣的作用下重新排列了。如果惡意的云企圖從X′中恢復(fù)X，需要猜對(duì)2n!種置換。

②在階段2 中，因?yàn)殡A段1 沒(méi)有保護(hù)零元素的數(shù)目，這一步將會(huì)實(shí)現(xiàn)。通過(guò)在兩邊乘幺模矩陣，X″和X的零元素的數(shù)目會(huì)隨之改變，有可能增加也有可能減少。這樣，即使是擁有強(qiáng)大的計(jì)算能力的惡意的云也無(wú)法再獲得它的數(shù)目，因?yàn)樵诰仃嘪″中零元素的分布沒(méi)有任何規(guī)律。

根據(jù)上面的分析，如果沒(méi)有每個(gè)階段密鑰，云是無(wú)法從X″中獲得原始輸入矩陣X的任何信息。這樣，MIC 協(xié)議被認(rèn)為實(shí)現(xiàn)了安全性，因此輸入隱私得到了保護(hù)。

（3）MIC 協(xié)議是可驗(yàn)證的。

解密后的結(jié)果會(huì)進(jìn)行第5 步的驗(yàn)證，驗(yàn)證算法重復(fù)l次。在本文的協(xié)議中l(wèi)=50，這個(gè)值是在強(qiáng)抵抗性和高效率之間的一個(gè)閾值。 □

定理3在單個(gè)云服務(wù)器模型中，安全外包MDC協(xié)議是正確的、安全的和可驗(yàn)證的。

證明（1）MDC 協(xié)議是正確的。

如果云誠(chéng)實(shí)地遵守協(xié)議，則det(X) 可由或者得到，其中和是云返回的結(jié)果。det(P1)、det(P2)、det(P3)和det(P4)可由客戶(hù)端簡(jiǎn)單地計(jì)算出來(lái)。如果云是誠(chéng)實(shí)的，那么在第4 步中的解密過(guò)程總會(huì)得到正確的結(jié)果。因?yàn)?，可得如下關(guān)系：

又根據(jù)det(U1)=det(U2)=det(U3)=det(U4)=1，進(jìn)而可以得到：

這表明解密過(guò)程總是能夠滿(mǎn)足正確的結(jié)果，因此本文的協(xié)議是正確的。

（2）MDC 協(xié)議是安全的。

由于云無(wú)法從密文矩陣X1″和X2″中獲取原始矩陣的任何信息，因此MDC 協(xié)議可以保護(hù)輸入隱私。原始矩陣X分為兩個(gè)階段加密。

階段1原始矩陣X盲化成X′ 乘以置換矩陣，。

階段2矩陣X′盲化成X″乘以幺模矩陣，。

①在階段1，矩陣X中的每一個(gè)元素都在隨機(jī)置換下重新排列。云端若想從中恢復(fù)X，需要猜對(duì)4n!種置換且要猜對(duì)系數(shù)(α1,α2,…,αn),(β1,β2,…,βn),(γ1,γ2,…,γn),(δ1,δ2,…,δn)。

根據(jù)以上分析，如果沒(méi)有每個(gè)階段的密鑰，云端就無(wú)法從X″中恢復(fù)X。MDC 協(xié)議被認(rèn)為是實(shí)現(xiàn)了安全性，因此輸入隱私得到了保護(hù)。

（3）MDC 協(xié)議是可驗(yàn)證的。

6 實(shí)驗(yàn)評(píng)估

在這一章中，對(duì)于安全外包MMC、MIC 和MDC算法提供了理論和實(shí)驗(yàn)分析。在理論方面，針對(duì)算法不同階段的計(jì)算時(shí)間和是否保護(hù)零元素?cái)?shù)目的問(wèn)題，對(duì)Atallah、Lei 和本文的方案進(jìn)行了對(duì)比，如表2所示。表中最后一列表示是否保護(hù)零元素的數(shù)目，可見(jiàn)本文設(shè)計(jì)的3 個(gè)算法都保護(hù)了零元素的數(shù)目，同時(shí)客戶(hù)端本地計(jì)算的時(shí)間復(fù)雜度為O(n2)。而且與其他方案不同的是，本文的MDC 算法的驗(yàn)證時(shí)間只需要O()1 。除此之外，本文設(shè)計(jì)的3 個(gè)協(xié)議都是基于Fq的代數(shù)結(jié)構(gòu)。

Table 2 Comparison of different schemes表2 各方案的比較

對(duì)于所提出的3 個(gè)安全外包算法進(jìn)行了實(shí)驗(yàn)評(píng)估。實(shí)驗(yàn)是在裝有2.70 GHz 英特爾i5 處理器和4 GB內(nèi)存的Ubuntu 系統(tǒng)上進(jìn)行的。本文中選擇參數(shù)q為251，相應(yīng)地記錄了3 個(gè)算法在不同維數(shù)和不同加密階段所需要的計(jì)算時(shí)間，如表3、表4 和表5 所示。隨著矩陣維數(shù)n的增加，客戶(hù)端不外包的計(jì)算時(shí)間toriginal不斷增大，外包計(jì)算的時(shí)間tclient也相應(yīng)地變大。但兩者相比而言，tclient要遠(yuǎn)遠(yuǎn)小于toriginal。也就是說(shuō)外包計(jì)算所節(jié)省的時(shí)間效率隨著矩陣規(guī)模的增大越來(lái)越大。當(dāng)維數(shù)n為2 000 時(shí)，外包MMC 可以獲得9 倍以上的效率。當(dāng)維數(shù)n為1 000 時(shí)，外包MIC 可以獲得20 倍的效率。同樣，當(dāng)n為5 000 時(shí)，外包MDC 可以獲得超過(guò)9 倍的效率。

Table 3 Running time of each stage of protocol MMC in different dimensions表3 協(xié)議MMC 各階段在不同維度下的計(jì)算時(shí)間 s

Table 4 Running time of each stage of protocol MIC in different dimensions表4 協(xié)議MIC 各階段在不同維度下的計(jì)算時(shí)間 s

Table 5 Running time of each stage of protocol MDC in different dimensions表5 協(xié)議MDC 各階段在不同維度下的計(jì)算時(shí)間 s

外包MMC 算法和不外包的時(shí)間比較如圖2 所示。toriginal是不外包MMC 時(shí)的本地計(jì)算時(shí)間，tclient是外包MMC 的計(jì)算時(shí)間。隨著矩陣規(guī)模的增大，兩者的差距越來(lái)越大。外包MMC 所需要的時(shí)間遠(yuǎn)遠(yuǎn)小于不外包所需要的時(shí)間。這說(shuō)明，外包MMC 算法具有高效性。

Fig.2 Comparison between outsourcing MMC and non-outsourcing computing圖2 外包MMC 和不外包計(jì)算的比較

外包MIC 算法和不外包的時(shí)間比較如圖3 所示。toriginal是不外包MIC 時(shí)的本地計(jì)算時(shí)間，tclient是外包MIC 時(shí)的計(jì)算時(shí)間。隨著矩陣規(guī)模的增大，兩者的差距越來(lái)越大。外包MIC 所需要的時(shí)間遠(yuǎn)遠(yuǎn)小于不外包所需要的時(shí)間。這說(shuō)明，外包MIC 算法具有高效性。

外包MDC 算法和不外包的時(shí)間比較如圖4 所示。toriginal是不外包MDC 時(shí)的本地計(jì)算時(shí)間，tclient是外包MDC 時(shí)的計(jì)算時(shí)間。隨著矩陣規(guī)模的增大，兩者的差距越來(lái)越大。外包MDC 所需要的時(shí)間遠(yuǎn)遠(yuǎn)小于不外包所需要的時(shí)間。這說(shuō)明，外包MDC 算法具有高效性。

Fig.3 Comparison between outsourcing MIC and non-outsourcing computing圖3 外包MIC 和不外包計(jì)算的比較

Fig.4 Comparison between outsourcing MDC and non-outsourcing computing圖4 外包MDC 和不外包計(jì)算的比較

圖5 和圖6 中的client speedup 表示客戶(hù)端的加速比，是toriginal和tclient的比值，圖5 和圖6 分別對(duì)外包MMC 和MIC 的client speedup 與Lei等人的client speedup 做了比較。圖5 表明，本文的加密方法在外包MMC 時(shí)客戶(hù)端所獲得的speedup 要略高于Lei 的speedup。圖6 表明，本文外包MIC 所獲得的speedup 與Lei 的speedup 相差較大，說(shuō)明外包MMC和MIC 減少了客戶(hù)端的計(jì)算開(kāi)銷(xiāo)。因此，本文的外包算法具有高效性。

Fig.5 Comparison of client speedup of outsourcing MMC圖5 外包MMC 的客戶(hù)端speedup 的比較

Fig.6 Comparison of client speedup of outsourcing MIC圖6 外包MIC 的客戶(hù)端speedup 的比較

7 結(jié)束語(yǔ)

本文設(shè)計(jì)了一種將矩陣相乘、矩陣求逆和行列式外包給云的算法。通過(guò)在置換矩陣的基礎(chǔ)上引入幺模矩陣的加密方法可以保護(hù)初始矩陣的每個(gè)元素的位置和數(shù)目，達(dá)到了正確性、隱私性、可驗(yàn)證性和高效性的目的。本文的工作留下了一個(gè)有趣的問(wèn)題，其他矩陣運(yùn)算比如矩陣秩的計(jì)算、矩陣分解、矩陣的特征多項(xiàng)式以及特征值，對(duì)于資源有限的客戶(hù)端來(lái)說(shuō)，這些操作同樣也是非常昂貴，因此也可以考慮外包給云服務(wù)器?；谄渌仃囘\(yùn)算，如何設(shè)計(jì)更高效、更安全的協(xié)議，是一個(gè)值得研究的課題。除此之外，在有限域上設(shè)計(jì)一個(gè)可驗(yàn)證的安全外包計(jì)算協(xié)議將是非常有意義的。