在幺模矩陣加密方法下的安全外包算法*

張勝霞，田呈亮,2+

1.青島大學 計算機科學技術學院，山東 青島266071

2.中國科學院 信息工程研究所，信息安全國家重點實驗室，北京100093

1 引言

安全外包計算，作為一個非常重要的服務，已經變得越來越流行。資源受限的客戶端獨立求解是非常困難且代價昂貴，云計算[1-2]對于資源有限的客戶端進行大規模的數據計算提供了一個高效且經濟的服務,因此客戶端需要將大量的計算任務外包給云服務器[3-5]。安全外包計算的最終目標是使客戶端的計算成本最小化，并保持原始數據的機密性和完整性。一般來說，云服務器并不是完全安全可靠的，如果將包含敏感信息的原始數據發送到云端，將會危及原始數據的完整性。因此，安全外包計算方法至少應該滿足以下要求：（1）正確性，對于一個誠實的云服務器，該算法可以使客戶端正確地獲得想要的結果。（2）輸入/輸出隱私性，算法應保證計算任務的實際輸入和輸出對云服務器是不可見的。（3）可驗證性，算法必須確?？蛻舳四軌蛞圆豢珊雎缘母怕黍炞C從云服務器返回的結果的正確性。（4）高效性，在外包算法中，客戶端的本地計算開銷應該遠遠小于其自身對原始任務的計算開銷。

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

近年來，由于大規模矩陣運算在各個領域的廣泛應用，許多學者提出了大量將矩陣相乘[13-15]、矩陣特征多項式[16-17]等不同矩陣操作外包的協議。

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

其次，關于安全外包MIC 的協議，Lei等人[25]利用與外包矩陣乘法方案[20]相同的加密方法來設計MIC的協議。這樣，原始矩陣的每個元素的位置都被隨機地重新排列，并進一步受到多個隨機值的保護。但是，原矩陣的零元素的數目同樣會暴露給云服務器。

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

本文針對上述保護輸入矩陣中零元素數目的問題，提出了一種新穎的加密方法。更具體地說，本文的協議通過使用幺模矩陣來保護零元素的數目，同時維護數據的輸入輸出隱私，實現結果的可驗證性。此外，本地端的計算開銷得到了很大的節省，就復雜度而言，客戶端的計算開銷從O(n3) 降低到了O(n2)。本文所提出的幺模矩陣的加密方法有很廣泛的適用性，除了本文所討論的MMC、MIC 和MDC 加密外，還可以應用到外包其他矩陣操作中。

2 問題描述

2.1 系統模型

如圖1 所示，安全外包計算模型包括兩個實體：資源受限的客戶端和有著強大計算資源和特殊軟件的云服務器。客戶端想要通過外包給云端進行大規模的矩陣運算，為了保護輸入隱私，首先必須使用密鑰加密原始矩陣。然后，把加密后的矩陣發送給云。云通過調用大量的資源完成計算后，將計算結果返回給客戶端。客戶端一旦收到返回的結果，將會使用密鑰解密。同時，客戶端必須檢查結果是否正確。如果是，則接受；否則，拒絕。

2.2 安全性定義

安全外包算法需要滿足以下四個要求：

（1）正確性：只要云服務器是誠實的，客戶端就會收到一個有效的輸出，通過解密和驗證，得到正確的結果。

Fig.1 System model圖1 系統模型

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

（3）可驗證性：客戶端必須成功驗證云服務的正確結果，準確檢測錯誤結果。

（4）高效性：客戶端外包的計算時間遠遠小于其不外包時在本地的計算時間。

3 預備知識

3.1 置換映射

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

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

3.2 置換矩陣

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

置換矩陣P的行列式為：

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

3.3 幺模矩陣

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

幺模矩陣的一個簡單性質[30]是，一個幺模矩陣的逆也是幺模矩陣。本文中幺模矩陣U的結構為：

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

3.4 相關符號

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

Table 1 Definition of abbreviation表1 縮寫定義

4 外包矩陣操作的算法

4.1 計算任務描述及基本思想

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

一般來說，如果對于兩個n×n的矩陣相乘，其復雜度為O(n3)，但是如果其中有一個是稀疏矩陣，那么復雜度為O(n2)?；谶@種啟發，本文通過引入置換矩陣和幺模矩陣來加密原始矩陣。任何一個n×n的矩陣和一個n×n置換矩陣相乘復雜度為O(n2)，同樣和一個n×n的幺模矩陣相乘復雜度仍然為O(n2)。利用這一特性，實現對原始矩陣的加密。然而，對于安全外包協議來說，矩陣中零元素的位置和數目是非常重要的。如果兩者都不受保護，云可能會獲取大量的敏感信息，進而通過自身強大的資源獲得正確的結果。

通過對輸入矩陣乘隨機置換矩陣，每個元素的位置將會被隨機打亂。換句話說，零元素的位置也被打亂。然而，零元素的數目仍然保持不變。因此，進一步通過乘隨機幺模矩陣來改變零的數目，同時仍然保持一定的高效性。密鑰是隨機置換矩陣和幺模矩陣。密鑰幺模矩陣的一般結構如式（1）所示。

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

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

（1）密鑰生成

①客戶端隨機地生成3個幺模矩陣U1、U2和U3。

②客戶端生成3 個隨機置換矩陣P1、P2和P3，,k=1,2,3，Πk是一個隨機置換。

（2）加密

①客戶端使用隨機置換矩陣，首先計算X′和Y′。

②客戶端使用密鑰幺模矩陣，然后計算X″和Y″。

客戶端隨機地發送X″和Y″給云服務。

（3）云計算

當云接收到加密后的矩陣X″ 和Y″ 時，計算Z″=X″Y″，并將結果Z″返回給客戶端。

（4）解密

當客戶端接收到云返回的結果Z″，客戶端進行解密：

則Z是X和Y相乘的結果。

（5）結果驗證

客戶端對于解密后的結果Z進行驗證，通過計算P=X×(Y×r)-Z×r，r是一個隨機0-1 列向量，任意非零向量P意味著驗證失敗。

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

（1）密鑰生成

①客戶端生成兩個幺模矩陣U1和U2。

②客戶端生成兩個隨機置換矩陣P1和P2，,k=1,2,3，Πk是一個隨機置換。

（2）加密

①客戶端使用隨機置換矩陣，首先計算X′。

②客戶端使用幺模矩陣，計算X″。

客戶端發送X″給云服務端。

（3）云計算

當云接收到加密后的矩陣X″時，計算其逆矩陣Z″=(X″)-1，并將其返回給客戶端。

（4）解密

當客戶端收到來自云端的Z″時，進行解密：

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

（5）結果驗證

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

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

（1）密鑰生成

①客戶端生成4 個幺模矩陣U1、U2、U3和U4。

②客戶端生成4 個隨機置換矩陣：

其中，Πk是隨機置換，αi、βi、γi和δi是隨機數。

（2）加密

（3）云計算

（4）結果驗證和解密

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

5 安全性分析

定理1在單個云服務器模型中，安全外包MMC協議是正確的、安全的和可驗證的。

證明（1）MMC 協議是正確的。

如果云是誠實的，那么客戶端可以成功解密收到的結果Z″并且得到的結果Z總是正確的。值得一提的是X″和Y″由給出。誠實的云在收到客戶端發送的X″ 和Y″ 時會計算Z″=X″Y″。然而：

（2）MMC 協議是安全的。

MMC 協議可以保護輸入隱私，因為云不能從加密后的矩陣X″和Y″中獲得原始矩陣的任何信息。原始矩陣X（Y）的加密分為兩個階段。

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

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

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

②在階段2 中，由于階段1 僅盲化了零元素的位置，因此這一步需要盲化零元素的數目。通過在兩邊乘幺模矩陣，X″ 和X的零元素的數目會隨之改變，有可能增加也有可能減少。這樣，即使是擁有強大的計算能力的惡意的云也無法再獲得它的數目，因為在矩陣X″中零元素的分布沒有任何規律。

根據上面的分析，如果沒有每個階段密鑰，云是無法從X″中獲得原始輸入矩陣X的任何數據。這樣，MMC 協議被認為實現了安全性，因此輸入隱私得到了保護。

（3）MMC 協議是可驗證的。

解密后的結果進行第5 步的驗證，驗證算法重復l次。在本文的協議中l=50，這個值是在強抵抗性和高效率之間的一個閾值。 □

定理2在單個云服務器模型中，安全外包MIC協議是正確的、安全的和可驗證的。

證明（1）MIC 協議是正確的。

如果云是誠實的，那么客戶端可以成功解密收到結果Z″并且得到的原始結果X-1（相當于Z-1）總是正確的。值得一提的是X″是由給出。誠實的云會計算其逆矩陣。然而，(X″)-1=。把(X″)-1記作Z″?？蛻舳私饷芡ㄟ^計算，可以立即得到Z-1=X-1。也就是說MIC 協議是正確的。

（2）MIC 協議是安全的。

MIC 協議可以保護輸入隱私，因為云不能從加密后的矩陣X″中得到原始矩陣的任何信息。原始矩陣X的加密分為兩個階段。

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

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

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

②在階段2 中，因為階段1 沒有保護零元素的數目，這一步將會實現。通過在兩邊乘幺模矩陣，X″和X的零元素的數目會隨之改變，有可能增加也有可能減少。這樣，即使是擁有強大的計算能力的惡意的云也無法再獲得它的數目，因為在矩陣X″中零元素的分布沒有任何規律。

根據上面的分析，如果沒有每個階段密鑰，云是無法從X″中獲得原始輸入矩陣X的任何信息。這樣，MIC 協議被認為實現了安全性，因此輸入隱私得到了保護。

（3）MIC 協議是可驗證的。

解密后的結果會進行第5 步的驗證，驗證算法重復l次。在本文的協議中l=50，這個值是在強抵抗性和高效率之間的一個閾值。 □

定理3在單個云服務器模型中，安全外包MDC協議是正確的、安全的和可驗證的。

證明（1）MDC 協議是正確的。

如果云誠實地遵守協議，則det(X) 可由或者得到，其中和是云返回的結果。det(P1)、det(P2)、det(P3)和det(P4)可由客戶端簡單地計算出來。如果云是誠實的，那么在第4 步中的解密過程總會得到正確的結果。因為，可得如下關系：

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

這表明解密過程總是能夠滿足正確的結果，因此本文的協議是正確的。

（2）MDC 協議是安全的。

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

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

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

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

根據以上分析，如果沒有每個階段的密鑰，云端就無法從X″中恢復X。MDC 協議被認為是實現了安全性，因此輸入隱私得到了保護。

（3）MDC 協議是可驗證的。

6 實驗評估

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

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

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

Table 3 Running time of each stage of protocol MMC in different dimensions表3 協議MMC 各階段在不同維度下的計算時間 s

Table 4 Running time of each stage of protocol MIC in different dimensions表4 協議MIC 各階段在不同維度下的計算時間 s

Table 5 Running time of each stage of protocol MDC in different dimensions表5 協議MDC 各階段在不同維度下的計算時間 s

外包MMC 算法和不外包的時間比較如圖2 所示。toriginal是不外包MMC 時的本地計算時間，tclient是外包MMC 的計算時間。隨著矩陣規模的增大，兩者的差距越來越大。外包MMC 所需要的時間遠遠小于不外包所需要的時間。這說明，外包MMC 算法具有高效性。

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

外包MIC 算法和不外包的時間比較如圖3 所示。toriginal是不外包MIC 時的本地計算時間，tclient是外包MIC 時的計算時間。隨著矩陣規模的增大，兩者的差距越來越大。外包MIC 所需要的時間遠遠小于不外包所需要的時間。這說明，外包MIC 算法具有高效性。

外包MDC 算法和不外包的時間比較如圖4 所示。toriginal是不外包MDC 時的本地計算時間，tclient是外包MDC 時的計算時間。隨著矩陣規模的增大，兩者的差距越來越大。外包MDC 所需要的時間遠遠小于不外包所需要的時間。這說明，外包MDC 算法具有高效性。

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

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

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

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

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

7 結束語

本文設計了一種將矩陣相乘、矩陣求逆和行列式外包給云的算法。通過在置換矩陣的基礎上引入幺模矩陣的加密方法可以保護初始矩陣的每個元素的位置和數目，達到了正確性、隱私性、可驗證性和高效性的目的。本文的工作留下了一個有趣的問題，其他矩陣運算比如矩陣秩的計算、矩陣分解、矩陣的特征多項式以及特征值，對于資源有限的客戶端來說，這些操作同樣也是非常昂貴，因此也可以考慮外包給云服務器。基于其他矩陣運算，如何設計更高效、更安全的協議，是一個值得研究的課題。除此之外，在有限域上設計一個可驗證的安全外包計算協議將是非常有意義的。