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

張明磊，韓 明，王震洲

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

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

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

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

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

協(xié)同過濾技術(shù)即收集用戶評(píng)分?jǐn)?shù)據(jù)集中的“最近鄰居”，根據(jù)“最近鄰居”的評(píng)分進(jìn)而預(yù)測目標(biāo)用戶的評(píng)分.

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

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

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

2 基于多個(gè)不可行第三方的安全計(jì)算模型SCM

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

2.1 安全多方計(jì)算

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

2.2 安全計(jì)算模型SCM

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

安全計(jì)算模型SCM：

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

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

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

圖1 安全計(jì)算模型SCMFig.1 Secure computingmodelSCM

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

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

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

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

輸入：

輸出：

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

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

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

4 實(shí)驗(yàn)結(jié)果及其分析

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

4.2 度量標(biāo)準(zhǔn)

實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)采用平均絕對(duì)偏差（Mean Absolute Error，MAE）預(yù)測準(zhǔn)確性.設(shè)評(píng)分項(xiàng)目個(gè)數(shù)為，預(yù)測評(píng)分集合為，實(shí)際評(píng)分集合為，則平均絕對(duì)誤差[8]為MAE值越小，表明預(yù)測精度越高，預(yù)測評(píng)分和實(shí)際評(píng)分相差越小.

4.3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

4.3.2 相似性度量比較

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

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

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

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

5 結(jié)論

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

圖4 推薦精度對(duì)比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].計(jì)算機(jī)學(xué)報(bào)，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].計(jì)算機(jī)學(xué)報(bào)，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.