云環(huán)境下一種低成本的數(shù)據(jù)安全存儲(chǔ)和處理框架

張麗敏

（西安外事學(xué)院現(xiàn)代教育技術(shù)中心 西安 710077）

1 引言

隨著網(wǎng)絡(luò)服務(wù)、移動(dòng)應(yīng)用和傳感器網(wǎng)絡(luò)的不斷發(fā)展，從多個(gè)分布式數(shù)據(jù)源中采集而成的數(shù)據(jù)集規(guī)模越來(lái)越大，數(shù)據(jù)集的用途越來(lái)越廣。例如，移動(dòng)設(shè)備的用戶(hù)可以生成用戶(hù)間交流情況、用戶(hù)對(duì)產(chǎn)品的興趣及用戶(hù)位置、用戶(hù)語(yǔ)音等多種有用信息。這些數(shù)據(jù)集已經(jīng)成為數(shù)據(jù)擁有者的重要資產(chǎn)。這一現(xiàn)象也為數(shù)據(jù)存儲(chǔ)、共享和分析帶來(lái)了多種挑戰(zhàn)：移動(dòng)設(shè)備和傳感器等大多數(shù)數(shù)據(jù)采集器可以用于存儲(chǔ)和處理數(shù)據(jù)的資源非常有限，數(shù)據(jù)只能被迫發(fā)送給服務(wù)器或云端；采集來(lái)的數(shù)據(jù)可能非常敏感，對(duì)數(shù)據(jù)傳輸、存儲(chǔ)和處理過(guò)程的安全性要求更高。安全地處理和分析大數(shù)據(jù)需要分配大量的計(jì)算資源，而云計(jì)算是實(shí)現(xiàn)這一目的的理想平臺(tái)[1]。

[2]提出一種方法，可以將計(jì)算任務(wù)安全外包。然而，該方法基于Gentry的全同形加密算法[3]，計(jì)算成本和密文體積太大，不具有可行性。Naehrig等人[4]提出一種安全的外包解決方案，只需要加密方法“稍微”同形即可，但是仍然存在密文體積過(guò)大的問(wèn)題。Atallah等人[5]提出一種適用于線(xiàn)性方程和矩陣相乘大規(guī)模應(yīng)用系統(tǒng)的安全外包方案。但是該方案會(huì)泄露隱私信息，依賴(lài)于非串通服務(wù)器，導(dǎo)致嚴(yán)重的通信開(kāi)銷(xiāo)，因此仍顯不足。

為此，文中提出一種基于云技術(shù)的數(shù)據(jù)存儲(chǔ)和處理框架，使用戶(hù)花費(fèi)較小成本便可對(duì)從分布式數(shù)據(jù)源中采集來(lái)的大型矩陣進(jìn)行安全共享和處理。在該框架下，數(shù)據(jù)貢獻(xiàn)者可以通過(guò)服務(wù)提供商（如數(shù)據(jù)擁有者）提供的移動(dòng)應(yīng)用，把數(shù)據(jù)向量（如描述用戶(hù)在社交網(wǎng)絡(luò)服務(wù)上交互情況的向量或者描述用戶(hù)感興趣話(huà)題的向量）提交給云端。數(shù)據(jù)擁有者授權(quán)數(shù)據(jù)消費(fèi)者（即社交服務(wù)提供商的數(shù)據(jù)挖掘團(tuán)隊(duì)）展開(kāi)分析。使用該框架，數(shù)據(jù)擁有者和數(shù)據(jù)消費(fèi)者不再需要擁有自己的計(jì)算基礎(chǔ)設(shè)施，只需要一臺(tái)PC與云基礎(chǔ)設(shè)施交互即能完成高強(qiáng)度的數(shù)據(jù)計(jì)算任務(wù)。本文框架的主要問(wèn)題就是數(shù)據(jù)的安全性。當(dāng)數(shù)據(jù)傳輸?shù)皆贫撕螅瑪?shù)據(jù)擁有者便失去了對(duì)數(shù)據(jù)的控制權(quán)，而底層的基礎(chǔ)設(shè)施由并不可靠的云供應(yīng)商提供，在云環(huán)境下實(shí)現(xiàn)數(shù)據(jù)的安全處理就非常困難。本文研究的目的就是使受到信任的相關(guān)方在不可靠的云基礎(chǔ)設(shè)施頂層展開(kāi)協(xié)作，對(duì)加密后的數(shù)據(jù)進(jìn)行安全計(jì)算。

2 背景知識(shí)

本節(jié)簡(jiǎn)要描述了文中用到的特征值分解以及Paillier加密等背景知識(shí)。表示模為q的n維整數(shù)向量的集合，{bi}表示向量（或數(shù)值）集合，其中i=1,…,k。

2.1 基于冪迭代的特征值分解

特征值分解是數(shù)據(jù)分析的重要工具。例如，主成份分析法就依賴(lài)于特征值分解[6]。在信息檢索領(lǐng)域，特征值分解常用來(lái)確定文本語(yǔ)料庫(kù)詞組和文檔間的關(guān)系，這些領(lǐng)域的矩陣規(guī)模可能非常大。因此，復(fù)雜度為O(n3)的直接計(jì)算方法不具有可行性。相反，對(duì)于大型矩陣，往往使用基于冪迭代[7]的方法求解Top-k特征向量。假設(shè)A是n×n維實(shí)數(shù)矩陣，b0是隨機(jī)n維向量，基于冪迭代的特征值分解算法如下。

b0←隨機(jī)維向量

for i←1 to k do

bi←Abi-1/||Abi-1||

冪迭代算法的其他運(yùn)算，成本為O(n)

end for

生成特征向量且成本為O(n)的后處理

在該迭代框架中，最復(fù)雜的運(yùn)算是bi←Abi-1/||Abi-1||，其他運(yùn)算只與bi和部分k×k維輔助矩陣有關(guān)。通常只需要部分特征向量，因此k較小（如k=10）。冪迭代方法其余計(jì)算過(guò)程的復(fù)雜度只有O(kn)。如果矩陣存儲(chǔ)于云端，則云端負(fù)責(zé)最復(fù)雜的部分，而客戶(hù)端負(fù)責(zé)剩余低成本運(yùn)算。

2.2 Paillier加密

全同形加密方法允許加密數(shù)據(jù)在不加密的情況下執(zhí)行加法和乘法運(yùn)算。Paillier加密方法是一種部分同形加密方法，其效率遠(yuǎn)高于參考文獻(xiàn)[3]中的全同形方法，但是只支持同形加法，即：

在Paillier加密方法中，乘法操作不得運(yùn)行于E(x)和E(y)之上。然而，如果有操作數(shù)沒(méi)有加密（如y），則乘法運(yùn)算可表示為：

其中，mod_power表示模冪運(yùn)算[8]。為了便于闡述，本文使用來(lái)(E(x))y表示E(x)mod_power y。已經(jīng)證明，Paillier加密的安全性很強(qiáng)，可以滿(mǎn)足語(yǔ)義安全的定義。

3 云環(huán)境下Top-k特征向量安全計(jì)算方法

本節(jié)描述了本文方法的主要組件。首先，給出總體計(jì)算框架，描述客戶(hù)端和云端組件的功能；其次，給出威脅模型，進(jìn)而提出基于Paillier加密和隨機(jī)擾動(dòng)的安全冪迭代算法和云端MapReduce算法；最后，分析本文方法的安全性和經(jīng)濟(jì)性。結(jié)果表明，本文方法可以實(shí)現(xiàn)云端計(jì)算成本最小化，同時(shí)保證處理大型矩陣的優(yōu)異性能和安全性。

3.1 計(jì)算框架

本文方法涉及四方：云端、數(shù)據(jù)擁有者、數(shù)據(jù)采集器/貢獻(xiàn)者和經(jīng)過(guò)授權(quán)的數(shù)據(jù)用戶(hù)。

圖1為云環(huán)境下矩陣數(shù)據(jù)框架，闡述了各方間的關(guān)系和交互。非云端方（數(shù)據(jù)擁有者）、數(shù)據(jù)采集器/貢獻(xiàn)者和經(jīng)過(guò)授權(quán)的用戶(hù)是可以信任的。數(shù)據(jù)擁有者對(duì)數(shù)據(jù)的各種權(quán)力進(jìn)行控制，分發(fā)公共密鑰，指示數(shù)據(jù)采集器/貢獻(xiàn)者上傳采集來(lái)的并且經(jīng)過(guò)公共密鑰加密的數(shù)據(jù)。數(shù)據(jù)擁有者可以自己處理匯總數(shù)據(jù)或者授權(quán)其他用戶(hù)使用加密數(shù)據(jù)。每個(gè)數(shù)據(jù)采集器可以貢獻(xiàn)小部分?jǐn)?shù)據(jù)，如一行矩陣。實(shí)際例子包括一段時(shí)間內(nèi)與其他用戶(hù)的交互或者對(duì)某些條目的建議。數(shù)據(jù)擁有者或授權(quán)用戶(hù)可以為完成數(shù)據(jù)分析或數(shù)據(jù)挖掘任務(wù)而與云端交互。請(qǐng)注意，加密后數(shù)據(jù)的規(guī)模遠(yuǎn)大于初始數(shù)據(jù)。授權(quán)用戶(hù)無(wú)法承擔(dān)在本地下載經(jīng)過(guò)加密的大型矩陣及計(jì)算任務(wù)。相反，他們希望充分利用云計(jì)算的優(yōu)勢(shì)，盡量降低云端的成本。

圖1 云環(huán)境下矩陣挖掘框架

3.2 威脅模型

本文的安全分析以所討論的架構(gòu)的重要特征為基礎(chǔ)，認(rèn)為如下假設(shè)是合理的。

·云提供商是不可靠的，可能會(huì)秘密觀察數(shù)據(jù)和數(shù)據(jù)的計(jì)算過(guò)程，進(jìn)而發(fā)現(xiàn)有用信息，如特征向量。

·只有數(shù)據(jù)擁有者和授權(quán)用戶(hù)可以使用專(zhuān)有矩陣。數(shù)據(jù)擁有者可以授權(quán)部分可靠用戶(hù)使用數(shù)據(jù)，可靠用戶(hù)不會(huì)故意泄秘。不會(huì)出現(xiàn)內(nèi)部人員攻擊現(xiàn)象。

·客戶(hù)端系統(tǒng)和通信信道經(jīng)過(guò)妥善的安全處理，隱私矩陣或計(jì)算結(jié)果不會(huì)泄露。

·敵人只能看到經(jīng)過(guò)安全處理的矩陣和提交的參與矩陣—向量安全計(jì)算的明文向量，其他信息均無(wú)法看到。

通過(guò)實(shí)施合適的安全規(guī)則便可以滿(mǎn)足這些假設(shè)。攻擊者的目標(biāo)是想要恢復(fù)或估計(jì)矩陣元素和計(jì)算結(jié)果，即特征值和特征向量。

3.3 數(shù)據(jù)采集

數(shù)據(jù)表示：為了使用Paillier加密系統(tǒng)，所有數(shù)據(jù)需要轉(zhuǎn)化為非負(fù)的整數(shù)。然而，實(shí)踐中是在實(shí)數(shù)域處理矩陣。實(shí)現(xiàn)預(yù)期精度（如d位小數(shù)）的合理方法是將初始數(shù)值與10d相乘，從而提高數(shù)值的標(biāo)度，舍棄剩余小數(shù)位。此外，需要對(duì)數(shù)據(jù)進(jìn)行移位（shift）以保證數(shù)域?yàn)檎＿@一過(guò)程是完全可逆的，因此可以準(zhǔn)確恢復(fù)結(jié)果。

提交數(shù)據(jù)：為了采集數(shù)據(jù)，數(shù)據(jù)擁有者將生成一個(gè)n維隨機(jī)向量b0，且b0利 用Paillier公 共 密鑰加密，即E(b0)=(E(b01),…,E(b0n))，然后分發(fā)給數(shù)據(jù)采集器。

數(shù)據(jù)采集器i將其矩陣Ai的部分行以加密的形式提交給云存儲(chǔ)。此外，它們將利用如下同形算法計(jì)算E(Aib0)的結(jié)果，并將其提交給數(shù)據(jù)擁有者。假設(shè)Ai某一行為a，則：

請(qǐng)注意，E(Aib0)中的元素?cái)?shù)量與采集器將要提交給云端的行的數(shù)量相同，且該數(shù)量通常為1。最后，數(shù)據(jù)擁有者收集所有的E(Aib0)，對(duì)其解密以尋找Ab0。

3.4 冪迭代協(xié)議

為了在冪迭代時(shí)保護(hù)提交給云端的明文向量的安全性，得到授權(quán)的數(shù)據(jù)用戶(hù)必須執(zhí)行數(shù)個(gè)步驟，以便為擾動(dòng)方法做好準(zhǔn)備。然后，客戶(hù)端與云端展開(kāi)協(xié)作，在迭代中完成安全矩陣—向量乘法運(yùn)算。

備好擾動(dòng)池。經(jīng)過(guò)授權(quán)的數(shù)據(jù)用戶(hù)將從數(shù)據(jù)擁有者接收E(b0)、E(Ab0)以及解密密鑰，然后選擇m個(gè)n維隨機(jī)向量，并將其發(fā)送給云端，其中m較小（如m=5）。這些隨機(jī)向量將被用于每次迭代時(shí)擾動(dòng)及保護(hù)向量{bi}。本文將其表示為種子隨機(jī)向量{si}，其中

對(duì)每個(gè)隨機(jī)向量si，在云端按照如下步驟進(jìn)行安全的Aisi計(jì)算。鑒于Pailier加密方法的同形屬性，對(duì)于結(jié)果向量(Aisi)j的第j個(gè)元素，有：

其中，sik表示向量si的第k個(gè)元素，Ajk表示矩 陣A的第(j,k)個(gè)元素。將E(Asi)發(fā)送回客戶(hù)端，經(jīng)過(guò)解密留作稍后處理。在準(zhǔn)備階段后，經(jīng)過(guò)授權(quán)的用戶(hù)保留隨機(jī)向量S={si}及結(jié)果向量As=(Asi),i=1,…,m。

迭代階段從隨機(jī)向量b0開(kāi)始，執(zhí)行bk+1=Abk/||Abk||及冪迭代方法中描述的其他低成本步驟。在每次迭代時(shí)必須要保護(hù)bi，否則，將會(huì)泄露特征向量。利用如下方法來(lái)保護(hù)計(jì)算的隱私性，其安全性將在稍后進(jìn)行詳細(xì)分析。

為了通過(guò)Paillier同形運(yùn)算，從E(A)和bi中計(jì)算出E(Abi)，bi不得被加密。在將bi發(fā)送給云端前，本文設(shè)計(jì)了一種擾動(dòng)方法來(lái)保護(hù)bi。基本思路是使用一個(gè)隨機(jī)向量ri，并將發(fā)送給云端。

其中，q表示較大的隨機(jī)素?cái)?shù)，q足夠大以包含應(yīng)用域中的所有數(shù)值。利用準(zhǔn)備階段生成的種子隨機(jī)向量來(lái)設(shè)計(jì)ri。

其中，i=1,…,k，αil和βij從中隨機(jī)選擇。在擾動(dòng)中包含bj(j=1,…,i-1)的目的是增強(qiáng)安全性，這一點(diǎn)將在稍后分析。于是，在準(zhǔn)備階段及先前步驟中計(jì)算出了{(lán)Ask}和{Abj,j

此時(shí)，只需要客戶(hù)端的向量運(yùn)算，成本為O(n)。

3.5 云端MapReduce計(jì)算

經(jīng)過(guò)Paillier方法加密的數(shù)據(jù)，其體積要遠(yuǎn)大于未加密時(shí)。設(shè)密鑰為1 024 bit，64 bit雙型初始數(shù)值加密后為2 048 bit，增長(zhǎng)了32倍。任何基于Diffie-Hellman或大整數(shù)因式分解的加密方案均無(wú)法避免該成本。于是，普通規(guī)模的問(wèn)題轉(zhuǎn)化為“大數(shù)據(jù)”問(wèn)題。明確了這一問(wèn)題后，本文設(shè)計(jì)了基于MapReduce的同形矩陣—向量相乘算法。客戶(hù)端把受到擾動(dòng)的向量bi作為參數(shù)傳遞給MapReduce程序，云端計(jì)算并返回下面描述云端計(jì)算時(shí)的MapReduce方法。

MapReduce程序非常簡(jiǎn)單。map函數(shù)使用安全矩陣—向量相乘計(jì)算式（式4），并發(fā)送利用行號(hào)表示的結(jié)果。根據(jù)行號(hào)將map輸出，進(jìn)行分割和排序，再發(fā)送給相應(yīng)的reducer，reducer將數(shù)據(jù)段寫(xiě)入磁盤(pán)。因?yàn)槭褂枚M(jìn)制表示法進(jìn)行矩陣元素加密，所以本文設(shè)計(jì)了專(zhuān)門(mén)的輸入/輸出格式類(lèi)以處理二進(jìn)制數(shù)據(jù)。針對(duì)加密后矩陣的MapReduce矩陣—向量乘法程序如下。

發(fā)送

end for

partition(j,nr)/*j：行號(hào)；nr：reduce操作的的總次數(shù)*/

返回

reduce()/*j：行號(hào)；υ：結(jié)果*/

瘦男人先幫女人跟蹤了一段“田科”，這是他為那個(gè)姓田的稅務(wù)干部起的綽號(hào)。再偷拍了一些照片，都是“田科”工作時(shí)間出入一些娛樂(lè)場(chǎng)所的身影。后來(lái)女人又讓他搞了些“田科”去查某些對(duì)口管轄單位，暗中收禮的情形，當(dāng)然這些證據(jù)很難掏弄，到手的幾個(gè)細(xì)節(jié)極其珍貴，女人給他加了錢(qián)。

發(fā)送()

3.6 安全性分析

本文算法包括3個(gè)部分：數(shù)據(jù)采集、客戶(hù)端的隨機(jī)擾動(dòng)、基于Paillier加密方法的矩陣—向量相乘。只要保證Paillier方法安全，那么第一部分和第三部分就能安全實(shí)現(xiàn)。因此，本文算法的安全性主要取決于第二部分。在擾動(dòng)準(zhǔn)確階段，云服務(wù)提供商可以采集擾動(dòng)池中的初始隨機(jī)種子向量S=(s1,…,sm)及逐漸生成的擾動(dòng)向量{bi}。此外，對(duì)手可能會(huì)知道，bi在次迭代內(nèi)收斂于與目標(biāo)特征值相對(duì)應(yīng)的主導(dǎo)特征向量。于是，有如下的推論。

設(shè)r1=Sa1+e1modq，其中e1=β1,0b0且a1保密。如果S、β1,0、b0均勻隨機(jī)選取，則和從隨機(jī)均勻選取的樣本之間的區(qū)分問(wèn)題就轉(zhuǎn)變?yōu)橛姓`差學(xué)習(xí)決策問(wèn)題[9]。根據(jù)參考文獻(xiàn)[9]可知，如果e1隨機(jī)選取且a1保密，則r1無(wú)法和隨機(jī)均勻選取的樣本區(qū)分開(kāi)來(lái)。因此，b1也無(wú)法與隨機(jī)均勻選擇的樣本區(qū)分開(kāi)來(lái)。相同的結(jié)論也可以推廣至i>1且未知量更多的情況。

因?yàn)閞i無(wú)法和隨機(jī)均勻樣本區(qū)分開(kāi)，所以無(wú)論bi如何出現(xiàn)（bi與充分大的i類(lèi)似），{}也無(wú)法和任意隨機(jī)向量集合區(qū)分開(kāi)。因此，{}序列不會(huì)幫助敵人獲得更多{bi}相關(guān)信息，推論得證。

3.7 成本分析

授權(quán)用戶(hù)必須準(zhǔn)備一個(gè)擾動(dòng)池，傳輸成本和解密成本均為O(nm)，其中m很小。在冪迭代中，為了獲得k個(gè)特征向量需要O(km)次解密，為了存儲(chǔ)加密后的數(shù)值需要O(km)空間。當(dāng)k和n較小時(shí)，客戶(hù)端成本也較小。總體來(lái)說(shuō)，一臺(tái)PC可以應(yīng)付這一工作負(fù)載，這一迭代對(duì)用戶(hù)充分利用云計(jì)算的效益具有重要意義。

云端為存儲(chǔ)經(jīng)過(guò)加密的矩陣元素，需要的空間成本為O(n2)，還需要基于MapReduce的安全矩陣—向量相乘導(dǎo)致的計(jì)算成本。因?yàn)橹饕杀臼莔ap階段，Hadoop集群有p個(gè)map點(diǎn)，因此總成本為O(n2/p)。存儲(chǔ)成本與經(jīng)過(guò)加密的數(shù)值數(shù)量成正比，且與密鑰尺寸有關(guān)。

4 仿真實(shí)驗(yàn)

為了證明本文方法的有效性，設(shè)計(jì)了一系列實(shí)驗(yàn)來(lái)評(píng)估數(shù)據(jù)采集器、授權(quán)用戶(hù)和云端三方的處理效率。

4.1 配置

客戶(hù)端機(jī)器配置為128 GB RAM、4個(gè)四核AMD處理器。利用賴(lài)特州立大學(xué)的Hadoop集群來(lái)測(cè)試云端MapReduce程序。集群配置為16個(gè)從屬節(jié)點(diǎn)，運(yùn)行Apache Hadoop version 1.0.3。每個(gè)從屬節(jié)點(diǎn)的配置為16 GB RAM、4個(gè)四 核AMD處 理 器、16個(gè)map槽、12個(gè)reduce槽、64 MB HDFS塊。云端MapReduce程序用Java部署，客戶(hù)端程序用C++和GMP庫(kù)（gmplib.org）部署。

由于密鑰低于1 024 bit的Paillier加密方法是不安全的[10]，因此本文實(shí)驗(yàn)中使用1 024 bit密鑰，利用仿真矩陣展開(kāi)實(shí)驗(yàn)。初始矩陣使用雙精度值作為元素（每個(gè)數(shù)值8 byte），如第3.3節(jié)所示，這些矩陣轉(zhuǎn)化為長(zhǎng)整數(shù)以便加密，維持足夠的精度。在冪迭代算法中使用加密后矩陣作為MapReduce程序的輸入。

4.2 數(shù)據(jù)采集器的成本

框架下的每個(gè)數(shù)據(jù)采集器將生成一個(gè)或一些向量，對(duì)向量加密，然后將其提供給云端。此外，它還將進(jìn)行安全的向量點(diǎn)積運(yùn)算以生成E(Aib0)。因此，數(shù)據(jù)采集器的主要成本在于向量加密、安全向量點(diǎn)積運(yùn)算以及傳輸，這些成本由Paillier加密成本（即密鑰尺寸）及維數(shù)確定。

本文使用二進(jìn)制編碼方法實(shí)現(xiàn)被加密數(shù)據(jù)量最小化，同時(shí)實(shí)現(xiàn)通信和云存儲(chǔ)最小化。一般來(lái)講，二進(jìn)制表示的數(shù)據(jù)加密后的尺寸是加密密鑰的兩倍，例如64 bit雙精度數(shù)值使用1 024 bit鍵值加密后將成為2 048 bit。表1給出了10 000維向量使用1 024 bit鍵值時(shí)的比較情況。

表1 10000維向量導(dǎo)致的數(shù)據(jù)采集器成本

與二進(jìn)制法相比，未經(jīng)壓縮的大整數(shù)的原始文本表示法的空間成本比其高出150%（壓縮后高出40%），但是計(jì)算時(shí)間基本相同。鑒于加密后數(shù)據(jù)的隨機(jī)性，二進(jìn)制表示法的壓縮效果有限。

4.3 迭代時(shí)的客戶(hù)端成本

通信成本包括從云端接收到加密后向量以及將明文受擾向量返回給云端，使用字節(jié)數(shù)量來(lái)表示這些成本。根據(jù)先前的討論，10 000維的加密后向量將會(huì)花費(fèi)2.56 MB，且字節(jié)需要傳輸給客戶(hù)端。比較而言，返回的由10 000個(gè)長(zhǎng)整數(shù)組成的明文向量有80 KB，這些數(shù)據(jù)與維數(shù)成線(xiàn)性關(guān)系。

計(jì)算步驟包括解密向量并構(gòu)建新的明文向量。假設(shè)擾動(dòng)池包括10個(gè)隨機(jī)生成的向量，表2給出了不同維數(shù)的成本分布。可以看出，解密步驟的用時(shí)最長(zhǎng)，因?yàn)槭褂枚嗪颂幚砥骱蠼饷懿襟E可以并行執(zhí)行，所以這一成本可以進(jìn)一步降低。

表2 客戶(hù)端的計(jì)算成本

存儲(chǔ)成本包括加密向量和擾動(dòng)池中的明文向量。根據(jù)第3.5節(jié)的MapReduce計(jì)算可知，每次迭代后生成的bi將被加入到擾動(dòng)池。然而，迭代次數(shù)通常較小，因此擾動(dòng)池的存儲(chǔ)量較小即可。例如，有10 000個(gè)維度且擾動(dòng)池的尺寸為10，則10次迭代只需要2 MB的內(nèi)存來(lái)存儲(chǔ)明文長(zhǎng)整數(shù)向量。

4.4 云端成本

云端的成本主要來(lái)自存儲(chǔ)加密后數(shù)據(jù)及安全矩陣—向量相乘運(yùn)算。加密后數(shù)據(jù)的體積非常大，授權(quán)用戶(hù)一般不會(huì)本地下載并存儲(chǔ)數(shù)據(jù)。表3給出了部分實(shí)數(shù)，從而更加具體地闡述問(wèn)題規(guī)模。

表3 用1024bit密鑰時(shí)矩陣加密的存儲(chǔ)成本

很明顯，使用傳統(tǒng)的方法無(wú)法處理如此規(guī)模的數(shù)據(jù)，必須充分利用云端并行處理的特點(diǎn)。云端計(jì)算包括安全矩陣—向量乘法運(yùn)算。

矩陣以行向量集合的形式進(jìn)行存儲(chǔ)，并在Hadoop文件系統(tǒng)中分割成大小為64 MB的數(shù)據(jù)塊。MapReduce框架為每個(gè)塊分配一個(gè)map，使得向量—向量點(diǎn)積集合可以并行出現(xiàn)。由于非常復(fù)雜的運(yùn)算出現(xiàn)于map階段，因此map的數(shù)量決定了整體性能。

圖2表明，當(dāng)加密后矩陣的規(guī)模不同時(shí)，成本呈現(xiàn)上升趨勢(shì)。當(dāng)維數(shù)低于10 000時(shí)，map階段在內(nèi)部Hadoop集群上只需一輪即可完成。當(dāng)維度更多時(shí)，需要更多輪map，總體時(shí)間成本與map輪數(shù)成正比。平均來(lái)說(shuō)，每輪map時(shí)間約為30～40 s，這展示了較強(qiáng)的可拓展性。當(dāng)增加集群的規(guī)模（map槽數(shù)更多）可以維持一輪map時(shí)，總體成本將保持不變（約為40 s）。

圖3給出了使用內(nèi)部集群時(shí)一次迭代所產(chǎn)生的總體成本在云端和客戶(hù)端的分布情況。當(dāng)維數(shù)上升時(shí)，總體成本主要取決于客戶(hù)端成本。客戶(hù)端和云端成本總體情況表明，經(jīng)過(guò)MapReduce優(yōu)化部署后，客戶(hù)端成本較低，云端效率較高。

圖2 一次加密后導(dǎo)致的MapReduce計(jì)算成本

圖3 客戶(hù)端與云端的成本比較

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

本文提出一種冪迭代算法，可在云環(huán)境下從加密后數(shù)據(jù)中求得Top-k特征向量。基于Paillier加密算法和高效的隨機(jī)向量擾動(dòng)策略，實(shí)現(xiàn)了本文算法的安全性。經(jīng)過(guò)精心設(shè)計(jì)后，客戶(hù)端計(jì)算成本實(shí)現(xiàn)了最小化。此外，本文還提出一種MapReduce程序，可以高效處理云端經(jīng)過(guò)加密的矩陣—向量乘法運(yùn)算。實(shí)驗(yàn)結(jié)果證明，本文方法在配置和使用過(guò)程中產(chǎn)生的存儲(chǔ)和計(jì)算成本均在合理范圍內(nèi)，本文算法具有一定的可拓展性。下一步工作將對(duì)本文研究進(jìn)行延伸，提出針對(duì)稀疏矩陣的更為高效的處理算法，同時(shí)提出不可靠或懶惰型服務(wù)提供商檢測(cè)技術(shù)。

參考文獻(xiàn)

1 鄧維,劉方明,金海等.云計(jì)算數(shù)據(jù)中心的新能源應(yīng)用:研究現(xiàn)狀與趨勢(shì).計(jì)算機(jī)學(xué)報(bào),2013,36(3):582～596 Deng W,Liu F M,Jin H,et al.Leveraging renewable energy in cloud computing data centers:state of the art and future research.Chinese Journal of Computers,2013,36(3):582～596

2 Gennaro R,Gentry C,Parno B.Non-interactive verifiable computing:outsourcing computation to untrusted workers.Proceedings of the 30th Annual Cryptology Conference,Santa Barbara,CA,USA,2010:465～482

3 Gentry C.Fully homomorphic encryption using ideal lattices.Proceedings of the 41st ACM Symposium on Theory of Computing(STOC),Washington,DC,USA,2009(9):169～178

4 Naehrig M,Lauter K,Vaikuntanathan V.Can homomorphic encryption be practical.Proceedings of the 3rd ACM on Cloud Computing Security Workshop,New York,USA,2011:113～124

5 Atallah M J,Frikken K B.Securely outsourcing linear algebra computations.Proceedings of the 5th ACM Symposium on Information,Computer and Communications Security,Beijing,China,2010:48～59

6 Ma Z.Sparse principal component analysis and iterative thresholding.The Annals of Statistics,2013,41(2):772～801

7 Bai Z,Li R C.Minimization principles for the linear response eigenvalue problemⅡ:computation.SIAM Journal on Matrix Analysis and Applications,2013,34(2):392～416

8 Al-Vahed A,Sahhavi H.An overview of modern cryptography.World Applied Programming,2011,1(1):3～8

9 Regev O.On lattices,learning with errors,random linear codes,and cryptography.Journal of the ACM(JACM),2009,56(6):34～43

10 Lenstra A K,Verheul E R.Selecting cryptographic key sizes.Journal of Cryptology,2001,14(4):255～293