基于同態(tài)加密的隱私保護推薦算法

潘 峰， 劉文超， 楊曉元,2， 周潭平,2， 涂廣升

(1.武警工程大學 密碼工程學院 陜西 西安 710086； 2.網(wǎng)絡與信息安全武警部隊重點實驗室 陜西 西安 710086)

0 引言

互聯(lián)網(wǎng)技術的進一步發(fā)展引起信息過載問題：信息量的大幅增長使用戶難以從過量信息中獲取所需信息。因此過濾用戶不需要的信息成為亟須解決的開放性問題。解決信息超載的一種重要途徑是使用搜索引擎，但是存在如必須主動搜索、沒有個性化推薦等問題。推薦算法是目前被廣泛應用的一種信息過濾的手段，根據(jù)用戶或者項目(如音樂、商品、視頻等)的特征建立模型用以預測用戶對其尚未考慮項目的偏好。推薦算法的出現(xiàn)，從大量可用項目中預測了用戶需求，使用戶有更合適的選擇，產(chǎn)生了巨大的經(jīng)濟效益。好的推薦算法能夠吸引用戶長期使用。因此，推薦算法從用戶角度考慮，可以為用戶提供個性化的服務，而從服務提供商角度考慮，則能提高用戶忠誠度，防止用戶流失。

好的推薦系統(tǒng)需要提供個性化和準確的推薦，因此需要盡可能多地掌握用戶的個性化信息。用戶提供越多的信息，則獲得的推薦越準確，但是泄露的隱私信息也就越多，從而導致推薦系統(tǒng)與用戶隱私保護之間的矛盾[1]。常見推薦系統(tǒng)的隱私保護方法包括：k-anonymous方法[2]、分布式推薦系統(tǒng)[3]和代理組件[4]等設計架構、同態(tài)加密[5]等手段。隨著同態(tài)加密效率的提高，涌現(xiàn)出許多基于同態(tài)加密的研究成果[6-7]，使用同態(tài)加密來保護推薦系統(tǒng)中的用戶隱私將成為一種越來越有前景的方法。

本文提出了一種基于TW16協(xié)議的同態(tài)隱私保護推薦算法，TW16是文獻[8]提出的一種基于好友關系的推薦協(xié)議，該協(xié)議可以基于用戶好友以及陌生人的評分來對用戶未評分的項目進行預測，并使用同態(tài)加密技術保護用戶的隱私。本文在該方案基礎上，通過增加活躍用戶的評分權值、對參數(shù)設置進行優(yōu)化和增加計算緩存的方法，構造并實現(xiàn)了一種準確高效的基于同態(tài)加密的隱私保護推薦協(xié)議。

1 推薦算法

本節(jié)對基于好友關系的推薦算法和類同態(tài)加密方案(somewhat homomorphic encryption，SHE)進行介紹。

X代表數(shù)據(jù)集，x←X表示從X中隨機均勻地選取一個x，|X|表示X的大小。如果χ是一個分布，那么s←χ表示s是從χ分布中抽樣得到的。給定兩個向量X和Y，使用X·Y表示兩個向量的內(nèi)積，使用‖X‖表示X的歐氏距離。

在推薦算法中，推薦條目集合表示為I=(1,2,…,b,…,M)，用戶x的評分表示為向量Rx=(rx,1,…,rx,b,…,rx,M)，其評分r∈{0,1,2,3,4,5}。如果某個條目i尚未被評分，則其評分值rx,i=0，評分結(jié)果為一個矩陣。推薦算法用來預測用戶尚未評分的rx,i。

給定兩個用戶x和y，其對應的評分向量Rx和Ry，余弦相似度定義為

sim(x,y)=(Rx·Ry)/‖Rx‖·‖Ry‖。

本文使用平均絕對誤差(mean absolute error，MAE)來衡量推薦算法的推薦是否準確，

2 基于同態(tài)加密的隱私保護推薦算法

在本節(jié)中，首先對TW16中描述的推薦算法進行介紹，然后說明對該系統(tǒng)進行的改進和優(yōu)化。

給定一個用戶u和一個陌生人集合Tu，輸入陌生人集合Tu對項目b的評價，預測算法定義為

(1)

給定一個用戶u和一個好友集合Fu，輸入好友集合Fu對項目b的評價，預測算法定義為

(2)

(3)

2.1 中心化的單預測協(xié)議

推薦算法中有大量的用戶參與提供數(shù)據(jù)，用戶之間并不直接聯(lián)系，故需要一個中心化的服務提供商來溝通參與協(xié)議的所有用戶，并向請求推薦結(jié)果的用戶提供服務。系統(tǒng)中存在中心化的服務提供商和大量的用戶，用戶好友之間可以單向關注也可雙向關注，簡化的系統(tǒng)架構圖如圖1。

圖1 中心化的推薦算法結(jié)構圖Figure 1 Structure of centralized recommendation algorithm

當用戶想要預測某未評分項目b的預測評分時，進行如下協(xié)議。

參考上文中的預測算法，協(xié)議共分為3個階段。第1階段，服務提供商根據(jù)公式(1)獲取陌生人的加密輸入；第2階段，服務提供商根據(jù)公式(2)獲取好友的加密輸入；第3階段，用戶u根據(jù)公式(3)可得知預測結(jié)果，而服務提供商沒有獲取用戶隱私信息。

用戶u生成二進制向量Ib，第b個元素為1，使用SHE加密算法采用逐比特加密的方式將Ib加密為[Ib]u=Enc(PKu,Ib)=([Ib]u(1),…, [Ib]u(M))并將結(jié)果發(fā)送到服務器。服務器再將PKu發(fā)送至隨機選擇且愿意參與計算的陌生人集Tu，將[Ib]u轉(zhuǎn)發(fā)給Tu中的每個陌生人。每個陌生人t使用PKu和(Rt,Qt)，作如下同態(tài)運算，

用戶u將加密后的權重[wu,f]u=Enc(PKu,wu,f)發(fā)送到服務提供商，服務提供商向用戶的好友f∈Fu發(fā)送[wu,f]u和[Ib]u，f使用PKu，[Ib]u，[wu,f]u和(Rf,Qf)計算

完成后將結(jié)果發(fā)送給服務提供商。

服務提供商首先計算[nT]u、[dT]u、[nF]u、[dF]u，然后計算[X]u和[Y]u。

服務提供商將結(jié)果發(fā)回給用戶u，u解密后獲得結(jié)果。

2.2 中心化的前n項預測協(xié)議

與單預測協(xié)議類似，當用戶想獲取前n個未評分項目的評分時，進行如下協(xié)議。

用戶u將加密后的權重[wu,f]u=Enc(PKu,wu,f)發(fā)送給每個朋友f∈Fu，好友f使用PKu、[wu,f]u和(Rf,Qf)計算

并將結(jié)果發(fā)回服務提供商。

用戶u和服務提供商進行如下交互：用戶u生成兩個矩陣MX、MY，生成M·M單位矩陣; 隨機置換列以獲得MY;對于每個項目b，若已被評分，則將MY第b列中的元素1替換為0，得到矩陣MX。用戶u逐個元素加密矩陣，并將加密結(jié)果[MX]u、[MY]u發(fā)送到服務提供商，然后進行計算。

服務提供商首先按照單預測協(xié)議中的方法計算[nT]u、[dT]u、[nF]u、[dF]u、[X]u和[Y]u，然后根據(jù)公式(3)計算

服務提供商置換密文向量(([X1]u,[Y1]u),([X2]u,[Y2]u),…，([XM]u′[YM]u)):

([U1]u,[U2]u,…,[UM]u)=[MX]u·([X1]u[X2]u,…,[XM]u)T，

([V1]u′[V2]u,…,[VM]u)=[MY]u·([Y1]u′[Y2]u,…,[YM]u)T。

元素之間的加法和乘法以同態(tài)運算函數(shù)的加法和乘法進行計算，密文矩陣和密文向量的乘法以標準方式進行。服務提供商使用密文上的比較協(xié)議，將Ui/Vi(1≤i≤|B|)進行排序。然后服務提供商將Top-n的索引發(fā)送給用戶u，用戶u解密后即可恢復真實的索引。

2.3 去中心化的預測協(xié)議

圖2 去中心化的推薦算法結(jié)構圖Figure 2 Structure of decentralized recommendation algorithm

半誠實的服務提供商往往是中心化的預測協(xié)議中的弱點，所以可以通過去除中心化的服務提供商，讓用戶之間進行溝通的方式來減少隱私泄露的可能性。假設所有用戶在推薦算法中被唯一標記，并且用戶之間共享社交網(wǎng)絡圖SG。在協(xié)議初始化階段，用戶u使用SHE方案生成其公私鑰對(PKu,SKu)并公開其公鑰以供他人驗證。用戶u生成其評級向量Ru和社交圖SG，并為其每個朋友f∈Fu分配權重wu,f。其他用戶也執(zhí)行相同的操作。在本協(xié)議中，用戶u的好友的好友(FoF)作為u的陌生人備選集合，系統(tǒng)結(jié)構的示意圖如圖2。去中心化的預測協(xié)議計算如下。

陌生人t′收到計算結(jié)果后，進行如下運算：

① 同中心化協(xié)議類似，計算[nT]u、[dT]u、[nF]u、[dF]u、[X]u和[Y]u；② 計算得到結(jié)果。

2.4 安全性分析

在基本安全模型中，假定服務提供者是半誠實的，將遵循協(xié)議規(guī)范并且不作為用戶參與協(xié)議。此外，用戶信任他的朋友是半誠實的。對于用戶之間的通信信道，假設所有通信在完整性和機密性方面受到保護(具有前向保密性)。在最壞情況下的安全模型中，假設某些朋友可能會受到攻擊。

本文中的推薦系統(tǒng)在兩個模型中都是安全的，所有計算都是在用戶u的公鑰下以密文形式完成的，并且在協(xié)議中服務提供商不為SHE加密方案生成公私鑰對，因此，協(xié)議避免了密鑰恢復攻擊。

在給定的安全模型中，推薦系統(tǒng)的信息泄露主要取決于參數(shù)α和β的大小以及陌生人集合的大小，若α/(α+β)增大，陌生人集合選擇較小，則來自用戶好友的信息比重更高，隱私信息更容易泄露。在協(xié)議中，用戶u不與其他用戶進行通信，因此u無法確定某特定用戶是否參與計算；每次預測的陌生人集合都是隨機選擇，所以攻擊者無法利用累積的信息進行攻擊；用戶的評分r∈{0,1,2,3,4,5}，因此已知的某個評分不能推斷出該評分來自于哪個用戶。

3 實驗

通過實驗對本文所提出的改進與預測算法的準確性進行測試。數(shù)據(jù)集由MovieTweetings數(shù)據(jù)集構建而來(https:∥github.com/lux-jwang/Experiments/tree/master/code2016)。MovieTweetings為電影評分數(shù)據(jù)，本文所用測試數(shù)據(jù)集為FMT和10-FMT數(shù)據(jù)集，共包含359 908個評分、35 456個用戶和20 156個條目。在FMT數(shù)據(jù)集中，每個用戶至少有1個朋友，每個朋友至少有1個評級；在10-FMT數(shù)據(jù)集中，每個用戶至少有10個朋友，每個朋友至少有10個評級。將每個數(shù)據(jù)集分為訓練集和測試集，其中訓練數(shù)據(jù)占80%，測試數(shù)據(jù)占20%。表1和表2描述了推薦算法在10-FMT數(shù)據(jù)集上的MAE值。軟硬件環(huán)境為：系統(tǒng)為Ubuntu 18.04；處理器為Inter(R)Core(TM)i7-3610QM；內(nèi)存為8 G。

表1 中心化預測算法在10-FMT數(shù)據(jù)集中的MAE值Table 1 The MAE of the centralized prediction algorithm in the 10-FMT data set

表2 去中心化預測算法在10-FMT數(shù)據(jù)集中的MAE值Table 2 The MAE of the decentralized prediction algorithm in the 10-FMT data set

首先在數(shù)據(jù)集中對算法的準確性進行測試。

從表1和表2中可以看出，推薦算法的MAE值隨著好友用戶參與的比重和用戶好友集的增加而減少，預測準確度增加。相比于文獻[8]方案，準確率有所提升。

將運算中常用的數(shù)據(jù)進行緩存，修改傳遞參數(shù)中一些多余的循環(huán)方式對代碼進行優(yōu)化，算法的運算效率提升如表3、表4所示。

表3 數(shù)據(jù)處理階段執(zhí)行時間Table 3 Data processing time 單位：s

表4 算法運行階段執(zhí)行時間Table 4 Algorithm execution time 單位：s

通過實驗證明，協(xié)議中數(shù)據(jù)預處理過程和算法執(zhí)行過程中的效率都得到提升，單預測協(xié)議運算時間減少了13.4%，Top-n協(xié)議運算時間減少了12.7%。

4 結(jié)束語

本文構造并實現(xiàn)了一種準確高效的基于同態(tài)加密的隱私保護推薦協(xié)議，針對推薦算法中存在隱私泄露問題，在TW16方案基礎上，增加活躍用戶的評分權值提升推薦協(xié)議預測的準確性，對參數(shù)設置進行優(yōu)化,提升協(xié)議的效率，并對方案進行實驗驗證，結(jié)果表明推薦算法的準確性和效率均有所提升。今后可對本文的基礎同態(tài)加密方案進行優(yōu)化，進一步研究方案效率的提升。