祁新雷,周 強(qiáng),田呈亮

(1.西安郵電大學(xué) 研究生院,陜西 西安 710121;2.青島大學(xué) 計算機(jī)科學(xué)技術(shù)學(xué)院,山東 青島 266071)

非負(fù)矩陣分解[1](Non-negative Matrix Factorization,NMF)主要是把一個非負(fù)矩陣V∈m×n分解成兩個規(guī)模更小的非負(fù)矩陣W∈m×r和H∈r×n,使得V≈WH。通過非負(fù)矩陣分解,可獲得近似原始矩陣的低秩矩陣,使得數(shù)據(jù)的存儲和處理更高效便捷,現(xiàn)已廣泛應(yīng)用在計算機(jī)視覺[2]、數(shù)據(jù)挖掘[3]、音頻信號處理[4]和推薦系統(tǒng)[5]等眾多領(lǐng)域。 然而,在大數(shù)據(jù)時代的實際應(yīng)用中,非負(fù)矩陣分解涉及到的矩陣往往規(guī)模很大,導(dǎo)致非負(fù)矩陣分解算法消耗大量的計算資源[6-7]。例如,圖像視頻處理過程中產(chǎn)生的大小為60 000×60 000雙精度矩陣占用存儲空間高達(dá)20 G,而使用一臺普通的筆記本電腦對一個8 000×4 000矩陣進(jìn)行非負(fù)矩陣分解時,耗時將近10 min。因此,資源受限的用戶很難在本地執(zhí)行非負(fù)矩陣分解操作。

云計算提供對可配置計算資源共享池的按需網(wǎng)絡(luò)訪問。通過云計算服務(wù),資源受限的用戶可以通過按需付費方式將沉重的計算任務(wù)外包給云服務(wù)器,而不必購買昂貴的軟硬件設(shè)備維持足夠大的計算資源。然而,遠(yuǎn)程云服務(wù)器的不可信性給這種計算模式帶來了許多安全挑戰(zhàn)[8-9]。首先,云服務(wù)器可能對收到的數(shù)據(jù)好奇,而用戶的外包數(shù)據(jù)可能包含用戶的生物特征信息、醫(yī)療記錄以及財產(chǎn)數(shù)據(jù)等敏感信息,這些敏感信息一旦泄露,將會給用戶帶來嚴(yán)重?fù)p失。其次,出于外部經(jīng)濟(jì)利益驅(qū)動,云服務(wù)器可能是懶惰的甚至是惡意的,這使得云服務(wù)器可能返回隨機(jī)或故意偽造的結(jié)果欺騙用戶。最后,一些意外事件,如軟硬件故障或外部攻擊也可能導(dǎo)致產(chǎn)生錯誤的計算結(jié)果。因此,設(shè)計保護(hù)用戶數(shù)據(jù)隱私并可檢測云服務(wù)惡意行為的高效外包計算算法具有重要的研究價值。

1992年,Chaum等[10]首次提出了“Wallet with Observers”概念,給出了一個在用戶的計算機(jī)中安裝一個安全硬件輔助用戶計算的方案。此后,設(shè)計完備的安全外包算法成為科學(xué)和工程技術(shù)領(lǐng)域的研究熱點[11]。根據(jù)當(dāng)前研究目的不同,安全外包算法主要分為兩個研究方向。第一個方向是致力于研究適用于任意運算的通用外包算法,聚焦于設(shè)計全同態(tài)加密(Fully Homomorphic Encryption,FHE)方案。Gentry[12]于2009年設(shè)計了第一個FHE方案,但由于實現(xiàn)全同態(tài)加密本身就涉及復(fù)雜的運算,導(dǎo)致方案效率很低,難以在實際工程應(yīng)用部署。另一個方向是研究適用于特定計算任務(wù)的定制外包算法,例如,大規(guī)模矩陣運算[13-15]、大規(guī)模線性方程組的求解[16]、線性回歸[17]、雙線性對運算[18]、模指數(shù)運算[19-20]和模逆運算[21]等。盡管該領(lǐng)域的研究廣泛,但對NMF的外包算法研究卻鮮有涉及。2016年,Duan等[22]提出了一個實用的外包求解NMF算法,其采用兩個置換矩陣對原始矩陣進(jìn)行加密,利用NMF計算的迭代性質(zhì)設(shè)計了一種單輪驗證策略,理論和實驗都證明了這種策略是非常高效的。但是,Pan等[7]發(fā)現(xiàn)基于置換矩陣的加密方法存在兩個缺陷。第一,泄露了原始矩陣的元素信息。置換矩陣加密只會改變原始矩陣中元素的位置,并不會改變其大小,因而原始矩陣中的元素不會變,云服務(wù)器可以獲得原始矩陣中元素的分布信息。第二,泄露了原始矩陣的聚類性質(zhì)。云服務(wù)器計算出的結(jié)果只是真實結(jié)果的簡單置換,從加密結(jié)果中可獲得真實結(jié)果的聚類信息。因此,Pan等采用可逆稀疏矩陣進(jìn)行加密策略,給出了可行的可逆稀疏矩陣構(gòu)造方法,有效地保護(hù)了原始矩陣,但是并不能保護(hù)原始矩陣中零元素的數(shù)目和分布。

基于對上述研究成果存在的隱私泄露及消耗計算資源問題,擬提出一種基于單服務(wù)器的安全外包算法。首先通過隨機(jī)矩陣填充對原始輸入矩陣中元素的個數(shù)進(jìn)行隱藏,然后使用隨機(jī)置換和對角矩陣變換,盲化矩陣中的元素的數(shù)值和分布,以解決原始矩陣零元素的數(shù)目和分布信息不能保護(hù)的問題。同時,使用的置換矩陣與對角矩陣均為稀疏矩陣,從而降低本地端的加解密成本以及與云端的通信成本,使本地端獲得可觀的計算節(jié)省。

1 預(yù)備知識

1.1 非負(fù)矩陣分解

給定一個非負(fù)矩陣V∈m×n,其非負(fù)矩陣分解是指尋找兩個非負(fù)矩陣W∈m×r和H∈r×n,使得V≈WH,其中r為分解因子,其同時小于m,n。V的每一列可以看作W中所有列向量的線性組合,即

Vi=WHi

式中：Vi為V的第i個列向量;Hi為H的第i個列向量。

1.2 代價函數(shù)

為了尋找V的近似非負(fù)矩陣分解形式,通常通過定義代價函數(shù)衡量結(jié)果的近似程度[23]。一般地,可使用兩個非負(fù)矩陣A∈m×n和B∈m×n之間的一些距離度量構(gòu)造這樣的代價函數(shù)。常見的衡量方式是簡單計算A和B之間歐式距離的平方,即

(1)

當(dāng)且僅當(dāng)A=B時,上式為0。

根據(jù)式(1),把NMF問題轉(zhuǎn)化為優(yōu)化問題

非負(fù)矩陣W和H中的每一個元素都要大于等于零,因此在實際應(yīng)用中,會預(yù)先設(shè)定錯誤邊界ε,即當(dāng)

時,認(rèn)為V≈WH。

求解非負(fù)矩陣分解問題的計算復(fù)雜度約為O(lmnr),其中l(wèi)為算法中的迭代次數(shù)。在實際應(yīng)用中,為達(dá)到精確的分解結(jié)果,迭代次數(shù)通常會設(shè)定的比較大。因此,當(dāng)處理的矩陣規(guī)模較大時,非負(fù)矩陣分解問題的復(fù)雜度就會變得非常大,這時會給資源受限的用戶造成沉重的計算負(fù)擔(dān),可將該任務(wù)外包給資源豐富的云服務(wù)器完成。

1.3 置換矩陣

集合{1,2,...,n}上的置換是指從該集合到自身的雙射,置換通常用置換函數(shù)形式表示為

其中αi∈{1,2,…,n},也可以表示為

π(i)=αi,i=1,2,…,n

特別地,恒等置換為

對于變量i,j,克羅內(nèi)克δ函數(shù)定義為

設(shè)In×n為一個n維的單位矩陣,則置換π對應(yīng)的置換矩陣Mn×n,其第i行j列元素可表示為

Mi,j=Ii,jδπ(i),j,Mi,j∈{0,1}

(2)

式中,Iij為單位矩陣第i行j列元素。

生成隨機(jī)置換的Fisher-Yates洗牌算法由Richard Durstenfeld于1964年提出[24],其偽代碼如下。

算法1 Fisher-Yates洗牌算法輸入：n個元素輸出：隨機(jī)打亂順序的n個元素1.令π=In2.對i從n-1到1,執(zhí)行3.隨機(jī)選取j←{1,…,i}4.交換π(j) and π(i)

2 系統(tǒng)模型和設(shè)計目標(biāo)

2.1 系統(tǒng)模型

安全外包算法的系統(tǒng)模型主要由資源受限的用戶C和具有強(qiáng)大計算能力但是不可信的云服務(wù)器S兩個實體組成。用戶C擁有輸入數(shù)據(jù)x,要完成大規(guī)模運算任務(wù)Φ受限于有限的計算能力,用戶C意圖通過把計算任務(wù)外包給云服務(wù)器S以完成計算。系統(tǒng)模型示意圖如圖1所示。

圖1 系統(tǒng)模型

圖1中,用戶C先調(diào)用密鑰生成算法得到私鑰Ks,利用私鑰Ks把真實輸入數(shù)據(jù)x加密成為σx,再把盲化之后的數(shù)據(jù)σx和相關(guān)數(shù)據(jù)發(fā)送給云服務(wù)器S。云服務(wù)器S收到交付的計算任務(wù)Φ、輸入數(shù)據(jù)σx及相關(guān)數(shù)據(jù)后便計算σv=Φ(σx),并將結(jié)果σv返回給用戶C。最后,用戶C首先驗證σv的正確性,如果驗證成功,則解密σv,將其恢復(fù)成真實結(jié)果y,否則輸出⊥。

2.2 設(shè)計目標(biāo)

完備的安全外包算法需要滿足正確性、隱私性、可驗證性和高效性等4個設(shè)計目標(biāo)。

1)正確性。如果云服務(wù)器誠實地執(zhí)行算法指定的計算任務(wù),安全外包算法總能確保用戶得到正確的計算結(jié)果。

2)隱私性。隱私性包括輸入的隱私性和輸出的隱私性,是指云服務(wù)器不能從用戶交付的輸入的盲化數(shù)據(jù)和自己計算得到的輸出數(shù)據(jù)中,恢復(fù)出用戶的真實輸入和真實輸出的相關(guān)信息。

3)α-可驗證性。保證用戶能以不可忽略的概率α檢測出云服務(wù)器的惡意行為。

4)高效性。用戶在使用安全外包算法時,本地用戶加密、驗證和解密的用時總開銷要小于不使用外包算法單獨計算的時間。

3 安全外包算法

3.1 問題描述及基本思想

V′=(VB)m×t

式中,t=p+n。

將盲化矩陣V″發(fā)送給云服務(wù)器,計算完畢后向用戶返回結(jié)果,用戶驗證結(jié)果是否正確,如果正確,則恢復(fù)出真實輸出結(jié)果,否則報告云服務(wù)器的惡意行為。

安全外包算法首先通過隨機(jī)矩陣增擴(kuò)原始矩陣,然后使用對角矩陣和置換矩陣先后對增擴(kuò)后的矩陣進(jìn)行加密,實現(xiàn)了對輸入矩陣的徹底盲化,不僅盲化了矩陣中的非零元素,而且首次隱藏了矩陣中零元素的分布和數(shù)目,同時隱藏了原始矩陣的部分維數(shù)信息,使得安全性能大幅上升。

3.2 安全外包算法具體描述

安全外包主要包括密鑰生成、加密、云計算以及驗證和解密等4個子算法。

2)加密。對輸入矩陣V∈m×n,首先使用隨機(jī)矩陣B填充得到V′=(VB)m×t,然后使用對角矩陣和置換矩陣加密得到盲化矩陣

并將V″以及分解因子r發(fā)送給云服務(wù)器。

3)云計算。云服務(wù)器收到用戶發(fā)送的數(shù)據(jù)后,執(zhí)行非負(fù)矩陣分解算法,得到W″∈m×r,H″∈r×t,其中V″=W″H″。

4)驗證和解密。對云服務(wù)器返回的W″和H″進(jìn)行驗證,若W″、H″均為非負(fù)矩陣且

否則,用戶拒絕接收并報告云服務(wù)器的惡意行為。

3.3 算法理論分析

圍繞設(shè)計目標(biāo),下面分別分析安全外包算法的正確性、隱私性、可驗證性與高效性。

3.3.1 正確性分析

首先先給出幾個引理。

引理1對V∈m×n,若P1∈{0,1}m×m和P2∈{0,1}n×n為置換矩陣,則

(P1V)i=(P1)iV

引理2對V∈m×n,若和為對角線元素大于1的對角矩陣且滿足或那么

(D1V)i,j≥Vi,j

式中：(D1V)i,j為矩陣D1和矩陣V乘積的第i行j列元素;Vi,j為矩陣V的第i行j列元素。

而

定理1對任意有效輸入V∈m×n,安全外包是正確的。

證明正確性意味著如果安全外包中云服務(wù)器是“誠實的”,那么用戶最后將得到正確結(jié)果。

對于輸入矩陣V∈m×n,通過隨機(jī)矩陣、對角矩陣和以及置換矩陣P1∈{0,1}m×m和P2∈{0,1}t×t加密得到

式中,V′=(VB)m×t。

因此

而V′=(VB)m×t,于是有

則由引理1和引理2可得

即

3.3.2 隱私性分析

定理2對任意有效輸入V∈m×n,安全外包能夠保護(hù)用戶輸入信息V∈m×n和輸出信息(分解結(jié)果)W、H的隱私。

證明對輸入矩陣V∈m×n,通過隨機(jī)矩陣對角矩陣和以及置換矩陣P1∈{0,1}m×m和P2∈{0,1}t×t加密得到其中V′=(VB)m×t。引入隨機(jī)矩陣B增擴(kuò)了原始矩陣,通過對角矩陣加密改變了增擴(kuò)后的矩陣中元素的大小,實現(xiàn)了對原始矩陣中非零元素和部分維數(shù)信息的盲化,最后通過置換矩陣加密,打亂了增擴(kuò)后的矩陣中元素的排列方式,實現(xiàn)了對原始矩陣中零元素數(shù)目分布的隱藏。云服務(wù)器獲得盲化后的矩陣V″之后,由于B、D1、D2、P1和P2是保密的,因此由V″相關(guān)信息無法恢復(fù)出真實輸入V∈m×n的信息,從而保護(hù)了輸入數(shù)據(jù)的隱私性。云服務(wù)器通過盲化后的矩陣V″計算得到W′、H′,同樣如果沒有密鑰B、D1、D2、P1和P2,也無法恢復(fù)或者獲得真實輸出W、H的相關(guān)信息,從而保護(hù)了輸出數(shù)據(jù)的隱私。

3.3.3 可驗證性分析

定理3對任意有效輸入V∈m×n,安全外包滿足1-可驗證性。

證明對于輸入矩陣V∈m×n,云服務(wù)器收到盲化矩陣V″∈m×n后,計算得到W′和H′。若計算錯誤,則驗證條件W″、H′是非負(fù)矩陣且就不能滿足。如果驗證通過,由定理1可知,用戶可通過計算得到

因此,云服務(wù)器的惡意行為總是能夠以1的概率被發(fā)現(xiàn),即安全外包滿足1-可驗證性。

3.3.4 高效性分析

定理4對任意有效輸入矩陣V∈m×n,安全外包具有高效性。

證明在調(diào)用安全外包時,用戶只需完成密鑰生成、加密、驗證和解密步驟。由于密鑰生成階段可以在預(yù)處理時完成,因此用戶實際要完成加密、驗證和解密。

在驗證和解密階段,用戶驗證W″、H″為非負(fù)矩陣且

是否成立,此時復(fù)雜度為O(mtr)。驗證通過后要計算

此時復(fù)雜度為O(mr)。

綜上,用戶的計算復(fù)雜度為O(mtr),b

4 性能評估實驗

為評估安全外包的實際性能,實驗硬件配置為Intel(R) Core(TM) i5-3230M CPU、2.60 GHz和8 GB RAM。軟件環(huán)境為Matlab R2016a。設(shè)tClient表示用戶在調(diào)用外包算法時所花費的時間,即加密、驗證和解密的時間總和,tCloud表示調(diào)用外包算法時云服務(wù)器花費的時間,tDirect表示用戶本地直接計算所花費的時間。tDirect與tClient之間的比值是衡量外包算法效率的一項重要指標(biāo),比值越大,說明用戶獲得計算節(jié)省越多,算法效率越高。當(dāng)固定r時,不同規(guī)模矩陣采用安全外包和不采用安全外包兩種模式的時間開銷對比如表1所示。

表1 固定r時兩種模式的時間開銷對比

由表1可以看出,矩陣的規(guī)模越大,tDirect與tClient比值越大,安全外包的優(yōu)勢就越明顯,因此安全外包適用于大規(guī)模非負(fù)矩陣分解。

當(dāng)固定(m,n,p)時,不同規(guī)模矩陣采用安全外包和不采用安全外包兩種模式的時間開銷對比如表2所示。

表2 固定(m,n,p)時兩種模式的時間開銷對比

由表2可以看出,分解因子r越大,tDirect與tClient比值越大,安全外包的優(yōu)勢就越明顯。

當(dāng)固定(m,n,r)時,采用安全外包和不采用安全外包兩種模式的時間開銷對比如表3所示。

表3 固定(m,n,r)時兩種模式的時間開銷對比

由表3可以看出,引入隨機(jī)矩陣后,p的規(guī)模越大,安全外包算法的效率優(yōu)勢逐漸減小,因此用戶可以根據(jù)實際情況確定隨機(jī)矩陣的規(guī)模。如果對安全性要求較高,對計算速度要求不高時,可以選擇一個大規(guī)模的隨機(jī)矩陣。如果對安全性要求較低,對計算速度要求較高時,可以選擇一個小規(guī)模的隨機(jī)矩陣。3組實驗均表明,安全外包算法能使本地端獲得可觀的計算節(jié)省。

5 結(jié)語

通過引入隨機(jī)矩陣,并使用對角矩陣和置換矩陣等矩陣變換技術(shù),給出了一個云輔助的安全高效非負(fù)矩陣分解安全外包算法。該算法不僅盲化了輸入矩陣中的非零元素,而且首次實現(xiàn)了盲化了矩陣中零元素的數(shù)目和分布。理論分析證明了安全外包算法的正確性、隱私性、可驗證性和高效性。實驗結(jié)果表明,采用安全外包算法能使本地端獲得可觀的計算節(jié)省。