可驗證的大規(guī)模矩陣滿秩分解的安全外包

杜志強，鄭 東，趙慶蘭

（西安郵電大學網(wǎng)絡空間安全學院，西安 710121）

（*通信作者電子郵箱zhaoqinglan@foxmail.com）

0 引言

隨著科技的不斷發(fā)展，基于云的服務在人們的生活中也越來越普及，如物聯(lián)網(wǎng)、醫(yī)療數(shù)據(jù)，因此，產(chǎn)生數(shù)據(jù)的規(guī)模也越來越大。對于資源受限的用戶來說，自己購買設備處理這些數(shù)據(jù)是不太現(xiàn)實的，因為購買和維護設備都需要大量的資金，是一個巨大的負擔，所以為了經(jīng)濟的需求，資源受限的用戶可以將龐大的數(shù)據(jù)存儲在云上，或者將復雜度高的計算外包給云［1-2］。這種模式以其方便快捷、價格低廉、可擴展性等優(yōu)勢，給社會帶來巨大的變革，但是，云帶來便利的同時，也會帶來一些安全性問題［3］：一方面，由于競爭者的利益輸送，云可能返回給用戶一個惡意的值，或者將計算結果泄露給競爭者；另一方面，為了節(jié)省開銷，云可能會返回給用戶一個任意的值；此外，云計算必須大大減少用戶自身的開銷，所以，方案必須是安全有效和可驗證的。

矩陣的滿秩分解作為基本的線性代數(shù)和矩陣理論問題，在學術和工程方面有許多應用，比如廣義逆求解、最小二乘解的計算、超廣義投影分析等。通常進行滿秩分解采用的方法是使用高斯消去法推導出原始矩陣的行階梯型［4］。假設一個m×n的矩陣A的秩為r，那么高斯消去法的時間復雜度為O(mnrw-2)［5］，其中w代表矩陣乘法的指數(shù)。目前，當采用Williams算法［6］時，w最小，w=2.373，所以滿秩分解的最低時間復雜度是O(mnr0.373)。然而，在如今數(shù)據(jù)規(guī)模呈現(xiàn)爆炸性增長的時代，資源受限的用戶是無法進行本地計算的。所以，利用云計算將是一種有效的方法。

關于外包大規(guī)模計算的研究有很多，研究領域主要集中在科學計算領域和密碼學領域。在科學計算領域，主要是對大規(guī)模矩陣運算的外包。2001 年，Atallah 等［7］首先提出了科學計算問題的外包框架，該方案研究了矩陣求逆、矩陣乘法等問題的安全外包；但僅僅考慮到隱私性和安全性，而沒有考慮到高效性和可驗證性。2013 年和2014 年，Lei 等［8-9］先后提出了矩陣求逆、矩陣乘法的外包方案，該方案構造了新的置換矩陣來進行加解密，但這樣的置換矩陣無法保護零元素數(shù)目的安全。2015年，Lei等［10］繼續(xù)設計了一個矩陣滿秩分解的外包方案，存在的問題是不僅沒有保護零元素數(shù)目的安全，而且不具備可驗證性。2016 年，Zhou 等［11］研究了矩陣的特征值分解和奇異值分解（Singular Value Decomposition，SVD）的外包，但該方案仍然存在零元素泄漏的問題。2017 年，Zhou 等［12］提出了外包線性回歸問題的方案，保護了零元素的安全。同年，Luo 等［13］研究了外包矩陣的正交三角（QR）分解和三角（Lower-Upper，LU）分解的問題，該方案中用戶需要和云進行多次交互。2019 年，Zhang 等［14］利用有限域上的幺模矩陣進行矩陣乘法、矩陣求逆、行列式的外包，解決了之前的方案中存在的零元素泄漏的問題，但對矩陣的處理也限制在了有限域。

在密碼學領域，外包主要集中在模冪和模逆兩個方面：2015 年，Xiang 等［15］分別針對單模冪運算和多模冪運算設計了兩種外包方案，安全性較之前有了提高，但是降低了效率；2019年，Tian等［16］巧妙地利用幺模矩陣的性質(zhì)，設計了模逆運算的安全外包，與之前的方案相比，將云的數(shù)量從兩個降到了一個。所以目前為止，關于安全外包滿秩分解仍然是一個開放的問題。

本文的主要工作如下：

1）對于需要保護矩陣零元素數(shù)目的安全和對云返回結果進行驗證的問題，提出了一個安全可驗證的矩陣滿秩分解的外包方案。

2）協(xié)議分析證明方案是正確、安全、高效和可驗證的。

3）計算出加密矩陣的熵，證明了方案可以盲化原始矩陣中零元素的數(shù)目，并且實驗證明方案具有較高的效率。

1 問題描述

1.1 系統(tǒng)模型

系統(tǒng)模型如圖1所示，資源受限的用戶將大規(guī)模矩陣A的滿秩分解問題外包到資源豐富的云上進行求解。假設云是惡意的，所以為保護用戶的輸入輸出隱私，用戶利用密鑰K將原始矩陣加密為X，然后發(fā)送給云。在對云返回的結果解密之前，必須對結果進行驗證：如果驗證通過，則繼續(xù)解密；否則，直接拒絕。

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

1.2 設計目標

本文設計的目標包括4 點：正確性、安全性、高效性和可驗證性。

正確性 如果云和用戶都誠實地執(zhí)行了方案，那么用戶最終可以得到正確的結果。

安全性 設計的方案必須可以有效地保護用戶的輸入輸出隱私。

高效性 用戶運行外包算法的時間要遠遠小于本地計算滿秩分解的時間。

可驗證性 方案必須具備驗證云返回結果正確性的能力。

2 預備知識

2.1 相關引理

引理1［4］有m×n的矩陣A，rank(A)=r。如果存在列滿秩矩陣和行滿秩矩陣，使得A=FG，則稱上式為矩陣A的滿秩分解。

引理2［17］Fm×r為列滿秩矩陣的充分必要條件是存在左逆Wr×m，使得Wr×m*Fm×r=Ir。同理，Gr×n是行滿秩矩陣充分必要條件是存在右逆Rn×r，使得Gr×n*Rn×r=Ir。

引理3［17］設A=Am×n，則rank(A)=r的充分必要條件是存在行滿秩矩陣Pr×n和列滿秩矩陣Qm×r，使得A=QP。

引理4［18］如果有m×m的可逆矩陣S1，和n×n的可逆矩 陣S2，則對于任意的m×n矩 陣A，有rank(S1A)=rank(AS2)=rank(S1AS2)。

引理5［19］Sherman-Morrison 公式：定義P是可逆矩陣，u、v是列向量。如果(1+vTP-1u) ≠0，則(P+uvT)-1=P-1-

2.2 置換

置換在群理論和組合學應用廣泛。根據(jù)柯西兩行表示法，可以寫成如下形式：

其中：π(i)=bi，并且bi∈[1，n]且互不相等。π-1表示置換的逆置換。

定義克羅內(nèi)克函數(shù)

給定集合{α1，α2，…，αm}←κα和{β1，β2，…，βn}←κβ，然后根據(jù)生成的置換π1、π2，定義置換矩陣［8］P1(i，j)=同時，也可以得到置換矩陣的逆。

2.3 加密矩陣

本文利用Sherman-Morrison 公式構造一種稠密的加密矩陣S1，且這個矩陣可逆。操作如下：

1）首先根據(jù)文獻［8］，約束集合{α1，α2，…，αm}←κα都大于0，隨后生成置換矩陣P1。

2）其次生成兩個列向量u1、v1，保證列向量中的每個元素大于0。

3）生成S1=P1+由于取密鑰空間κα的中的元素都大于零，則根據(jù)有其次，有u1(i) ＞0，v1(i) ＞0，所以根據(jù)Sherman-Morrison 公 式，只 要有同理，構造加密矩陣

3 可驗證的矩陣滿秩分解的安全外包

3.1 方案概述

假設外包矩陣Am×n的滿秩分解，求解出列滿秩矩陣B和行滿秩矩陣C，使其滿足A=BC。方案如下：用戶首先根據(jù)2.3 節(jié)，構造出加密矩陣S1、S2、隨后，對原始矩陣A進行加密，X=，最后將X發(fā)送給云。云在得到加密矩陣X后，首先對X進行滿秩分解，得到列滿秩矩陣Fm×r和行滿秩矩陣Gr×n。接下來繼續(xù)計算Fm×r的左逆Wr×m和Gr×n的右逆Rn×r，最后將4 個矩陣返回給用戶。在驗證階段需要驗證兩部分內(nèi)容：1）Fm×r是否為列滿秩矩陣，Gr×n是否為行滿秩矩陣；2）驗證等式X=Fm×r×Gr×n是否成立。和文獻［10］一樣，采用矩陣向量乘法進行概率性驗證。驗證通過則用戶進行解密。

3.2 具體的算法

外包矩陣Am×n滿秩分解的具體算法包含以下5個步驟：

1）密鑰生成。

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

輸出 密鑰K：{α1，α2…，αm}、{β1，β2…，βn}和4 個列向量u1、u2、v1、v2。

用戶定義密鑰空間κα、κβ，約束密鑰空間中的數(shù)據(jù)都是大于0 的。生成集合{α1，α2，…，αm}←κα，{β1，β2，…，βn}←κβ。同時產(chǎn)生m×1的密鑰列向量u1、v1，n×1的密鑰列向量u2、v2。約束列向量中的元素都是大于0的。

2）加密。

輸入A和密鑰K。

輸出 加密的矩陣X。

用戶首先生成m×m置換矩陣和n×n的置換矩陣構造出密鑰矩陣：

隨后根據(jù)定理1 高效的計算出加密矩陣X=，最后用戶將加密矩陣發(fā)送給云。

3）云計算。

輸入X。

輸出F，G，W，R。

云在接收到用戶發(fā)送來的加密矩陣X后，首先進行滿秩分解，得到兩個矩陣Fm×r，Gr×n。隨后計算矩陣Fm×r的左逆Wr×m和矩陣Gr×n的右逆Rn×r，并將這4 個矩陣F，G，W，R返回給用戶。

4）驗證。

輸入F，G，W，R。

輸出 0/1。

首先用戶驗證矩陣Fm×r和矩陣Gr×n是否是列滿秩和行滿秩矩陣。操作如下：

用戶隨機生成l組r× 1維的列向量t，計算：

如果q1和q2是零向量，則繼續(xù)；否則返回0，表示結果錯誤。

隨后，用戶隨機生成l組n× 1 維的列向量d，計算Fm×r×Gr×n×dn×1-Xm×n×dn×1=q3。如果q3是零向量，返回1，表示結果正確；否則返回0，表示結果錯誤。

5）解密。

輸入F，G和密鑰K。

輸出B，C。

用戶計算B=，C=GS2。

4 協(xié)議分析

4.1 協(xié)議證明

定理1加密過程和解密過程是高效的。

證明 在加密過程中

開銷主要集中在矩陣與置換矩陣之間的計算或矩陣向量之間的計算。各部分的時間復雜度如下的時間復雜度 為O(mn)；的時間復雜度為O(5mn)；時間復雜度為O(3mn)的時間復雜度為O(7mn)。故加密的時間復雜度為O(16mn)。同理，解密的時間復雜度為O(8mn)。

定理2外包方案滿足正確性、安全性、高效性和可驗證性。

證明 1）外包方案滿足正確性。

利用兩個可逆矩陣S1、S2將矩陣A加密成X=隨后云返回X的滿秩分解為：

所 以F=S1B，G=可以推導出C=GS2。而且，通過引理4，有rank(X)=r。此外

故在解密完成后，B是列滿秩矩陣和C是行滿秩矩陣且A=BC。由引理1 和引理3 得，B、C一定是秩為r的矩陣A的滿秩分解。

2）外包方案滿足安全性。

當m，n非常大時，攻擊者不可能獲取用戶的輸入輸出隱私。

3）外包方案滿足高效性。

由于云是具備大量資源的實體，所以不考慮云的開銷。從定理1 得，加密的時間復雜度為O(16mn)，解密的時間復雜度為O(8mn)。同時，密鑰生成的時間復雜度為O(3(m+n))，驗證的時間復雜度為O(3mrl) +O(3nrl) +O(mnl)。由于l遠小于m、n，所以用戶所需的總的時間復雜度近似為O(mn) +O(mr) +O(nr)。而文獻［10］的時間復雜度也和本方案一樣，也為O(mn) +O(mr) +O(nr)。此外，由于用戶本地計算滿秩分解的時間復雜度為O(mnr0.373)。O(mnr0.373)遠大于O(mn) +O(mr) +O(nr)。所以，方案是高效的。

4）外包方案滿足可驗證性。

方案的驗證分為兩步：第一步是驗證云返回的F，G是否為行滿秩矩陣和列滿秩矩陣。這步是非常有必要的，因為云有可能返回給用戶任意兩個滿足X=FG的矩陣F，G。所以除了讓云計算X的滿秩分解外，也讓云計算出F的左逆W和G的右逆R。這是因為從引理2得，矩陣存在左逆則一定是列滿秩矩陣；同理，存在右逆一定是行滿秩矩陣。因此，如果成功驗證F是列滿秩矩陣和G是行滿秩矩陣之后，再繼續(xù)第二步驗證X=FG是否相等。這里的驗證都是通過矩陣向量乘法進行的概率性驗證，成功的概率為

4.2 加密矩陣的熵

在信息論中，香農(nóng)提出熵是信息不確定度的度量，可用于進行安全性評估。通過一組實驗來測量加密矩陣的熵，證明方案確實可以保護矩陣零元素的安全，并與文獻［10］算法進行了比較。方便起見，認為原始矩陣的維度是512 × 512，矩陣中非0元素的密度從0.1增加到1。

實驗結果如圖2 所示，本文算法的熵恒定為18。這說明在本文的加密矩陣中，每個元素都不相同，盲化了零元素的數(shù)目。理由如下：假設在加密矩陣中，每個元素都不相同，不存在重復的零元素，則每個元素出現(xiàn)的概率均為p(xi)=所以根據(jù)熵的計算公式：

圖2 加密矩陣的熵Fig.2 Entropy of encryption matrix

計算出加密矩陣的熵。如下：

計算得到熵為18，與實驗結果相同，說明方案保護了零元素數(shù)目的安全。而在文獻［10］算法中，熵的大小是隨著矩陣的密度的增加而遞增，因此不能保護零元素的安全。

5 實驗仿真

本章對本文方案進行仿真。仿真環(huán)境是：Inter Core i7，1.8 GHz CPU，4 GB RAM，Matlab 2015a。方便起見，假設原始矩陣的維度為n×n。在實驗中，用戶計算和云計算是在同一臺電腦進行，這樣可以忽略用戶端和云端之間的通信延遲，不考慮云計算時間，并且定義toriginal為用戶本地完成滿秩分解所需要的時間，tclient為用戶運行算法所需要的時間，即在密鑰生成、加密、驗證、解密這4 個階段總的時間。speedup=toriginal/tclient，表示加速比，當這個值大于1時，表示算法有效，并且這個值越大，說明用戶運行算法所能得到的收益越高。實驗結果如表1所示。

表1 不同維度下各階段的運行時間 單位：sTab.1 Running time of each stage in different dimension unit：s

實驗結果表明，當矩陣是1 000×1 000 的方陣時，用戶本地計算矩陣滿秩分解的時間為14.278 5 s，而如果采用設計的外包協(xié)議，所需要的時間僅為0.183 8 s。因此，外包矩陣滿秩分解可以得到77.678 5 倍的效率，說明方案確實可以有效地節(jié)省用戶滿秩分解的時間。而且從表1 的數(shù)據(jù)可以看出，當矩陣的規(guī)模越來越大時，隨著加速比的增加，用戶選擇外包時得到的效率也越來越高。所以，實驗結果體現(xiàn)了方案的高效性。

6 結語

本文利用Sherman-Morrison等式和矩陣的偽逆的性質(zhì)，提出了一個安全有效、可驗證的外包矩陣滿秩分解的方案。方案不僅對原始矩陣中零元素的數(shù)目進行了保護，而且對云返回的結果進行了驗證。通過協(xié)議分析和實驗仿真證明了方案具有正確、安全、高效、可驗證的性質(zhì)。本文的驗證算法是概率性的驗證算法。接下來，將引入公共驗證的性質(zhì)對外包問題進行重點研究。