一種基于分布式架構(gòu)的隱私保護(hù)協(xié)同過(guò)濾算法

崔煒榮，徐龍華，李 寶

（1.安康學(xué)院 電子與信息工程學(xué)院，陜西 安康 725000；2.安康學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，陜西 安康 725000）

1 引言

在信息過(guò)載的當(dāng)今社會(huì)，“推薦系統(tǒng)”已無(wú)處不在。它隱藏在各大新聞、視頻、購(gòu)物平臺(tái)之后，悄無(wú)聲息地收集著人們的瀏覽記錄，及時(shí)將用戶感興趣的信息展現(xiàn)在用戶眼前。由于需要利用用戶的歷史行為信息，甚至其人口統(tǒng)計(jì)屬性信息，推薦系統(tǒng)在給用戶帶來(lái)便利的同時(shí)也面臨著嚴(yán)峻的隱私安全問(wèn)題[1]。其主要的隱私風(fēng)險(xiǎn)在于，一方面平臺(tái)可以直接利用用戶所提交的數(shù)據(jù)獲得用戶的個(gè)人身份、興趣愛(ài)好等敏感信息；另一方面基于推薦系統(tǒng)所收集數(shù)據(jù)的稀疏特性，攻擊者可利用推薦系統(tǒng)發(fā)布的聚合數(shù)據(jù)，有效推測(cè)出用戶的敏感信息[2]。在個(gè)人隱私安全備受矚目的當(dāng)今社會(huì)，如何在保證可用性的前提下提供可靠的隱私保障成了推薦系統(tǒng)研究的熱點(diǎn)問(wèn)題。

矩陣分解協(xié)同過(guò)濾（Matrix Factorization Collaborative Filtering，MFCF）是構(gòu)建推薦系統(tǒng)的主流算法之一[3]。本文基于常用的MFCF算法，設(shè)計(jì)了一種可有效保護(hù)用戶隱私的協(xié)同過(guò)濾算法，稱(chēng)之為DSAMF（Distributed Secure Aggregation Matrix Factorization）。該算法采用了分布式架構(gòu)，并且基于同態(tài)加密技術(shù)實(shí)現(xiàn)了模型計(jì)算過(guò)程中梯度更新信息的安全聚合，從而在保證推薦準(zhǔn)確性的同時(shí)，有效保護(hù)了用戶隱私。

2 相關(guān)工作

混淆和擾動(dòng)是推薦系統(tǒng)中實(shí)現(xiàn)隱私保護(hù)的基本思路。該方式通過(guò)在用戶數(shù)據(jù)中增加偽造值（加擾）以達(dá)到向服務(wù)器隱藏用戶真實(shí)數(shù)據(jù)的目的[4-5]。然而，偽造值的引入犧牲了推薦系統(tǒng)的準(zhǔn)確性，而且其安全性沒(méi)有得到嚴(yán)格的證明。

差分隱私保護(hù)的原理在于通過(guò)在計(jì)算中引入特定分布的噪聲來(lái)降低用戶輸入的可分辨性。與簡(jiǎn)單的混淆和擾動(dòng)不同，差分隱私保護(hù)能夠提供可度量和可證明的隱私保障。在推薦系統(tǒng)中引入差分隱私保護(hù)機(jī)制，同樣需要在安全性和準(zhǔn)確性之間做出權(quán)衡[6-10]。

同態(tài)加密技術(shù)能夠使用戶通過(guò)直接對(duì)密文運(yùn)算以達(dá)到預(yù)期的明文計(jì)算效果，被廣泛應(yīng)用于各類(lèi)隱私保護(hù)場(chǎng)景中。使用同態(tài)加密技術(shù)避免了加擾技術(shù)對(duì)推薦準(zhǔn)確性的影響，但又帶來(lái)了效率和能耗方面的較大開(kāi)銷(xiāo)[11-13]。

本文所設(shè)計(jì)的算法DSAMF是基于同態(tài)加密技術(shù)以及分布式計(jì)算架構(gòu)來(lái)實(shí)現(xiàn)MFCF過(guò)程中的用戶隱私保護(hù)。與現(xiàn)有算法區(qū)別在于，DSAMF除了能實(shí)現(xiàn)用戶數(shù)據(jù)的保護(hù)外，還可以實(shí)現(xiàn)模型的保護(hù)以及用戶評(píng)分“存在性”的保護(hù)。

3 同態(tài)加密技術(shù)

同態(tài)加密（Homomorphic Encryption）被廣泛應(yīng)用于安全計(jì)算領(lǐng)域。使用同態(tài)加密機(jī)制，可以將針對(duì)明文的特定代數(shù)運(yùn)算轉(zhuǎn)變?yōu)獒槍?duì)密文的特定代數(shù)運(yùn)算。本文使用了Pailliers同態(tài)加密體系，與其他同態(tài)加密方法相比，Pailliers同態(tài)加密體系更加簡(jiǎn)單高效，因此被廣泛使用。

3.1 Pailliers同態(tài)加密體系

Pailliers同態(tài)加密體系由三個(gè)原語(yǔ)組成。

（1）密鑰生成：給定安全參數(shù)k，選擇兩個(gè)素?cái)?shù)p和q(|p|=|q|)，計(jì)算λ=lcm(p-1,q-1)。定義函數(shù)L(u)=(u-1)/n，其中n=pq。選擇一個(gè)循環(huán)群生成元g，計(jì)算μ=(L(g2mod n2))-1mod n。所生成的公鑰為(n,g)，相應(yīng)的私鑰為(λ,μ)。

（3）解密：給定密文C，私鑰(λ,μ)，明文mod n。

3.2 Pailliers加密體系的同態(tài)性質(zhì)

Pailliers加密體系的同態(tài)性質(zhì)為：

以上同態(tài)性質(zhì)可簡(jiǎn)化為：

4 系統(tǒng)模型構(gòu)建及隱私保護(hù)目標(biāo)設(shè)計(jì)

4.1 系統(tǒng)模型及假設(shè)

整個(gè)推薦系統(tǒng)由多個(gè)用戶和一個(gè)服務(wù)器組成。令用戶集合為U={u1,u2,...,um}，物品集合為V={v1,v2,...,vm}，服務(wù)器為S。用戶對(duì)物品的評(píng)分矩陣為R∈R|U|×|V|，rij∈R 為 ui對(duì) vj的評(píng)分。系統(tǒng)的輸入為用戶評(píng)分矩陣R，輸出為預(yù)測(cè)模型M=(W,H)。其中，W為用戶隱藏因子矩陣，H為物品隱藏因子矩陣。R=WHT為評(píng)分預(yù)測(cè)矩陣，其應(yīng)具有較好的擬合和泛化能力。對(duì)于上述模型，我們假設(shè)：（1）用戶評(píng)分只保存在對(duì)應(yīng)的客戶端；（2）用戶之間可以通過(guò)額外的安全信道進(jìn)行點(diǎn)對(duì)點(diǎn)通信。

4.2 隱私保護(hù)目標(biāo)

本文所設(shè)計(jì)的算法應(yīng)滿足如下隱私保護(hù)需求：

（1）模型保護(hù)：任意用戶和服務(wù)器都無(wú)法獲知完整的M，也無(wú)法通過(guò)所持有的部分信息推斷出M的完整內(nèi)容。

（2）評(píng)分保護(hù)：在模型的訓(xùn)練過(guò)程中，服務(wù)器無(wú)法獲知用戶的評(píng)分記錄。每一個(gè)用戶也無(wú)法獲知其他用戶的評(píng)分記錄。

（3）存在性保護(hù)：在模型的訓(xùn)練過(guò)程中，服務(wù)器無(wú)法獲知用戶是否對(duì)某一物品進(jìn)行了評(píng)分。每一個(gè)用戶也無(wú)法獲知其他用戶是否對(duì)某一物品進(jìn)行了評(píng)價(jià)。

5 算法設(shè)計(jì)

5.1 總體設(shè)計(jì)

為了實(shí)現(xiàn)上述隱私保護(hù)目標(biāo)，本算法采用了分布式架構(gòu)，即用戶和服務(wù)器通過(guò)多輪迭代，共同參與了矩陣分解，如圖1所示。

圖1 總體設(shè)計(jì)

在初始化過(guò)程中，由服務(wù)器生成同態(tài)加密密鑰對(duì)，并將加密公鑰廣播給每個(gè)用戶。每輪迭代分為三個(gè)階段。第一階段：各個(gè)客戶端ui從服務(wù)器下載更新過(guò)的H，之后利用保存在本機(jī)上的Ri和wi基于SGD算法計(jì)算wi的更新梯度grad(wi)以及其評(píng)價(jià)過(guò)的每一個(gè)物品所對(duì)應(yīng)hj的更新梯度。接著，ui使用grad(wi)更新wi，并用同態(tài)加密密鑰對(duì)每一個(gè)grad(hj)進(jìn)行加密。第二階段：用戶間隨機(jī)選舉一位作為安全聚合端，由其完成針對(duì)各個(gè)hi的加密梯度更新信息聚合，并上傳至服務(wù)器。第三階段：服務(wù)器對(duì)聚合信息進(jìn)行解密并更新H，至此進(jìn)入下一輪迭代。

5.2 系統(tǒng)初始化

在初始化階段，各個(gè)用戶生成隨機(jī)用戶隱藏因子向量wi，服務(wù)器生成隨機(jī)物品隱藏因子矩陣H。此外，服務(wù)器需要生成同態(tài)加密密鑰對(duì)(ck,pk)，并將pk廣播給各個(gè)用戶。

5.3 梯度更新信息計(jì)算

對(duì)于所求的目標(biāo)模型M=(W,H)，矩陣分解的目的在于基于給定的維度k找到最優(yōu)的W∈R|U|×k和H∈R|V|×k，使得HWT≈R。也就是說(shuō)，找到使損失函數(shù)L(W,H)值最小的W和H：

上式中，λ為歸一化參數(shù)，用于防止過(guò)擬合。在本文中，使用隨機(jī)梯度下降（Stochastic Gradient Descent，SGD）算法求解上式，其每輪迭代的更新規(guī)則為：

根據(jù)式（2），每輪迭代，用戶ui首先需從服務(wù)器端下載H。假設(shè)用戶評(píng)分過(guò)的物品集合為T(mén)={vj1,vj2,...,vjl}，對(duì)于每一個(gè)hjk∈H，客戶端進(jìn)行如下計(jì)算：

（1）計(jì)算 eijk，

（2）計(jì)算grad(wi)jk和grad(hjk)。

上述步驟中，Encpk(grad(hjk))表示用服務(wù)器生成的同態(tài)加密公鑰pk對(duì)梯度更新值grad(hjk)進(jìn)行加密運(yùn)算。

5.4 安全聚合

每輪迭代中，為了避免服務(wù)器通過(guò)用戶端上傳的梯度更新信息推測(cè)出用戶評(píng)價(jià)過(guò)哪些物品，客戶端會(huì)對(duì)求平均值后，再將聚合結(jié)果上傳至服務(wù)器。具體步驟為：

（1）混淆值加入：假設(shè)對(duì)于任意用戶ui，其未評(píng)價(jià)的物品集合為在此步驟中，用戶ui從中隨機(jī)選取個(gè)物品，生成對(duì)應(yīng)的s個(gè)Encpk(0)，加入到中。

（2）聚合器選舉：用戶之間通過(guò)分布式選舉程序從U={u1,u2,...,um}中選舉出某一用戶作為聚合節(jié)點(diǎn)?？紤]到效率和安全性的權(quán)衡，選舉可以每y輪迭代進(jìn)行一次。

（3）安全聚合：假設(shè)聚合節(jié)點(diǎn)為ua，其他用戶ui將發(fā)送給ua。為了區(qū)別起見(jiàn)，令用戶ui生成的加密梯度更新值集合為，集合中針對(duì)某一物品vj的加密梯度更新信息為。聚合節(jié)點(diǎn)ua進(jìn)行如下運(yùn)算：

算法1同態(tài)聚合

聚合節(jié)點(diǎn)完成上述計(jì)算后，將結(jié)果上傳至服務(wù)器，由服務(wù)器解密并更新H。

5.5 更新H

6 安全性分析

本文所設(shè)計(jì)的算法兼顧了預(yù)測(cè)模型、用戶評(píng)分和用戶評(píng)分存在性三方面的隱私保護(hù)需求。

6.1 模型保護(hù)

算法采取了分布式架構(gòu)，對(duì)于模型M=(W,H)而言，W中的每一個(gè)行向量wi都保存在對(duì)應(yīng)的用戶ui端。對(duì)于服務(wù)器而言，在整個(gè)迭代過(guò)程中，其僅僅能夠獲知針對(duì)hj的更新信息。此外，由于該信息是多個(gè)用戶針對(duì)同一hj的聚合，因此服務(wù)器無(wú)法從中推測(cè)出具體的用戶隱藏因子向量。對(duì)于每個(gè)用戶ui而言，雖然其能夠獲得H，但由于其無(wú)法得知其他用戶的wi'(i≠i′)因此無(wú)法獲知完整的W。根據(jù)上述分析，無(wú)論是服務(wù)器還是用戶，都無(wú)法獲知W，因此能夠?qū)崿F(xiàn)對(duì)M的保護(hù)。

6.2 用戶評(píng)分保護(hù)

用戶評(píng)分透露了用戶的喜好，是推薦系統(tǒng)所涉及的重要隱私數(shù)據(jù)。本算法中，評(píng)分矩陣R沒(méi)有集中存放，其每一行Ri∈R由對(duì)應(yīng)的用戶ui保存。在每輪迭代過(guò)程中，Ri只參與計(jì)算預(yù)測(cè)誤差eij。因此，服務(wù)器在這個(gè)模型計(jì)算過(guò)程中，無(wú)法獲知用戶的評(píng)分矩陣，每個(gè)用戶也無(wú)法獲知其他用戶的評(píng)分向量，用戶評(píng)分得以保護(hù)。

6.3 存在性保護(hù)

在本算法中，安全聚合步驟是實(shí)現(xiàn)存在性保護(hù)的關(guān)鍵。舉例而言，如果省略安全聚合步驟，客戶端ui將梯度更新信息grad(hj)直接發(fā)放服務(wù)器，則服務(wù)器至少可以知道ui對(duì)hj進(jìn)行了評(píng)分。而通過(guò)安全聚合步驟，服務(wù)器接收到的是來(lái)自多個(gè)用戶針對(duì)同一hj的梯度更新值聚合，因此實(shí)現(xiàn)了針對(duì)服務(wù)器端的用戶評(píng)分存在性保護(hù)。此外，在安全聚合步驟中，通過(guò)在用戶加密梯度更新值集合中加入隨機(jī)0值以及隨機(jī)選取聚合節(jié)點(diǎn)兩個(gè)操作，避免了評(píng)分存在性在用戶之間的泄露。

7 實(shí)驗(yàn)結(jié)果與分析

基于所描述的算法設(shè)計(jì)，我們使用Python3.6+TensorFlow2.0開(kāi)發(fā)了系統(tǒng)原型，測(cè)試了模型計(jì)算的收斂效率并與有關(guān)學(xué)者提出的SDMF方法[14]進(jìn)行了比較。實(shí)驗(yàn)方法和結(jié)果如下。

7.1 數(shù)據(jù)集及實(shí)驗(yàn)方法

實(shí)驗(yàn)數(shù)據(jù)集為：MovieLens數(shù)據(jù)集ML-100K和ML-1M，Netflix數(shù)據(jù)子集（包含10000個(gè)用戶和5000個(gè)物品）。我們將每一個(gè)數(shù)據(jù)集隨機(jī)劃分為占比80%和訓(xùn)練集和占比20%的測(cè)試集。具體的超參數(shù)設(shè)置為：K=50，學(xué)習(xí)速率分別為5×10-6(ML-100K)，5×10-7(Netflix)。對(duì)于 SDMF，我們選取了作為兩組差分隱私配置參數(shù)。

7.2 結(jié)果與分析

實(shí)驗(yàn)結(jié)果如圖2所示。SDMF算法主要應(yīng)用了差分隱私保護(hù)的思想，通過(guò)在訓(xùn)練過(guò)程中加入總體可控的噪聲來(lái)實(shí)現(xiàn)對(duì)個(gè)體數(shù)據(jù)的保護(hù)。該算法的參數(shù)表示所要達(dá)到的差分隱私保護(hù)強(qiáng)度。越小，則差分隱私保障越強(qiáng)，相應(yīng)的預(yù)測(cè)準(zhǔn)確度就越低。圖2中的實(shí)驗(yàn)數(shù)據(jù)說(shuō)明了這一點(diǎn)。同時(shí)，圖2也清晰地表明，DSAMF的預(yù)測(cè)準(zhǔn)確度和收斂速度遠(yuǎn)遠(yuǎn)高于SDMF。這是因?yàn)獒槍?duì)同樣的隱私保護(hù)目標(biāo)，DSAMF采用了同態(tài)加密的思路。由于沒(méi)有在系統(tǒng)中引入干擾噪聲，所以能夠在保護(hù)隱私的同時(shí)最大限度地保障推薦準(zhǔn)確度。

圖2 實(shí)驗(yàn)結(jié)果

8 結(jié)語(yǔ)

針對(duì)協(xié)同過(guò)濾推薦系統(tǒng)中的隱私保護(hù)問(wèn)題，本文設(shè)計(jì)了DSAMF算法。在DSAMF中，矩陣分解由各個(gè)客戶端和服務(wù)器協(xié)作完成。整個(gè)模型訓(xùn)練過(guò)程中，服務(wù)器僅僅獲得針對(duì)物品隱藏因子向量的聚合梯度更新，而每個(gè)用戶僅能獲知更新后的物品隱藏因子向量和來(lái)自其他用戶的加密梯度更新值。因此DSAMF算法能夠有效地實(shí)現(xiàn)模型、用戶評(píng)分記錄、用戶評(píng)分存在性的保護(hù)。今后還需要針對(duì)如何進(jìn)一步提高模型的準(zhǔn)確度和生成效率展開(kāi)研究，以期在安全性和效率兩方面達(dá)到更優(yōu)的權(quán)衡。