數(shù)據(jù)隱私保護(hù)的社會化推薦協(xié)議

劉曙曙，劉安，趙雷，劉冠峰，李直旭，鄭凱，周曉方

(1.蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215000；2.江蘇省軟件新技術(shù)與產(chǎn)業(yè)化協(xié)同創(chuàng)新中心，江蘇 南京 211102)

1 引言

推薦系統(tǒng)是一系列通過對用戶或其購買行為進(jìn)行分析，從而自動為用戶推薦其可能感興趣的信息和商品的算法集合。協(xié)同過濾算法出現(xiàn)以來就受到了廣泛關(guān)注，但隨之而來的“冷啟動”問題卻制約了該算法的進(jìn)一步使用。為解決這一問題，研究學(xué)者們提出了基于鄰域的社會化推薦方法[1,2]，該方法指出，將基于社交網(wǎng)絡(luò)拓?fù)鋱D得到的用戶關(guān)系引入到推薦系統(tǒng)中，可以有效解決協(xié)同過濾計(jì)算過程中由于新用戶缺少歷史行為數(shù)據(jù)而帶來的“冷啟動”問題?；卩徲虻纳鐣扑]算法得到普遍關(guān)注，同時(shí)，大量最新的研究也表明，該算法明顯優(yōu)于傳統(tǒng)推薦算法。

盡管推薦系統(tǒng)能夠幫助人們在海量數(shù)據(jù)中高效快速過濾掉大量無關(guān)信息，但是，這一過程帶來的信息泄露卻值得人們擔(dān)憂。在傳統(tǒng)的推薦系統(tǒng)中，用戶的歷史行為數(shù)據(jù)，如購物記錄、對于電影或物品的評分記錄等，都必須作為數(shù)據(jù)上傳到推薦系統(tǒng)服務(wù)器。一旦這些信息發(fā)生泄漏，攻擊者便可以基于以上信息，迅速推測出用戶的年齡、性別、身體狀況等個(gè)人隱私信息，由此而引發(fā)的一些問題可能會對用戶的生命財(cái)產(chǎn)造成威脅。

為了防止傳統(tǒng)推薦系統(tǒng)中由于用戶歷史行為數(shù)據(jù)泄露而帶來的擔(dān)憂，研究學(xué)者們提出了一系列解決方案。Canny[5]最初提出了針對推薦系統(tǒng)的隱私保護(hù)方案，通過借助同態(tài)加密和一個(gè)端對端的協(xié)議，他能夠?yàn)槎喾N基于協(xié)同過濾的推薦系統(tǒng)提供隱私服務(wù)。該方案同樣在文獻(xiàn)[4,6]中得到了應(yīng)用。借助隨機(jī)擾動技術(shù)，Polat和Du[7]將用戶的歷史行為數(shù)據(jù)進(jìn)行一定程度的干擾后再將其發(fā)送給推薦服務(wù)提供商，從而保證了用戶的數(shù)據(jù)隱私安全。文獻(xiàn)[8]使用了相同的原理來實(shí)現(xiàn)這一目標(biāo)，他們都能夠保證用戶的歷史行為數(shù)據(jù)在推薦服務(wù)提供商端的安全。Jorgensen[3]等提出利用差分隱私技術(shù)可以保證目標(biāo)用戶無法從推薦結(jié)果中推測任何和其他用戶相關(guān)的信息，從而保證了其他用戶個(gè)人隱私的安全性。不同于上述傳統(tǒng)推薦系統(tǒng)中的問題模型，在社會化推薦系統(tǒng)中，以推薦系統(tǒng)服務(wù)提供商及社交網(wǎng)絡(luò)服務(wù)提供商為主要參與方。在現(xiàn)實(shí)生活中，推薦系統(tǒng)服務(wù)提供商通常對應(yīng)在線電子商務(wù)平臺，他們持有用戶的歷史行為數(shù)據(jù)，卻沒有完善的社交網(wǎng)絡(luò)拓?fù)鋱D；社交網(wǎng)絡(luò)拓?fù)鋱D通常來自于第三方的在線社交網(wǎng)絡(luò)服務(wù)提供商，如FaceBook或者Twitter等，他們都擁有用戶信賴及用戶數(shù)據(jù)信息。但是，出于對社交網(wǎng)絡(luò)拓?fù)鋱D擁有重要的利益價(jià)值和維護(hù)用戶隱私的考慮，在線社交網(wǎng)絡(luò)服務(wù)提供商并不愿意將數(shù)據(jù)信息提供給推薦系統(tǒng)服務(wù)提供商。同樣，推薦系統(tǒng)服務(wù)提供商愿意為用戶提供高效的推薦服務(wù)，但是并不愿意透漏用戶的歷史行為數(shù)據(jù)。

出于對以上實(shí)際情況的考慮，本文認(rèn)為在社會化推薦系統(tǒng)中，保證兩主要參與方的數(shù)據(jù)隱私安全是完成社會化推薦的前提。上述方案雖然能夠有效解決傳統(tǒng)推薦系統(tǒng)中用戶隱私保護(hù)問題，但是這些方案并不適用于本文的問題模型。如何能夠在保護(hù)雙方數(shù)據(jù)隱私的前提下，實(shí)現(xiàn)兩參與方協(xié)同計(jì)算的問題是本文的重點(diǎn)，將在后面詳細(xì)講解。

2 相關(guān)背景及問題定義

在基于鄰域的社會化推薦系統(tǒng)中，通常有2個(gè)參與方，分別稱為Alice和Bob。Alice代表持有用戶歷史行為數(shù)據(jù)的推薦系統(tǒng)服務(wù)提供商（如ebay、淘寶等電子商務(wù)平臺），Bob是擁有社交網(wǎng)絡(luò)拓?fù)鋱D的第三方社交網(wǎng)站（如Facebook、Twitter等）。本文分別對以上2個(gè)數(shù)據(jù)模型給出形式化的定義。

定義1用戶歷史行為二分圖。如圖1（a）所示，用戶歷史行為數(shù)據(jù)圖Gt=(U,I,Et)是一個(gè)單向二分圖，其中，U(∣U∣=M)是所有用戶的集合，I(∣I∣=N)是物品集合，Et是由用戶U指向物品I的單向邊集合，每一條邊都附有權(quán)重值w(u,i)≥0，w(u,i)＞0時(shí)，表示用戶u對于物品i的相應(yīng)評分或購買頻次，當(dāng)用戶u未曾購買過物品i,w(u,i)=0。

定義2用戶社交網(wǎng)絡(luò)拓?fù)鋱D。如圖1（b）所示，社交網(wǎng)絡(luò)拓?fù)鋱DGs=(U,Es)是一個(gè)由用戶集合U和用戶關(guān)系邊Es構(gòu)成的無向圖，其中，Es(u,v)表示用戶u和v之間存在聯(lián)系。

圖1 用戶歷史行為二分圖和用戶社交網(wǎng)絡(luò)拓?fù)?/p>

上述假設(shè)模型可以方便地?cái)U(kuò)展到其他應(yīng)用領(lǐng)域，如在Last.fm中，邊Et(u,i)表示用戶u聽過作者i的歌曲，在Brightkite.com中，邊Et(u,i)表示用戶u曾經(jīng)訪問過位置i，在上述假設(shè)中，權(quán)重值w(u，i)分別代表了用戶u聽過作者i的歌曲的次數(shù)，以及用戶u曾經(jīng)訪問過位置i的次數(shù)。同樣，各種類型的在線社交網(wǎng)站均可映射到定義2的模型中，如關(guān)系邊（u,v）既可表示Facebook中用戶u和v之間的好友關(guān)系，也可以代表Twitter中用戶之間的“Following”關(guān)系。

定義3基于鄰域的社會化推薦。假設(shè)兩參與方Alice和Bob，Alice擁有用戶歷史行為數(shù)據(jù)，Bob擁有社交網(wǎng)絡(luò)拓?fù)鋱D（以及用戶之間相似度度量算法sim），Alice和Bob通過合作計(jì)算，為目標(biāo)用戶u∈U，推薦K個(gè)評分最高的物品Ru∈I。

對于Alice中的任一目標(biāo)用戶u，Alice將會為u推薦K個(gè)得分最高的物品，記為集合Ru。其中，s(u,i)，即對于用戶u而言物品i的得分

其中，sim(u,v)是用戶u和v之間的相似度值，在非社會化推薦系統(tǒng)中，如圖2(a)所示，sim(u,v)的計(jì)算主要基于用戶的歷史交易記錄向量，常用方法有皮爾遜相關(guān)系數(shù)法、余弦相似度以及基于概率的相似度計(jì)算方法等，其中前2種方法使用最為廣泛。在社會化推薦系統(tǒng)中，如圖2(b)所示，相似度的計(jì)算通常基于社交網(wǎng)絡(luò)拓?fù)鋱D（即圖中用戶之間的鄰接矩陣），常用方法有共同鄰居（common neighbor），Katz以及隨機(jī)游走（random walk with restart）等。w(v,i)是用戶v與物品i的連接邊的權(quán)重值。

圖2 傳統(tǒng)和社會化推薦系統(tǒng)

在社會化推薦中，sim(u,v)的計(jì)算依賴于社交網(wǎng)絡(luò)拓?fù)鋱DGs。為了能夠完成社會化推薦，Alice即電子商務(wù)平臺必須利用社交網(wǎng)絡(luò)拓?fù)?。出于商業(yè)利益或維護(hù)用戶隱私的權(quán)益，Bob即社交網(wǎng)絡(luò)拓?fù)鋱D的持有者，并不愿意將私有數(shù)據(jù)，社交網(wǎng)絡(luò)拓?fù)鋱D直接提供給Alice使用，保證兩參與方的數(shù)據(jù)隱私安全是完成社會化推薦的前提。下面將給出保護(hù)隱私的社會化推薦的定義。

定義4保護(hù)隱私的社會化推薦。假設(shè)兩參與方Alice和Bob，Alice擁有用戶歷史行為數(shù)據(jù)，Bob擁有社交網(wǎng)絡(luò)拓?fù)鋱D以及用戶之間相似度度量算法sim，Alice和Bob通過合作計(jì)算，為目標(biāo)用戶u∈U，推薦K個(gè)評分最高的物品Ru∈I，計(jì)算過程中，雙方私有信息（如Gt和Gs）不能暴露給對方。

假設(shè)前提：定義中的推薦結(jié)果都是基于某一時(shí)刻的靜態(tài)圖譜Gt和Gs展開的。對于圖譜Gt和Gs的動態(tài)更新，需要重新運(yùn)行協(xié)議，更新推薦結(jié)果。下面將給出該問題的具體解決方案。

3 保護(hù)隱私的社會化推薦系統(tǒng)

針對社會化推薦系統(tǒng)需要在兩方隱私數(shù)據(jù)上進(jìn)行協(xié)同計(jì)算，本文提出了2種數(shù)據(jù)隱私保護(hù)的社會化推薦協(xié)議，可以同時(shí)保護(hù)推薦系統(tǒng)服務(wù)提供商和社交網(wǎng)絡(luò)服務(wù)提供商的數(shù)據(jù)隱私。其中，基于不經(jīng)意傳輸?shù)纳鐣扑]，計(jì)算代價(jià)較小，適用于對推薦效率要求較高的應(yīng)用?；谕瑧B(tài)加密的社會化推薦，安全程度較高，適用于對數(shù)據(jù)隱私要求較高的應(yīng)用。下面是2個(gè)協(xié)議的詳細(xì)介紹。

3.1 基于不經(jīng)意傳輸?shù)纳鐣扑]

不經(jīng)意傳輸(OT，oblivious transfer)是安全計(jì)算領(lǐng)域的重要工具，在眾多問題中得到了廣泛應(yīng)用。借助不經(jīng)意傳輸協(xié)議，可以高效地實(shí)現(xiàn)兩方安全乘法計(jì)算[13]。計(jì)算過程中，兩參與方私有數(shù)據(jù)信息安全完成后，結(jié)果由兩方以和形式秘密共享，即參與方A持有數(shù)據(jù)a，參與方B持有數(shù)據(jù)b，利用不經(jīng)意傳輸乘法協(xié)議后，A將持有結(jié)果x，B持有結(jié)果y，并且滿足公式x+y=ab。相關(guān)細(xì)節(jié)參見文獻(xiàn)[13]。

根據(jù)定義4，Alice持有數(shù)據(jù)Gt，Bob持有數(shù)據(jù)Gs。對于目標(biāo)用戶u，Bob可以根據(jù)事先確定好的相似度計(jì)算方法計(jì)算出sim(u,v)(v是除u外的所有其他用戶)。以物品i為例，Bob端持有相似度向量SIM={sim(u,u1),sim(u,u2),…,sim(u,um)}，Alice持有物品i的評分向量Wi={w(u1,i),w(u2,i),…,w(um,i)}，根據(jù)式（1）可知，對于目標(biāo)用戶u而言，物品i的推薦得分s(u,i)為對應(yīng)位積之和。具體算法如下。

算法1基于OT乘法的推薦得分算法

輸入：Alice端Gt=(U,I,Et)

在計(jì)算過程中，使用OT乘法直接算出所有用戶和物品之間的乘積，其復(fù)雜度為MN。但是由于用戶歷史行為記錄是一個(gè)及其稀疏的矩陣，通常為M+N，直接對所有元素進(jìn)行OT乘法操作，會產(chǎn)生大量不必要的計(jì)算。通用的解決方案是，Alice將用戶歷史行為記錄矩陣的數(shù)據(jù)分布情況（0為用戶未曾夠買過物品；1為用戶購買過物品）共享給Bob，同樣Bob也需要將自己數(shù)據(jù)分布情況共享給Alice，兩端僅需計(jì)算sim(u,uj)≠0和w(uj,i)≠0的項(xiàng)，從而減少不必要的計(jì)算開銷。在這一共享過程中，兩方共享的僅為數(shù)據(jù)分布情況，并未涉及兩方的數(shù)據(jù)值信息，在對安全要求不是很高的情況下，該方法是安全可信的。

利用OT乘法協(xié)議完成物品的推薦得分計(jì)算后，所有物品的推薦得分由Alice和Bob以加法和形式秘密共享，即Alice端持有s1，Bob持有s2，同時(shí)s1+s2=s。

接下來，需要從所有候選物品中，挑選出K個(gè)推薦得分最高的物品推薦給用戶。因?yàn)樽罱K只需要將K個(gè)推薦得分最高的物品推薦給目標(biāo)用戶即可，K個(gè)物品之間的排列順序并不影響推薦，所以采用線性時(shí)間復(fù)雜度的隨機(jī)選擇算法[14]來實(shí)現(xiàn)TopK選擇。

隨機(jī)選擇算法的基本思想是：隨機(jī)選擇樞紐元，將數(shù)據(jù)分為2個(gè)獨(dú)立的部分，其中一部分的所有數(shù)據(jù)都比樞紐元小，另外一部分的數(shù)據(jù)都比樞紐元大，然后再按此方法繼續(xù)對其中某一部分?jǐn)?shù)據(jù)進(jìn)行劃分，直到找到的樞紐元在整個(gè)序列中處于K的位置。具體算法如下。

算法2安全的TopK選擇算法

輸入：推薦得分向量S={s1,s2,…,sn}

輸出：K個(gè)最高推薦得分物品集合Ru

Yao協(xié)議[9,10]允許2個(gè)半誠實(shí)參與方分別輸入x和y作為一個(gè)任意函數(shù)f(x,y)的輸入，協(xié)議能夠保證兩參與方私有信息安全的前提下，準(zhǔn)確計(jì)算函數(shù)值，沒有任何關(guān)于輸入或者中間值的相關(guān)信息泄露。關(guān)于Yao協(xié)議的定理證明可以參見文獻(xiàn)[10]?；赮ao協(xié)議實(shí)現(xiàn)的兩方安全計(jì)算框架FGC[11]近年來憑借其高效的性能得到普遍使用。本文將基于FGC中的2-ADD和2-CMP這2個(gè)基本模塊，實(shí)現(xiàn)TopK選擇的比較模塊。其中，2-ADD可以實(shí)現(xiàn)任意2個(gè)L位整數(shù)之間的加法，2-CMP可以實(shí)現(xiàn)任意2個(gè)L位整數(shù)之間的比較，輸出結(jié)果為0或1。2-ADD可以以密文形式還原推薦得分，隨后使用2-CMP完成得分的比較即可。

3.2 基于同態(tài)加密的社會化推薦

在上述協(xié)議中，為了減少不必要的開銷，實(shí)現(xiàn)高效率計(jì)算，Alice和Bob需要將本身的數(shù)據(jù)分布情況共享給對方，盡管這一共享并沒有泄露兩參與方實(shí)際的數(shù)據(jù)值信息，但對于高安全級別的系統(tǒng)而言仍然存在一定程度的安全隱患。為了實(shí)現(xiàn)更高層次的安全保護(hù)，防止任何形式的信息泄露，提出了基于同態(tài)加密的完全隱私保護(hù)的社會化推薦協(xié)議。

Paillier同態(tài)加密系統(tǒng)[8]是Paillier于1999年發(fā)明的用于公鑰加密的概率非對稱算法。在本文中，用E(x)表示對明文x的Paillier加密函數(shù)，D(x)表示對密文x的Paillier解密函數(shù)，證明參見文獻(xiàn)[8]。該加密系統(tǒng)具有加法同態(tài)性質(zhì)，即2個(gè)密文乘積的解密值，與兩密文對應(yīng)明文的和相等；密文的k次冪解密值，與k和對應(yīng)明文的乘積相等；Paillier加密系統(tǒng)的語義安全特性保證了攻擊者無法由給定密文導(dǎo)出任何相關(guān)明文信息?；谕瑧B(tài)加密的推薦得分算法如下。

算法3基于Paillier同態(tài)機(jī)密的推薦得分算法

為了保證數(shù)據(jù)信息的安全，Bob端的相似度值需要用Paillier加密函數(shù)En加密后方可發(fā)送給Alice端，Paillier的語義安全特性保證了Alice無法從密文獲取與Bob相關(guān)的任何信息。同時(shí)，鑒于Paillier加密的同態(tài)性質(zhì)，Alice端可以單獨(dú)計(jì)算出所有物品的推薦結(jié)果得分，得分以密文形式存在。Alice端推薦得分計(jì)算公式如下

由于w(v,i)是Alice端的數(shù)據(jù)，所以Alice可以自動過濾掉w(uj,i)≠0的項(xiàng)，減少不必要的計(jì)算開銷?；赑aillier完成推薦得分計(jì)算后，結(jié)果以密文形式由Alice持有，密鑰由Bob端持有。

因?yàn)镻ailler并不支持基于密文的比較操作，Alice無法單獨(dú)實(shí)現(xiàn)安全的TopK選擇。加法秘密共享能夠保證推薦得分對于兩參與方的保密，同時(shí)，加法和秘密共享形式能保證安全的TopK選擇順利進(jìn)行。為了實(shí)現(xiàn)推薦得分的秘密共享，首先，Alice生成N個(gè)足夠大的隨機(jī)數(shù)r，并結(jié)合Paillier加密算法計(jì)算En(s-r)，密文結(jié)果發(fā)送給Bob；Bob借助其本身持有的密鑰可以解密數(shù)據(jù)，從而得到s'=s-r。至此，Alice端持有隨機(jī)數(shù)r，Bob持有s'，同時(shí)r+(s')=s。盡管Alice持有隨機(jī)數(shù)r和推薦得分的密文，但是Alice并沒有密鑰，所以無法得知任何與中間結(jié)果s相關(guān)的任何信息。Bob持有密鑰和s'，但是s'=s-r，由于隨機(jī)數(shù)的干擾，Bob端無法推測出s的相關(guān)信息。

接下來，調(diào)用算法2提出的安全TopK選擇算法，即可從所有候選物品中，挑選出K個(gè)推薦得分最高的物品推薦給用戶。

4 理論分析

攻擊模型：本文假設(shè)Alice和Bob都是半誠實(shí)的，兩方將嚴(yán)格的執(zhí)行協(xié)議，但是計(jì)算過程中兩方也會盡可能地根據(jù)中間信息推測出更多的額外信息。針對惡意攻擊模型的安全協(xié)議雖然存在，但是計(jì)算代價(jià)過大，在實(shí)際中并不實(shí)用。而針對半誠實(shí)模型的安全協(xié)議不但能夠?qū)崿F(xiàn)高效的計(jì)算，而且對惡意攻擊模型下的安全協(xié)議研究具有重要參考價(jià)值。

4.1 安全性分析

如上所述，社會化推薦方法包括物品的推薦得分計(jì)算和TopK選擇2個(gè)過程。此處將就這2個(gè)過程逐一分析。

本文就不經(jīng)意傳輸和同態(tài)加密提出了2種不同的隱私保護(hù)方法來計(jì)算推薦得分，在不經(jīng)傳輸乘法協(xié)議中，兩參與方私有數(shù)據(jù)信息安全，計(jì)算完成后，結(jié)果由兩方以和形式秘密共享，即參與方A持有數(shù)據(jù)a，參與方B持有數(shù)據(jù)b，利用不經(jīng)意傳輸乘法協(xié)議后，A將持有結(jié)果x，B持有結(jié)果y，并且滿足x+y=ab（相關(guān)安全性證明參見文獻(xiàn)[13]）。在不經(jīng)意傳輸乘法協(xié)議可信的前提下，基于不經(jīng)意傳輸?shù)耐扑]得分計(jì)算不會泄露任何一方的私有信息。

在基于同態(tài)加密實(shí)現(xiàn)的推薦得分計(jì)算中，為了保證數(shù)據(jù)信息的安全，Bob端將相似度值加密后發(fā)送給Alice端，Paillier的語義安全特性保證了Alice無法從密文獲取與Bob相關(guān)的任何信息。同時(shí)，基于密文，Alice端可以單獨(dú)計(jì)算出所有物品的推薦結(jié)果得分，得分以密文形式存在。為了實(shí)現(xiàn)加法秘密共享從而保證Garbled Circuit的調(diào)用，首先，Alice生成N個(gè)足夠大的隨機(jī)數(shù)r，并結(jié)合Paillier加密算法計(jì)算En(s-r)，密文結(jié)果發(fā)送給Bob；Bob借助其本身持有的密鑰可以解密數(shù)據(jù)，從而得到s'=s-r。至此，Alice端持有隨機(jī)數(shù)r，Bob持有s'，同時(shí)r+(s')=s。在此過程中，盡管Alice持有隨機(jī)數(shù)r和推薦得分的密文，但是Alice并沒有密鑰，所以無法得知任何與中間結(jié)果s相關(guān)的任何信息。Bob持有密鑰和s'，但是s'=s-r，由于隨機(jī)數(shù)的干擾，Bob端無法推測出s的相關(guān)信息。

完成推薦得分計(jì)算后，所有得分由Alice和Bob以加法和形式秘密共享，即Alice端持有s1，Bob持有s2，同時(shí)s1+s2=s。結(jié)合這一特點(diǎn)，可以基于Garbled Circuit提供的2-ADD和2-CMP這2個(gè)基本模塊完成TopK推薦。文獻(xiàn)[10]指出在半誠實(shí)模型下，Garbled Circuit允許2個(gè)參與方分別輸入x和y作為一個(gè)任意函數(shù)f(x,y)的輸入，協(xié)議能夠保證兩參與方私有信息安全的前提下，準(zhǔn)確計(jì)算函數(shù)值，沒有任何關(guān)于輸入或者中間值的相關(guān)信息泄露。這一性質(zhì)保證了在TopK推薦過程中，任何與兩方相關(guān)的輸入或者中間信息都不會泄露，該TopK選擇過程安全可靠。

綜上，基于不經(jīng)意傳輸?shù)纳鐣扑]方法和基于同態(tài)加密的社會化推薦方法，都能在保證兩方（推薦系統(tǒng)服務(wù)提供商和社交網(wǎng)絡(luò)服務(wù)提供商）數(shù)據(jù)隱私的前提下，為目標(biāo)用戶提供精確的推薦。

4.2 復(fù)雜度分析

如表1所示為兩方案的復(fù)雜度分析，其中，|U|表示用戶個(gè)數(shù)，|I|表示物品個(gè)數(shù)，|Et|表示用戶歷史購買記錄條數(shù)，t為推薦得分的二進(jìn)制比特?cái)?shù)。在基于不經(jīng)意傳輸?shù)纳鐣扑]中，步驟1對應(yīng)OT乘法協(xié)議計(jì)算推薦得分，步驟2是安全的TopK選擇。在基于同態(tài)加密的社會化推薦方法中，步驟1至步驟3分別對應(yīng)了基于Paillier同態(tài)加密的推薦得分，加法秘密共享及安全的TopK選擇。

表1 復(fù)雜度分析

通過算法1，可以明顯看出，在不經(jīng)意傳輸協(xié)議的步驟1中，雙方共需調(diào)用不經(jīng)意傳輸乘法協(xié)議|Et|次。同時(shí)，由上文可知，在TopK選擇中基本單元包含2個(gè)2-ADD和1個(gè)2-CMP模塊，對于t位的電路輸入，共包含非異或門3t+1個(gè)。因?yàn)椴捎昧司€性時(shí)間復(fù)雜度的隨機(jī)選擇算法[14]來實(shí)現(xiàn)TopK選擇，其平均比較次數(shù)為|I|，所以共需非異或門(3t+1)|I|個(gè)。

在基于同態(tài)加密的社會化推薦方法中，由算法3可知，為了計(jì)算物品得分，Bob共需|U|次加密操作，Alice共需|I|次指數(shù)操作。在步驟2，即加法秘密共享中，Alice共需|I|次加密和指數(shù)操作，Bob需要|I|次解密操作。由于兩方案使用同一TopK協(xié)議，所以復(fù)雜度仍為(3t+1)|I|。下面將通過實(shí)驗(yàn)對兩方案的性能做進(jìn)一步的比較。

5 實(shí)驗(yàn)部分

本文提出了2種方案，都能夠在保證兩參與方私有信息（Gt和Gs）不泄露的前提下，為目標(biāo)用戶提供精確的推薦。在這一部分，將使用4個(gè)公開數(shù)據(jù)集測試所提的方法，數(shù)據(jù)集相關(guān)統(tǒng)計(jì)信息如表2所示。

表2 數(shù)據(jù)集統(tǒng)計(jì)信息

其中，|U|表示用戶個(gè)數(shù)，|I|表示物品個(gè)數(shù)，|Es|是用戶之間的關(guān)聯(lián)邊數(shù)，|Et|表示用戶歷史購買記錄條數(shù)，從表中數(shù)據(jù)可以看出，用戶歷史記錄矩陣相當(dāng)稀疏。本實(shí)驗(yàn)主要包含了4個(gè)數(shù)據(jù)集，Last.fm[1]是一個(gè)相對較小的數(shù)據(jù)集，主要包含了不同用戶對音樂家的收聽習(xí)慣。Flixter.com[2]是一個(gè)電影評分網(wǎng)站。Brightkite.com[3]和Gowalla.com[4]則是基于位置信息的信息分享網(wǎng)站，主要記錄不同用戶在不同地點(diǎn)有多次的登錄行為。

實(shí)驗(yàn)在2.6 GHz CPU，1TB RAM的服務(wù)器上執(zhí)行，軟件環(huán)境為Centos Linux release 7.1，JDK7。

使用Java實(shí)現(xiàn)了Paillier同態(tài)加密系統(tǒng)，實(shí)驗(yàn)中，密鑰空間設(shè)為1 024 bit（1 024 bit相當(dāng)于對稱密鑰方案中80 bit的安全級別，在這個(gè)設(shè)置下，可以忽略由于密碼被攻破而帶來的信息泄露）?；贔GC框架，實(shí)現(xiàn)了安全的TopK選擇協(xié)議。默認(rèn)情況下，推薦數(shù)K設(shè)置為10。

實(shí)驗(yàn)結(jié)果如表3和表4所示，表3和表4分別是方法1和方法2對應(yīng)的時(shí)間統(tǒng)計(jì)。表3中，步驟1對應(yīng)OT乘法協(xié)議計(jì)算推薦得分，步驟2是安全的TopK選擇。表4中包含了3步操作，基于Paillier同態(tài)加密的推薦得分以及得分的秘密共享及安全的TopK選擇。

表3 基于OT乘法的社會化推薦系統(tǒng)時(shí)間統(tǒng)計(jì)

表4 基于同態(tài)加密的社會化推薦系統(tǒng)時(shí)間統(tǒng)計(jì)

結(jié)合算法分析可知，由于矩陣的稀疏度影響，表3中步驟1的時(shí)間主要與非零項(xiàng)相關(guān)。步驟2中時(shí)間和物品數(shù)|I|成正比。由于表4中步驟1推薦得分計(jì)算與|Et|成正比，步驟2加法秘密共享與|I|成正比。

從表中可以看到，除了Flixster外的其他3個(gè)數(shù)據(jù)集上，基于OT乘法的社會化推薦協(xié)議比基于同態(tài)加密的社會化推薦方案更為高效。而Flixster由于矩陣的非零項(xiàng)記錄|Et|遠(yuǎn)大于|I|，所以基于OT乘法的協(xié)議并沒有因?yàn)槭÷约臃孛芄蚕聿僮鞫@得足夠優(yōu)勢。在方法選擇過程中，用戶可以根據(jù)自己的數(shù)據(jù)集特性及要求選擇合適的方案。

6 結(jié)束語

本文提出了2種數(shù)據(jù)隱私保護(hù)的社會化推薦協(xié)議。兩協(xié)議都能夠在保證不泄露兩參與方私有數(shù)據(jù)信息的前提下，完成社會化推薦。其中，基于不經(jīng)意傳輸?shù)纳鐣扑]，計(jì)算代價(jià)較小，適用于對推薦效率要求較高的應(yīng)用?；谕瑧B(tài)加密的社會化推薦，安全程度較高，適用于對數(shù)據(jù)隱私要求較高的應(yīng)用。4組真實(shí)數(shù)據(jù)集實(shí)驗(yàn)表明，本文提出的方案切實(shí)可行，用戶可以根據(jù)自身需求選擇合適的方案。

[1]KONSTAS I,STATHOPOULOS V,JOSE J M.On social networks and collaborative recommendation[A].32nd International ACM SIGIR Conference on Research and Development in Information Retrieval[C].ACM,2009.195-202.

[2] YUAN Q,ZHAO S,CHEN L,et al.Augmenting collaborative recommender by fusing explicit social relationships[A].Workshop on Recommender Systems and the Social Web[C].2009.2009.

[3] JORGENSEN Z,YU T.A privacy-preservingframework for personalized,social recommendations[A].EDBT[C].2014.571-582.

[4] HAN S,NG W K,YU P S.Privacy-preserving singular value decomposition[A].ICDE[C].2009.

[5] CANNY J.Collaborative filtering with privacy[A].Security and Privacy,Proceedings of 2002 IEEE Symposium[C].IEEE,2002.45-57.

[6]MILLER B N,KONSTAN J A,RIEDL J.PocketLens:toward a personal recommender system[J].ACM Transactions on Information Systems(TOIS),2004,22(3):437-476.

[7] POLAT H,DU W.Privacy-preserving collaborative filtering[J].International Journal of Electronic Commerce,2005,9(4):9-35.

[8]BERKOVSKY S,EYTANI Y,KUFLIK T,et al.Enhancing privacy and preserving accuracy of a distributed collaborative filtering[A].2007 ACM Conference on Recommender Systems[C].ACM,2007.9-16.

[9] YAO A.How to generate and exchange secrets[A].Foundations of Computer Science 27thAnnual Symposium on[C].1986.162-167.

[10]LINDELL Y,PINKAS B.A proof of security of Yao's protocol for two-partycomputation[J].Journal of Cryptology,2009,22(2):161-188.

[11]HUANG Y,EVANS D,KATZ J,et al.Faster secure two-party computation using garbled circuits[A]. USENIX Security Symposium[C].2011,201(1).

[12]NAOR M,PINKAS B.Efficient oblivious transfer protocols[A].Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics[C].2001.448-457.

[13]GILBOA N.Two party RSA key generation[A].Advances in Cryptology—CRYPTO'99[C].SpringerBerlin Heidelberg,1999.116-129.

[14]CORMEN T H.Introduction toAlgorithms[M].MIT Press,2009.