云輔助的安全高效非負矩陣分解算法

祁新雷,周 強,田呈亮

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

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

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

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

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

1 預備知識

1.1 非負矩陣分解

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

Vi=WHi

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

1.2 代價函數

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

(1)

當且僅當A=B時,上式為0。

根據式(1),把NMF問題轉化為優化問題

非負矩陣W和H中的每一個元素都要大于等于零,因此在實際應用中,會預先設定錯誤邊界ε,即當

時,認為V≈WH。

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

1.3 置換矩陣

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

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

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

特別地,恒等置換為

對于變量i,j,克羅內克δ函數定義為

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

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

(2)

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

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

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

2 系統模型和設計目標

2.1 系統模型

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

圖1 系統模型

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

2.2 設計目標

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

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

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

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

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

3 安全外包算法

3.1 問題描述及基本思想

V′=(VB)m×t

式中,t=p+n。

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

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

3.2 安全外包算法具體描述

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

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

并將V″以及分解因子r發送給云服務器。

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

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

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

3.3 算法理論分析

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

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,安全外包是正確的。

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

對于輸入矩陣V∈m×n,通過隨機矩陣、對角矩陣和以及置換矩陣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,安全外包能夠保護用戶輸入信息V∈m×n和輸出信息(分解結果)W、H的隱私。

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

3.3.3 可驗證性分析

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

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

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

3.3.4 高效性分析

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

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

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

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

此時復雜度為O(mr)。

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

4 性能評估實驗

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

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

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

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

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

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

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

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

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

5 結語

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