基于安全多方計算的系統(tǒng)間隱私保持推薦算法

張明磊，韓 明，王震洲

（1.河北科技大學(xué) 黨政辦公室，河北 石家莊 050018；2.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；3河北科技大學(xué) 信息科學(xué)與工程學(xué)院，河北 石家莊 050018）

隨著個性化服務(wù)的興起，用戶的信息被分散在各個站點.由于站點信息的稀疏性，不同的用戶之間和站點之間的信息共享成為一種必然的趨勢[1].隨著系統(tǒng)間協(xié)同合作的廣泛應(yīng)用，用戶的隱私保持問題越來越受重視.雖然隱私偏好設(shè)定平臺P3P（Platform forPrivacy Preference）及復(fù)合能力/偏好設(shè)置文件CC/PP（Composite Capabilities/Preferences Profile）提高了用戶對個人隱私的控制權(quán)，但由于現(xiàn)存的站點大多不支持他們所定義規(guī)范和協(xié)議，用戶隱私難以保障.因此，如何保護隱私數(shù)據(jù)和防止敏感信息泄露成為系統(tǒng)間協(xié)作所面臨的重大挑戰(zhàn).

為了解決系統(tǒng)間個性化服務(wù)中的隱私泄露問題，BM.Sarwar[2]提出基于流行排列的跨系統(tǒng)個性化方法，即通過用戶與系統(tǒng)的參與以及大量的機器學(xué)習(xí)，將隱私保護機制加入到傳統(tǒng)的概率性潛在語義分析 PLSA(Probabilistic Latent Semantic Analysis)中.2008年，黃創(chuàng)光[3]提出一種基于同態(tài)加密的隱私保護方法，系統(tǒng)根據(jù)加密后的矢量積計算用戶間的相關(guān)相似性，并利用相關(guān)相似性實現(xiàn)跨系統(tǒng)隱私保持協(xié)同過濾.2009年，C.Clifton[4-5]又利用基于商品服務(wù)商模型的安全矢量積[6]技術(shù)解決了系統(tǒng)間協(xié)作計算問題.但由于第三方的不可信性，使得此方法存在一定的安全隱患.

針對以上存在的用戶信息安全問題，本文基于RSA（Rivest，Sham iramp;Adleman）公鑰密碼系統(tǒng)和解決互不信任的參與方之間隱私的安全多方計算理論（SecureMulti-Party Computation，SMC）[7]為基礎(chǔ)，提出一個安全計算模型SCM，并將此安全計算模型SCM應(yīng)用到系統(tǒng)間的協(xié)同過濾推薦算法中.實驗證明該算法可以有效防止第三方的惡意串通，保障用戶隱私不被泄露，與單系統(tǒng)協(xié)同過濾相比，跨系統(tǒng)協(xié)同過濾提高了推薦精度.

1 傳統(tǒng)的協(xié)同過濾算法存在問題

協(xié)同過濾技術(shù)即收集用戶評分數(shù)據(jù)集中的“最近鄰居”，根據(jù)“最近鄰居”的評分進而預(yù)測目標用戶的評分.

“最近鄰居”即根據(jù)相關(guān)相似性高的用戶的集合，其中相關(guān)相似性度量計算公式如式 (1)所示.

根據(jù)協(xié)同過濾發(fā)生的位置不同，采取相應(yīng)的措施.首先，當協(xié)同過濾發(fā)生在單個系統(tǒng)內(nèi)部時，則默認用戶同意信息共享；其次，當協(xié)同過濾的過程發(fā)生在不同的系統(tǒng)之間時，由于各種因素造成用戶隱私在系統(tǒng)間泄露，使得用戶和個性化服務(wù)站點不愿意提供用戶信息共享的服務(wù)或模型[8].

為使數(shù)據(jù)隱私最大限度地得到保持，使用協(xié)同過濾技術(shù)，對給定的目標用戶進行評分預(yù)測.對于不同的用戶分屬于不同的系統(tǒng)時，為了保證信息安全，根據(jù)式 (1)計算用戶的相似度時，首先來判斷隱私是否泄露.例如：設(shè)系統(tǒng)和，通過式 (1)計算用戶 和用戶的相似度，則和的值必然要在系統(tǒng)和之間共享，而通過的大小可推測用戶 對項目的評分大于還是小于平均值，進而推測出用戶對項目是喜歡還是厭惡，因而造成隱私泄露.由此可見和值對于跨系統(tǒng)度量用戶相似性非常重要，因此保證不把和的值泄露給進行協(xié)作計算的系統(tǒng)，就可以保證信息擁有者的信息安全和共享信息的質(zhì)量.

2 基于多個不可行第三方的安全計算模型SCM

由于網(wǎng)絡(luò)上信息資源逐漸增多，使得單個系統(tǒng)中信息的稀疏性越來越嚴重，要求多個系統(tǒng)間的協(xié)作計算也越來越多.當給定目標用戶后，系統(tǒng)向相同領(lǐng)域內(nèi)的系統(tǒng)發(fā)出協(xié)作計算請求，并按照安全計算模型 SCM將請求系統(tǒng)中的用戶評分數(shù)據(jù)在系統(tǒng)間共享，準確地對某一指定項進行評分預(yù)測，為用戶提供跨系統(tǒng)的隱私保持個性化服務(wù)[9].

2.1 安全多方計算

安全多方計算指在一組互不信任的參與多方合作計算的參與者中，相互在不泄露各自的私有信息的前提下進行的多方合作計算.在計算的過程中只能了解自己的輸入和輸出的最終計算結(jié)果，但是不能獲得其他參與者的信息的多方計算.

2.2 安全計算模型SCM

為了實現(xiàn)多個第三方協(xié)同合作與系統(tǒng)間的數(shù)據(jù)傳遞，同時防止第三方和系統(tǒng)惡意串通，本文以RSA公鑰密碼系統(tǒng)和SMC理論為基礎(chǔ)，提出一個安全計算模型SCM.系統(tǒng)首先利用RSA公鑰密碼系統(tǒng)將公鑰放入公鑰庫，當?shù)谌揭獮橄到y(tǒng)提供數(shù)據(jù)時首先去公鑰庫里找到系統(tǒng)的公鑰，并利用公鑰將數(shù)據(jù)加密，數(shù)據(jù)并不直接由第三方傳遞給系統(tǒng)，而是通過一個中間節(jié)點，在第三方和中間節(jié)點之間采用茫然傳送協(xié)議，中間節(jié)點將獲得的數(shù)據(jù)傳遞給系統(tǒng)，實現(xiàn)第三方和系統(tǒng)間的數(shù)據(jù)傳遞.安全計算模型SCM具體描述如圖1所示.

安全計算模型SCM：

1）系統(tǒng)利用RSA公鑰密碼系統(tǒng)產(chǎn)生一對用來加密和解密的密鑰，公鑰和私鑰，并將公鑰放入公鑰庫，另一私鑰保密；

2）當?shù)谌揭拖到y(tǒng)傳遞數(shù)據(jù)時，首先從公鑰庫中取得系統(tǒng)發(fā)布的公鑰，并將要發(fā)送的明文使用公鑰加密得到密文 ，并將密文 發(fā)送給中間節(jié)點；

3）第三方和中間節(jié)點采用茫然傳送協(xié)議，中間節(jié)點從密文組(c1,c2,...,cci,...,cm)中獲得一組數(shù)據(jù)ci.并將獲得的數(shù)據(jù)ci發(fā)送給系統(tǒng)；

圖1 安全計算模型SCMFig.1 Secure computingmodelSCM

3 系統(tǒng)間隱私保持協(xié)同過濾推薦算法

為了保護用戶在使用跨系統(tǒng)服務(wù)時的隱私信息，本文提出基于SCM的跨系統(tǒng)隱私保持協(xié)同過濾推薦算法.

圖2給出了兩個系統(tǒng)間基于SCM的跨系統(tǒng)服務(wù)模型，系統(tǒng)A和系統(tǒng)B借助中間模塊SCM實現(xiàn)系統(tǒng)間的協(xié)作計算.

下面給出了兩個系統(tǒng)間基于SCM的隱私保持協(xié)同過濾推薦算法PPCF-SCM，算法描述如下.

輸入：

輸出：

1）A lice和Bob分別利用RSA公鑰密碼系統(tǒng)產(chǎn)生一對用來加密和解密的密鑰，公鑰，和私鑰，，并將公鑰放入公鑰庫，另一對私鑰，保密；

圖2 基于SCM的跨系統(tǒng)服務(wù)Fig.2 Cross-system servicesbased on SCM

該算法結(jié)合了SCM的優(yōu)點，文中已論證了SCM的安全性，同傳統(tǒng)的安全多方計算相比，PPCF-SCM可以有效防止第三方的惡意串通，由于RSA公鑰密碼系統(tǒng)的參與，勢必會造成系統(tǒng)間通訊時間的增加，為了提高算法的性能，RSA密鑰對的產(chǎn)生即算法的第一步也可以離線進行.

4 實驗結(jié)果及其分析

4.1 實驗數(shù)據(jù)

本文的實驗數(shù)據(jù)來自于Jester數(shù)據(jù)集，此數(shù)據(jù)集是對73 421個用戶的100個笑話的4.1×106個數(shù)據(jù)的評分，參與的評分數(shù)據(jù)為 10～10之間的連續(xù)數(shù)據(jù).數(shù)據(jù)庫包括3個Excel表格，其中前2個數(shù)據(jù)較稠密，其稠密度高達72%，第3個數(shù)據(jù)較稀疏，其稠密度只有24%.

4.2 度量標準

實驗評價標準采用平均絕對偏差（Mean Absolute Error，MAE）預(yù)測準確性.設(shè)評分項目個數(shù)為，預(yù)測評分集合為，實際評分集合為，則平均絕對誤差[8]為MAE值越小，表明預(yù)測精度越高，預(yù)測評分和實際評分相差越小.

4.3 實驗結(jié)果及分析

為了驗證提出的保護用戶隱私的跨系統(tǒng)協(xié)同過濾推薦算法的有效性，分別從算法的性能和推薦精度上進行了實驗驗證.

4.3.1 RSA公鑰加密系統(tǒng)的性能分析及驗證

RSA算法目前最新記錄是129位十進制數(shù)已處在分解技術(shù)的邊緣上，因此要選取足夠大的數(shù)作為公鑰.考慮到密鑰長度對RSA算法的執(zhí)行時間的影響，利用java語言實現(xiàn)了一個簡單的RSA公鑰密碼系統(tǒng)，在本文的試驗中選取的密鑰長度分別為512位，1 024位和2 048位，實驗仿真給出了RSA密鑰生成時間以及加密解密時間，如圖3所示.

由圖3的實驗結(jié)果可以看出，RSA密鑰生成時間隨著密鑰長度的增加而呈現(xiàn)指數(shù)級增加，RSA加密和解密時間也呈現(xiàn)線性增長趨勢.由于RSA的攻擊主要依賴于大數(shù)的因數(shù)分解，并且有實驗證明對于200位10進制數(shù)進行因式分解，在億次機上需要運行55萬年，因此本文選取足夠大的素數(shù)保證攻擊者根據(jù)公鑰求私鑰在計算上的不可行性.

4.3.2 相似性度量比較

對于分布式系統(tǒng)間基于矢量積的隱私保持協(xié)同過濾算法的性能 D.Heckmann[8]已經(jīng)給出了證明，下面針對跨系統(tǒng)協(xié)同過濾和單系統(tǒng)協(xié)同的精度進行對比試驗.分別從數(shù)據(jù)比較稀疏的數(shù)據(jù)表中隨機選取100個用戶評分向量作為系統(tǒng)A，從數(shù)據(jù)比較稠密的數(shù)據(jù)表中隨機選取100個用戶作為系統(tǒng)B.為了比較數(shù)據(jù)的稀疏度對協(xié)同過濾推薦算法的影響，本文采用數(shù)據(jù)的稀疏度來衡量數(shù)據(jù)的稀疏情況，稀疏度即用戶評分矩陣中未評分數(shù)目所占的比例.系統(tǒng)A的數(shù)據(jù)稀疏度為0.82，系統(tǒng)B的數(shù)據(jù)稀疏度為0.18.由于系統(tǒng)A的用戶的評分數(shù)據(jù)極端稀疏，為了給用戶提供更加滿意的個性化服務(wù)，系統(tǒng)A向系統(tǒng)B發(fā)出協(xié)作計算請求，當系統(tǒng)A收到系統(tǒng)B的同意協(xié)作計算的反饋后，系統(tǒng)A和系統(tǒng)B按照算法PPCFSCM，共同完成協(xié)作計算.

實驗分別對系統(tǒng)A和系統(tǒng)B及系統(tǒng)A與B間的跨系統(tǒng)協(xié)作計算的平均絕對誤差MAE進行了對比試驗，相似鄰居的個數(shù)從4遞增到20個，推薦精度對比如圖4所示.

由實驗結(jié)果可知，協(xié)同過濾的推薦精度隨著數(shù)據(jù)集稀疏度的增加而降低，對于用戶數(shù)據(jù)非常稀疏的站點，通過跨系統(tǒng)協(xié)作計算，可以有效地提高協(xié)同過濾推薦算法的推薦精度，并且基于安全計算模型的跨系統(tǒng)協(xié)作計算可以保護用戶的隱私不泄露給協(xié)同合作的系統(tǒng).

圖3 RSA算法的密鑰長度-執(zhí)行時間Fig.3 Key length and execution timeof RSA algorithm

5 結(jié)論

本文針對跨系統(tǒng)協(xié)同過濾推薦算法中存在的用戶隱私泄露問題，在安全多方計算的基礎(chǔ)上提出一個安全計算模型，此模型在RSA公鑰密碼系統(tǒng)和安全多方計算的理論基礎(chǔ)上，實現(xiàn)了在保護用戶評分矩陣的前提下進行跨系統(tǒng)協(xié)同過濾計算，同時可有效防止第三方和任何一方惡意串通，并給出了證明及實驗結(jié)果.本文給出了兩個系統(tǒng)間協(xié)作計算的實驗結(jié)果，理論上可以從兩個系統(tǒng)推廣到多個系統(tǒng)，但還沒有進行實驗驗證，下一步的工作主要集中在多個系統(tǒng)之間的推廣和應(yīng)用.

圖4 推薦精度對比Fig.4 Recommended accuracy comparison

[1]Deng Ai-Lin，Zhu Yang-Yong，ShiBai-Le.A Collaborative Filtering Recommendation Algorithm Based on Item Rating Prediction[J].Journalof Software，2003，14（9）:1621-1627.

[2]SarwarBM，KarypisG，Konstan JA，Riedl J.Applicationofdimensionality reduction in recommendersystem-A casestudy[C]//ACMWebKDD 2000Workshop.2000.

[3]黃創(chuàng)光，印鑒，汪靜.不確定近鄰的協(xié)同過濾推薦算法 [J].計算機學(xué)報，2010，33（8）:1369-1377.

[4]JVaidya，CClifton，M Zhu. Privacy Preserving DataM ining（Advances in Information Security）[M].New York：Springer2Verlag，2005.

[5]M Kantarcioglu，C Clifton.Privacy preserving distributedm ining of association rules on horizontally partitioned data[J].IEEE Transactions on Know ledgeand Data Engineering，2004，16（9）:1026-1037.

[6]QIU Mei，LUO Shou shan，LIUWen，CHEN Ping. A Solution of Secure Multi2Party Multi-Data Ranking Problem Based on RSA Encryption Scheme[J].Acta Electronica Sinica，2009，37（5）:1119-1123.

[7]YaoiA.Protocols forsecure computations[C]//Proceedingsof the23rd Annual IEEESymposium on FoundationsofComputerScience，LosAngeles：1982，160-164.

[8]羅文俊，李祥.多方安全矩陣乘積協(xié)議及應(yīng)用 [J].計算機學(xué)報，2005，28（7）:1230-1235.

[9]BhaskarMehta，Wolfgang Nejdl.IntelligentDistributed UserModeling:from Semantics to Learning[C]//Proceedingsof the InternationalWorkshop on Ubiquitousand Decentralized UserModeling UBIDEUM 2007，USA：2007，18-28.