數據隱私保護的社會化推薦協議

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

(1.蘇州大學 計算機科學與技術學院，江蘇 蘇州 215000；2.江蘇省軟件新技術與產業化協同創新中心，江蘇 南京 211102)

1 引言

推薦系統是一系列通過對用戶或其購買行為進行分析，從而自動為用戶推薦其可能感興趣的信息和商品的算法集合。協同過濾算法出現以來就受到了廣泛關注，但隨之而來的“冷啟動”問題卻制約了該算法的進一步使用。為解決這一問題，研究學者們提出了基于鄰域的社會化推薦方法[1,2]，該方法指出，將基于社交網絡拓撲圖得到的用戶關系引入到推薦系統中，可以有效解決協同過濾計算過程中由于新用戶缺少歷史行為數據而帶來的“冷啟動”問題。基于鄰域的社會化推薦算法得到普遍關注，同時，大量最新的研究也表明，該算法明顯優于傳統推薦算法。

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

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

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

2 相關背景及問題定義

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

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

定義2用戶社交網絡拓撲圖。如圖1（b）所示，社交網絡拓撲圖Gs=(U,Es)是一個由用戶集合U和用戶關系邊Es構成的無向圖，其中，Es(u,v)表示用戶u和v之間存在聯系。

圖1 用戶歷史行為二分圖和用戶社交網絡拓撲

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

定義3基于鄰域的社會化推薦。假設兩參與方Alice和Bob，Alice擁有用戶歷史行為數據，Bob擁有社交網絡拓撲圖（以及用戶之間相似度度量算法sim），Alice和Bob通過合作計算，為目標用戶u∈U，推薦K個評分最高的物品Ru∈I。

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

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

圖2 傳統和社會化推薦系統

在社會化推薦中，sim(u,v)的計算依賴于社交網絡拓撲圖Gs。為了能夠完成社會化推薦，Alice即電子商務平臺必須利用社交網絡拓撲。出于商業利益或維護用戶隱私的權益，Bob即社交網絡拓撲圖的持有者，并不愿意將私有數據，社交網絡拓撲圖直接提供給Alice使用，保證兩參與方的數據隱私安全是完成社會化推薦的前提。下面將給出保護隱私的社會化推薦的定義。

定義4保護隱私的社會化推薦。假設兩參與方Alice和Bob，Alice擁有用戶歷史行為數據，Bob擁有社交網絡拓撲圖以及用戶之間相似度度量算法sim，Alice和Bob通過合作計算，為目標用戶u∈U，推薦K個評分最高的物品Ru∈I，計算過程中，雙方私有信息（如Gt和Gs）不能暴露給對方。

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

3 保護隱私的社會化推薦系統

針對社會化推薦系統需要在兩方隱私數據上進行協同計算，本文提出了2種數據隱私保護的社會化推薦協議，可以同時保護推薦系統服務提供商和社交網絡服務提供商的數據隱私。其中，基于不經意傳輸的社會化推薦，計算代價較小，適用于對推薦效率要求較高的應用。基于同態加密的社會化推薦，安全程度較高，適用于對數據隱私要求較高的應用。下面是2個協議的詳細介紹。

3.1 基于不經意傳輸的社會化推薦

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

根據定義4，Alice持有數據Gt，Bob持有數據Gs。對于目標用戶u，Bob可以根據事先確定好的相似度計算方法計算出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)}，根據式（1）可知，對于目標用戶u而言，物品i的推薦得分s(u,i)為對應位積之和。具體算法如下。

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

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

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

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

接下來，需要從所有候選物品中，挑選出K個推薦得分最高的物品推薦給用戶。因為最終只需要將K個推薦得分最高的物品推薦給目標用戶即可，K個物品之間的排列順序并不影響推薦，所以采用線性時間復雜度的隨機選擇算法[14]來實現TopK選擇。

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

算法2安全的TopK選擇算法

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

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

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

3.2 基于同態加密的社會化推薦

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

Paillier同態加密系統[8]是Paillier于1999年發明的用于公鑰加密的概率非對稱算法。在本文中，用E(x)表示對明文x的Paillier加密函數，D(x)表示對密文x的Paillier解密函數，證明參見文獻[8]。該加密系統具有加法同態性質，即2個密文乘積的解密值，與兩密文對應明文的和相等；密文的k次冪解密值，與k和對應明文的乘積相等；Paillier加密系統的語義安全特性保證了攻擊者無法由給定密文導出任何相關明文信息。基于同態加密的推薦得分算法如下。

算法3基于Paillier同態機密的推薦得分算法

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

由于w(v,i)是Alice端的數據，所以Alice可以自動過濾掉w(uj,i)≠0的項，減少不必要的計算開銷。基于Paillier完成推薦得分計算后，結果以密文形式由Alice持有，密鑰由Bob端持有。

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

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

4 理論分析

攻擊模型：本文假設Alice和Bob都是半誠實的，兩方將嚴格的執行協議，但是計算過程中兩方也會盡可能地根據中間信息推測出更多的額外信息。針對惡意攻擊模型的安全協議雖然存在，但是計算代價過大，在實際中并不實用。而針對半誠實模型的安全協議不但能夠實現高效的計算，而且對惡意攻擊模型下的安全協議研究具有重要參考價值。

4.1 安全性分析

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

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

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

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

綜上，基于不經意傳輸的社會化推薦方法和基于同態加密的社會化推薦方法，都能在保證兩方（推薦系統服務提供商和社交網絡服務提供商）數據隱私的前提下，為目標用戶提供精確的推薦。

4.2 復雜度分析

如表1所示為兩方案的復雜度分析，其中，|U|表示用戶個數，|I|表示物品個數，|Et|表示用戶歷史購買記錄條數，t為推薦得分的二進制比特數。在基于不經意傳輸的社會化推薦中，步驟1對應OT乘法協議計算推薦得分，步驟2是安全的TopK選擇。在基于同態加密的社會化推薦方法中，步驟1至步驟3分別對應了基于Paillier同態加密的推薦得分，加法秘密共享及安全的TopK選擇。

表1 復雜度分析

通過算法1，可以明顯看出，在不經意傳輸協議的步驟1中，雙方共需調用不經意傳輸乘法協議|Et|次。同時，由上文可知，在TopK選擇中基本單元包含2個2-ADD和1個2-CMP模塊，對于t位的電路輸入，共包含非異或門3t+1個。因為采用了線性時間復雜度的隨機選擇算法[14]來實現TopK選擇，其平均比較次數為|I|，所以共需非異或門(3t+1)|I|個。

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

5 實驗部分

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

表2 數據集統計信息

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

實驗在2.6 GHz CPU，1TB RAM的服務器上執行，軟件環境為Centos Linux release 7.1，JDK7。

使用Java實現了Paillier同態加密系統，實驗中，密鑰空間設為1 024 bit（1 024 bit相當于對稱密鑰方案中80 bit的安全級別，在這個設置下，可以忽略由于密碼被攻破而帶來的信息泄露）。基于FGC框架，實現了安全的TopK選擇協議。默認情況下，推薦數K設置為10。

實驗結果如表3和表4所示，表3和表4分別是方法1和方法2對應的時間統計。表3中，步驟1對應OT乘法協議計算推薦得分，步驟2是安全的TopK選擇。表4中包含了3步操作，基于Paillier同態加密的推薦得分以及得分的秘密共享及安全的TopK選擇。

表3 基于OT乘法的社會化推薦系統時間統計

表4 基于同態加密的社會化推薦系統時間統計

結合算法分析可知，由于矩陣的稀疏度影響，表3中步驟1的時間主要與非零項相關。步驟2中時間和物品數|I|成正比。由于表4中步驟1推薦得分計算與|Et|成正比，步驟2加法秘密共享與|I|成正比。

從表中可以看到，除了Flixster外的其他3個數據集上，基于OT乘法的社會化推薦協議比基于同態加密的社會化推薦方案更為高效。而Flixster由于矩陣的非零項記錄|Et|遠大于|I|，所以基于OT乘法的協議并沒有因為省略加法秘密共享操作而獲得足夠優勢。在方法選擇過程中，用戶可以根據自己的數據集特性及要求選擇合適的方案。

6 結束語

本文提出了2種數據隱私保護的社會化推薦協議。兩協議都能夠在保證不泄露兩參與方私有數據信息的前提下，完成社會化推薦。其中，基于不經意傳輸的社會化推薦，計算代價較小，適用于對推薦效率要求較高的應用。基于同態加密的社會化推薦，安全程度較高，適用于對數據隱私要求較高的應用。4組真實數據集實驗表明，本文提出的方案切實可行，用戶可以根據自身需求選擇合適的方案。

[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.