張麗敏

（西安外事學院現代教育技術中心 西安 710077）

1 引言

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

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

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

2 背景知識

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

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

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

b0←隨機維向量

for i←1 to k do

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

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

end for

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

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

2.2 Paillier加密

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

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

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

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

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

3.1 計算框架

本文方法涉及四方：云端、數據擁有者、數據采集器/貢獻者和經過授權的數據用戶。

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

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

3.2 威脅模型

本文的安全分析以所討論的架構的重要特征為基礎，認為如下假設是合理的。

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

·只有數據擁有者和授權用戶可以使用專有矩陣。數據擁有者可以授權部分可靠用戶使用數據，可靠用戶不會故意泄秘。不會出現內部人員攻擊現象。

·客戶端系統(tǒng)和通信信道經過妥善的安全處理，隱私矩陣或計算結果不會泄露。

·敵人只能看到經過安全處理的矩陣和提交的參與矩陣—向量安全計算的明文向量，其他信息均無法看到。

通過實施合適的安全規(guī)則便可以滿足這些假設。攻擊者的目標是想要恢復或估計矩陣元素和計算結果，即特征值和特征向量。

3.3 數據采集

數據表示：為了使用Paillier加密系統(tǒng)，所有數據需要轉化為非負的整數。然而，實踐中是在實數域處理矩陣。實現預期精度（如d位小數）的合理方法是將初始數值與10d相乘，從而提高數值的標度，舍棄剩余小數位。此外，需要對數據進行移位（shift）以保證數域為正。這一過程是完全可逆的，因此可以準確恢復結果。

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

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

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

3.4 冪迭代協(xié)議

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

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

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

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

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

為了通過Paillier同形運算，從E(A)和bi中計算出E(Abi)，bi不得被加密。在將bi發(fā)送給云端前，本文設計了一種擾動方法來保護bi?；舅悸肥鞘褂靡粋€隨機向量ri，并將發(fā)送給云端。

其中，q表示較大的隨機素數，q足夠大以包含應用域中的所有數值。利用準備階段生成的種子隨機向量來設計ri。

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

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

3.5 云端MapReduce計算

經過Paillier方法加密的數據，其體積要遠大于未加密時。設密鑰為1 024 bit，64 bit雙型初始數值加密后為2 048 bit，增長了32倍。任何基于Diffie-Hellman或大整數因式分解的加密方案均無法避免該成本。于是，普通規(guī)模的問題轉化為“大數據”問題。明確了這一問題后，本文設計了基于MapReduce的同形矩陣—向量相乘算法?？蛻舳税咽艿綌_動的向量bi作為參數傳遞給MapReduce程序，云端計算并返回下面描述云端計算時的MapReduce方法。

MapReduce程序非常簡單。map函數使用安全矩陣—向量相乘計算式（式4），并發(fā)送利用行號表示的結果。根據行號將map輸出，進行分割和排序，再發(fā)送給相應的reducer，reducer將數據段寫入磁盤。因為使用二進制表示法進行矩陣元素加密，所以本文設計了專門的輸入/輸出格式類以處理二進制數據。針對加密后矩陣的MapReduce矩陣—向量乘法程序如下。

發(fā)送

end for

partition(j,nr)/*j：行號；nr：reduce操作的的總次數*/

返回

reduce()/*j：行號；υ：結果*/

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

發(fā)送()

3.6 安全性分析

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

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

因為ri無法和隨機均勻樣本區(qū)分開，所以無論bi如何出現（bi與充分大的i類似），{}也無法和任意隨機向量集合區(qū)分開。因此，{}序列不會幫助敵人獲得更多{bi}相關信息，推論得證。

3.7 成本分析

授權用戶必須準備一個擾動池，傳輸成本和解密成本均為O(nm)，其中m很小。在冪迭代中，為了獲得k個特征向量需要O(km)次解密，為了存儲加密后的數值需要O(km)空間。當k和n較小時，客戶端成本也較小?？傮w來說，一臺PC可以應付這一工作負載，這一迭代對用戶充分利用云計算的效益具有重要意義。

云端為存儲經過加密的矩陣元素，需要的空間成本為O(n2)，還需要基于MapReduce的安全矩陣—向量相乘導致的計算成本。因為主要成本是map階段，Hadoop集群有p個map點，因此總成本為O(n2/p)。存儲成本與經過加密的數值數量成正比，且與密鑰尺寸有關。

4 仿真實驗

為了證明本文方法的有效性，設計了一系列實驗來評估數據采集器、授權用戶和云端三方的處理效率。

4.1 配置

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

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

4.2 數據采集器的成本

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

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

表1 10000維向量導致的數據采集器成本

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

4.3 迭代時的客戶端成本

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

計算步驟包括解密向量并構建新的明文向量。假設擾動池包括10個隨機生成的向量，表2給出了不同維數的成本分布。可以看出，解密步驟的用時最長，因為使用多核處理器后解密步驟可以并行執(zhí)行，所以這一成本可以進一步降低。

表2 客戶端的計算成本

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

4.4 云端成本

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

表3 用1024bit密鑰時矩陣加密的存儲成本

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

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

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

圖3給出了使用內部集群時一次迭代所產生的總體成本在云端和客戶端的分布情況。當維數上升時，總體成本主要取決于客戶端成本?？蛻舳撕驮贫顺杀究傮w情況表明，經過MapReduce優(yōu)化部署后，客戶端成本較低，云端效率較高。

圖2 一次加密后導致的MapReduce計算成本

圖3 客戶端與云端的成本比較

5 結束語

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

參考文獻

1 鄧維,劉方明,金海等.云計算數據中心的新能源應用:研究現狀與趨勢.計算機學報,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