推薦系統的隱私保護研究進展

周 俊 董曉蕾 曹珍富,2,3

1(上海市高可信計算重點實驗室(華東師范大學) 上海 200062) 2(鵬城實驗室網絡空間安全研究中心 廣東深圳 518055) 3(上海智能科學與技術研究院(同濟大學) 上海 200092)

近些年來，無線通信與移動計算的迅猛發展使得各類在線應用軟件日益成為人們日常生活的重要組成部分.這些新興的網絡應用服務在滿足用戶信息需求的同時也引發了信息過載問題，用戶往往需要花費大量時間和精力從海量數據信息中篩選出對自己有用的信息[1-2].推薦系統是建立在海量數據挖掘基礎之上的一種智能平臺，根據用戶個人信息與物品特征，比如用戶的興趣、歷史購買行為和物品的材質、價格等，利用統計分析、機器學習和人工智能等技術建立模型，預測用戶對新物品的評價與喜好，從而向用戶推薦其可能感興趣的潛在物品，以實現個性化的信息服務和決策支持[3-4].如：淘寶的購物推薦、Amazon的購書推薦、豆瓣的電影推薦等均是典型的個性化推薦系統應用案例.

推薦系統根據推薦算法輸出的不同一般可分為2類：單項推薦和多項(Top-N)推薦，前者輸出一個用戶對其尚未評分的特定物品的預測打分；后者輸出用戶尚未評分且預測打分最高的前N個物品.推薦系統根據推薦算法的不同一般可分為3類：基于內容的推薦(單用戶、多數據模型推薦)、協同過濾推薦(多用戶、多數據模型推薦)和混合推薦.基于內容的推薦是指根據目標用戶已評分物品與尚未評分的物品特征之間的相似性為用戶推薦其可能感興趣的物品；由于其歷史評分數據訓練集均來自同一用戶，又稱為基于單用戶、多數據模型推薦.協同過濾推薦是指根據用戶或物品之間的相關性進行推薦，即無需對用戶或物品本身的特征進行建模，如：根據與被推薦目標用戶具有一定相似度的其他用戶的喜好來進行推薦；由于其歷史評分數據訓練集來自多個不同的相關用戶，又稱為基于多用戶、多數據模型推薦.混合推薦是指綜合運用上述2種推薦方法進行推薦，以進一步提高推薦的精確性.其中，協同過濾推薦在如今個性化推薦系統中有著廣泛的應用，算法主要可以分為2類：基于記憶[5-7]的協同過濾推薦和基于模型[8-12]的協同過濾推薦.前者是根據用戶或物品之間的相似性來進行預測推薦；后者是對已有數據，即收集到的用戶歷史數據信息，如商品評分、網頁瀏覽記錄等，運用統計學和機器學習等技術進行分析，挖掘用戶的偏好和行為，建立一個預測模型，該模型能對新數據進行預測并向用戶進行個性化的結果推薦.由于基于模型的推薦系統具有推薦精確度高、對大批量歷史數據可通過離線訓練、在線推薦的方法降低用戶的存儲、計算與通信開銷等優點，因此被廣泛應用于各種不同類型的個性化推薦系統.

由于移動用戶本地計算資源受限，通常將推薦系統的預測模型建立與推薦結果計算工作外包給存儲、計算資源充足的推薦服務器完成.然而推薦服務器一般在半可信或惡意模型下工作.前者是指推薦服務器誠實地按照協議的規定來執行，同時通過與用戶間的交互最大程度地獲取有關用戶的秘密信息；后者是指推薦服務器可通過任意行為來破壞協議的執行.因此，推薦系統的隱私保護面臨著兩難問題：一方面，為了提高推薦結果的精確性與可用性，系統需要盡可能大規模、高精確度地提取用戶的相關歷史數據信息(用戶屬性、物品屬性、評分等)作為預測模型的訓練集；另一方面，用戶的歷史數據給出得體量越大、越具體，其隱私暴露的風險就越大、推薦系統執行的效率就越低(用戶端的存儲開銷、計算開銷和通信開銷就越大).因此，解決推薦系統中的高效隱私保護問題，即如何在密文域上設計輕量級的隱私保護推薦系統，包括密文域上的用戶歷史數據訓練、預測建模和密文域上的推薦結果計算，是一個亟待解決且具有重要理論意義和社會應用價值的問題.

Fig. 1 Privacy-preserving recommender system in the single user and multiple data setting圖1 基于單用戶、多數據模型的推薦系統隱私保護

1 推薦系統的隱私保護

1.1 推薦系統隱私保護的模式

推薦系統的隱私保護根據歷史訓練數據集來源于同一個用戶還是多個不同用戶，可分為基于單用戶、多數據模型的推薦系統隱私保護和基于多用戶、多數據模型的推薦系統隱私保護.

傳統的基于單用戶、多數據模型的推薦系統隱私保護系統架構如圖1所示，其主要工作流程為：

① 歷史數據源用戶利用公鑰全同態加密[13-19]等技術對歷史訓練數據集中的輸入數據進行加密；

② 歷史數據源用戶將加密后的歷史數據訓練集發送給推薦服務器；

③ 推薦結果授權用戶向歷史數據源用戶申請其推薦結果訪問授權；

④ 歷史數據源用戶向推薦結果授權用戶發布授權令牌；

⑤ 存儲與計算資源充足的推薦服務器在密文域上建立預測模型，并計算推薦結果；

⑥ 推薦服務器返回密文域上的推薦結果，并出示推薦結果正確性驗證證據；

⑦ 擁有公鑰加密算法對應私鑰的推薦結果授權用戶可成功解密推薦結果并驗證其正確性.

以上基于單用戶、多數據模型的推薦系統隱私保護系統架構考慮了推薦結果授權用戶和歷史數據源用戶為不同用戶的一般化情形，增加了步③和步④申請推薦結果訪問授權和授權推薦結果訪問令牌.當推薦結果授權用戶與歷史數據源用戶為同一用戶時，圖1中虛線部分可省略.

基于多用戶、多數據模型的推薦系統隱私保護系統架構如圖2所示，不失一般性，令域1為目標域，即推薦服務器1為用戶組1中的用戶進行隱私保護的個性化推薦.為提高匹配效果與精度，需要利用域i(i=2,3,…,n)中與用戶組1相似用戶的歷史數據作為訓練集，從而在多域場景下，實現基于多用戶、多數據模型的密文域上的預測模型建立和推薦結果計算.具體步驟為：

① 推薦服務器1對存儲在不同域推薦服務器i(i=2,3,…,n)中且在不同CSPi(i=2,3,…,n)公鑰PKi(i=2,3,…,n)加密下的，與用戶組1中用戶屬性相似的用戶歷史數據進行安全搜索；

② 各推薦服務器i(i=1,2,…,n)通過安全多方計算，在密文域上實現推薦系統隱私保護的預測模型建立和推薦結果計算，并將安全多方計算得到的密文推薦結果及其正確性可驗證證據返回給目標域，即域1中的推薦服務器1；

③ 推薦服務器1將密文推薦結果及其正確性可驗證證據返回給用戶組1中的用戶；

④ 用戶組1中的用戶解密推薦結果，并驗證其正確性.

Fig. 2 Privacy-preserving recommender system in the multiple user and multiple data setting圖2 基于多用戶、多數據模型的推薦系統隱私保護

1.2 推薦系統隱私保護的安全模型

推薦系統隱私保護理論研究是近年來國內外的一大熱點，得到了國內外密碼與計算機安全領域學者的廣泛關注.推薦系統的隱私保護要求推薦系統不應向推薦服務提供商或其他惡意用戶暴露任何有關用戶的隱私信息，包括用戶歷史數據訓練集的隱私、預測模型隱私和推薦結果隱私等[3-4].推薦系統的可用性是指推薦結果的可靠性、有效性等功能指標.當前，國內外推薦系統的隱私保護主要可分為基于數據擾動的方法[5-12,20-25]和基于公鑰全同態加密的方法[26-44]等.

1.2.1 基于數據擾動的方法

此外，為保護推薦系統的差分隱私，Berlioz等人[12]提出了3種將差分隱私應用到矩陣分解的技術，并且評估了每個方法對隱私保護和推薦結果精確性的權衡效果.Liu等人[20]將差分隱私和貝葉斯后驗抽樣結合起來，提出了一種高效的可證明差分隱私安全的推薦算法.2017年Wang等人[21]通過向預測模型訓練過程中引入拉普拉斯噪音，提出了一個具有差分隱私的基于毗鄰關系的隱私保護推薦系統，與文獻[12]基于矩陣分解的差分隱私保護方法相比，具有更高的推薦精確性.2018年Meng等人[22]提出了一個隱私保護的社交推薦協議，用戶可對其歷史打分與社交關系進行隱私保護建模，并且通過將不同的噪聲強度引入敏感和非敏感數據訓練集，對不可信的推薦服務器與惡意用戶保護了差分隱私.然而，上述通過基于數據擾動技術[5-12,20-22]實現的推薦系統隱私保護難以同時獲得完美的推薦系統可用性與用戶數據隱私保護.

1.2.2 基于公鑰全同態加密的方法

在利用公鑰全同態加密技術實現推薦系統的隱私保護方面，主要思想是利用公鑰全同態加密對用戶的歷史數據訓練集加密后上傳到推薦服務器，后者利用其全同態性質在密文域上進行預測模型建立和推薦結果計算，因此能在一定程度上解決推薦系統可用性與隱私性的統一問題.Katzenbeisser等人[26]利用Paillier公鑰加法同態加密算法，在電子醫療系統中提出了一個病人健康信息隱私保護的內積協議、歐幾里得距離計算和病人信息匹配協議，并在此基礎上構造了一個對醫療服務消費者隱私保護的推薦系統.Erkin等人[27]通過引入可信第三方，利用數據壓縮技術設計加密數據比較協議，構建用戶個人數據隱私保護的推薦系統.Nikolaenko等人[28]利用Paillier公鑰加法同態加密，結合Yao的混淆電路提出了一個基于隱私保護脊回歸的推薦系統.隨后，Nikolaenko等人[29]進一步利用用戶歷史評分數據的稀疏性、不經意分類網絡技術和Yao的混淆電路技術，提出了隱私保護的矩陣分解算法，并將其應用到隱私保護的推薦系統中，實現了在保護用戶評分隱私和評價商品隱私的前提下進行有效推薦的新機制.文獻[28-29]的方案均在對用戶歷史數據隱私保護的前提下，利用假定不合謀的推薦服務器和密碼服務提供商(cryptographic service provider, CSP)之間的交互建立預測模型.具體而言，每個用戶首先向推薦服務器提交加密的歷史物品評分數據；然后，推薦系統對加密歷史數據盲化后發送給CSP；CSP解密盲化數據并將其編碼成對應的用于建立推薦預測模型的Yao混淆電路的輸入發送給推薦服務器；最后，推薦服務器執行Yao的混淆電路得到推薦預測模型.然而，該協議中Yao的混淆電路所需門電路個數、計算和通信開銷均隨矩陣維數的增加迅速增長，僅能有效支持密文域上固定次數的矩陣分解迭代，無法保證矩陣分解的質量，從而影響了推薦系統的可用性.

為解決上述問題，Kim等人[30]在加密向量運算時引入新的數據結構，利用公鑰全同態加密和安全多方計算技術，提出了較文獻[29]更為高效的基于矩陣分解的隱私保護推薦系統，然而安全多方計算技術要求推薦服務器實時在線.2018年，Chen等人[31]提出了隱私保護的分布式脊回歸協議，然而為實現隱私保護和密態數據處理，用戶需利用Paillier公鑰加法同態加密對每個輸入數據進行加密，計算開銷和通信開銷巨大.此外，在上述工作[28-30]中，推薦服務器通過Yao混淆電路計算將直接得到明文狀態下的預測模型，未形式化刻畫預測模型隱私的安全模型及構造相應解決解決方案，因此，用戶未來行為模式隱私無法對推薦服務器實現隱私保護.工作在半可信或惡意環境下的推薦服務器將通過預測模型獲得用戶在將來任意狀態下可能的行為措施，導致用戶隱私在一定程度上的泄漏.

為解決用戶使用初期歷史評分數據訓練集過小而導致推薦精度不高的冷啟動問題，Jeckmans等人[32]在相對較小用戶歷史數據訓練集上，利用公鑰部分全同態加密和安全多方計算技術，提出了一個社交網絡中隱私保護的推薦系統.Tang等人[33]根據用戶社交網絡的歷史評分數據，利用公鑰全同態加密技術構造了能預測用戶對特定物品的評分，以及預測用戶評分最高的N個物品的隱私保護推薦協議.然而，所有相似用戶的歷史數據都在推薦服務器發布的統一公鑰下加密，未給出多用戶、多數據模型推薦系統隱私保護的形式化安全模型與解決方案，無法適用于跨域場景中隸屬于不同域的用戶數據由不同的推薦服務器或密碼服務提供商(CSP)的不同公鑰加密下的多用戶、多數據模型推薦系統隱私保護.Badsha等人[34]通過引入不同的半可信第三方，利用公鑰同態加密技術提出了一個基于用戶的聯合過濾隱私保護推薦系統.為了去除隱私保護推薦系統中需要引入可信第三方或多個半可信第三方的限制，Tang等人[35]在無須半可信服務提供商的前提下，利用Gentry的部分公鑰全同態加密技術構造了一個預測用戶對特定商品評分的隱私保護推薦系統.為進一步提高推薦系統隱私保護的可用性與效率，Aimeur等人[36]在電子商務場景中，利用公鑰同態加密和安全多方計算技術，在假定商家與半可信第三方不合謀的前提下，提出了一個能同時保護消費者歷史購買數據隱私、未來購買意愿隱私與商家消費策略隱私的，基于內容、人口學和聯合過濾的混合推薦系統.2017年Tang等人[37]利用Gentry的部分公鑰全同態加密技術，設計了隱私保護的漸進矩陣分解協議與隱私保護的基于用戶的聯合過濾協議，并在此基礎上構造了一個隱私保護的混合推薦系統.

為了實現基于機器學習的隱私保護推薦系統，2017年Liu等人[38]利用Yao的混淆電路、公鑰加法同態加密和秘密分享技術，提出了隱私保護的神經網絡預測模型miniONN.然而，服務器和用戶間需支持實時在線交互，在資源受限的用戶端帶來了巨大的輪復雜度與通信開銷.2018年Bourse等人[39]利用公鑰全同態加密，構造了深度離散神經網絡中的快速同態計算框架，然而，該工作未解決密文域上的模型訓練問題，且未給出隱私保護模型計算中非線性激活函數、梯度函數的高效實現方法.為改進文獻[38-39]中僅針對單用戶歷史數據訓練集實現隱私保護模型訓練與計算的不足，同年Wang等人[40]利用Paillier公鑰加法同態加密，在假定不合謀的云服務器與密碼服務提供商(CSP)場景下，設計了隱私保護的多用戶詞向量訓練聯合模型學習協議.然而，上述工作[26-40]均利用計算開銷和密文擴張都較大的公鑰(全)同態加密技術實現，其用戶數據隱私無法抵抗半可信或惡意推薦服務器和推薦結果授權用戶發起的合謀攻擊，推薦結果隱私和預測模型隱私僅達到選擇明文(CPA)安全，同時也未形式化刻畫惡意云服務器環境下推薦結果的正確性可驗證安全模型.此外，在用戶本地對大規模的歷史數據訓練集逐個加密，無法滿足推薦系統中移動用戶存儲、計算資源受限的客觀要求；此外，將公鑰全同態加密直接作用在用戶歷史數據集上，違背了混合加密體制“用公鑰加密算法加密較短的對稱密鑰，用對稱加密算法加密較大的數據”這一基本原則.

1.2.3 存在問題

現有的利用公鑰全同態加密技術實現的隱私保護推薦系統，僅適用于單用戶、多數據模型，即用于預測模型訓練的歷史數據集均來自同一個單一用戶.其具體流程如下：用戶首先用自己的公鑰或其授權用戶的公鑰，利用公鑰全同態加密對其歷史數據集中的每一個數據進行加密；然后，推薦服務器利用其全同態性質在密文域上進行機器學習和模型訓練，得到密文域上的預測模型；最后，推薦服務器在密文域上為用戶計算推薦結果，僅授權用戶(用戶本身或經其授權的其他用戶)可以用相應的私鑰正確解密推薦結果.然而，單用戶、多數據模型通常存在歷史數據訓練集規模有限且用戶本地計算、通信開銷大的缺陷.

為了解決上述問題，基于多用戶、多數據模型的隱私保護協同過濾推薦算法得到了學術界的廣泛關注.現有的做法通常是利用公鑰全同態加密技術與Yao的混淆電路(garbled circuit)，通過在假定不存在合謀攻擊的推薦服務器與密碼服務提供商(CSP)間的安全多方計算實現.在初始化階段，推薦服務器選取盲化因子并與CSP通過運行不經意傳輸協議，獲得可用于Yao的混淆電路計算的相關盲化因子輸入.然后，各用戶用CSP的公鑰加密各自的歷史數據訓練集(物品-評分數據)，上傳至推薦服務器，推薦服務器對加密歷史數據進行盲化并發送給CSP；其次，CSP解密盲化后的加密歷史數據，并將其編碼成用于計算推薦系統預測模型的Yao的混淆電路的輸入，并將其發送給推薦服務器；最后，推薦服務器再利用初始化階段從CSP獲取的盲化因子混淆電路輸入，運行Yao的混淆電路，對盲化后的歷史數據實現脫盲后向用戶輸出預測模型與推薦結果.然而，在上述過程存在3個缺陷：1)在基于多用戶多數據模型的協同過濾推薦算法中，沒有考慮如何在密文歷史數據集上尋找與目標用戶特征相似的其他用戶的密文歷史數據作為有效參考訓練集的安全搜索問題；2)多個不同用戶仍然用一個相同的公鑰(CSP的公鑰)加密各自的歷史數據集，其本質上還是單用戶多數據模型，不適用于跨域(每個域由不同的推薦服務器和CSP負責管理)環境下的基于多用戶多數據模型的協同過濾推薦；3)推薦服務器以明文的方式返回預測模型及推薦結果，對工作于半可信或惡意環境下的推薦服務器難以實現隱私保護.

由于在多用戶、多數據模型中，要求每一個用戶各自的歷史數據集對其他用戶實現隱私保護，與單用戶多數據模型相比需要建立更高級別的新安全模型.雖然國內外對于單用戶多數據模型以及基于推薦服務器和CSP聯合架構下的多用戶多數據模型的隱私保護推薦系統已有一定的研究結果，但對跨域環境下(即：屬于不同域的用戶使用不同的CSP公鑰加密各自的歷史數據集)的多用戶多數據模型協同過濾推薦系統的隱私保護問題還鮮有研究.因此，形式化刻畫跨域環境下多用戶多數據新安全模型，即：在多個不同用戶用各自域中CSP的公鑰(而非同一個CSP的統一公鑰)加密自己的歷史數據集中并上傳至推薦服務器的前提下，實現密文域上高效的相似用戶歷史數據安全搜索、密文域上高效的預測模型建立與推薦結果計算是一項在密碼安全與隱私保護領域急需開展的、具有重大理論突破和實際應用價值的研究工作.同時，針對惡意推薦服務器與惡意CSP環境下，如何建立對返回的預測模型及推薦結果的正確性可驗證安全模型，以及如何在標準模型或通用組合安全模型下設計可證明安全的隱私保護推薦系統也是一項重要的研究課題.

因此不難看出，無論是對推薦系統隱私保護新理論、新方法方面的研究，還是對多用戶、多數據新安全模型的探索，都有助于推動推薦系統隱私保護從理論研究真正地走向實際應用.

1.3 推薦系統隱私保護的高效性

推薦系統隱私保護的高效性要求用戶本地的計算開銷應小于推薦模型訓練與推薦結果預測的計算開銷之和，即只有在該條件下，存儲、計算資源受限的用戶才具有將推薦算法外包給資源龐大但處于半可信或惡意環境下運行的推薦服務器完成的動機.

為進一步降低利用公鑰全同態加密技術實現推薦系統隱私保護的計算與通信開銷，近年來國內外學者多致力于研究高效的公鑰全同態加密與高效的隱私保護外包計算，涌現了一系列重要結果[13,19,45-54].2009年，Gentry[13]提出了基于理想格的全同態構造方法，這是第一個語義安全的全同態加密方案.它在理論上無懈可擊，但實現起來卻頗有難度.隨后，Smart等人[14]和Stehle等人[15]分別采用行列式為素數的主理想格和引入解密誤差的方法來實現.Van等人[16]提出了一個基于整數環的全同態加密方案，其中設計了一個僅需基本模(加法和乘法)運算實現的部分同態加密，并結合Gentry的技術[13]設計了一個高效的全同態加密方案.

為促成同態密碼在實際中的應用，除了采取各種技巧來提高效率之外，在方案的構造階段，還存在另一種思路，就是針對實際應用的特點，降低對加密算法的要求，利用效率較高的類同態加密方案來滿足實際需要.自從LWE(learning with error)問題[17]被提出以來，它就被應用于密碼體制的構建中.Halvei等人[18]在2010年基于BGN密碼提出了一種實用的方案，其安全性基于ring-LWE問題，支持任意次數的加法和一次乘法，支持較大的消息空間，是一個高效而實用的方案.但是，只能計算一次乘法運算的性質仍然限制了其應用范圍.2011年Brakerski和Vaikuntanathan[19]使用Gentry的構造方法[13]和重線性化技術的基本原理，分別基于ring-LWE困難問題和標準LWE困難問題構造了2個全同態加密方案.2016年Chillotti等人[45]在基于GSW的公鑰全同態加密及其環上的變種方案，設計一個更加快速的公鑰全同態加密算法.同年，Cao等人[46]通過優化對大整數乘法運算器的結構，對公鑰全同態加密的運算速度得到一定程度的改善.2017年Canetti等人[47]利用Boneh等人的提出的一般性通用轉換技術，在任意多密鑰基于身份的公鑰全同態加密基礎上構造具有非適應性選擇密文安全(CCA1)的公鑰全同態加密方案；并利用高效的非交互知識證明協議構造了高效的CCA1安全的公鑰全同態加密方案.2018年Halevi等人[48]提出了快速同態線性變換軟件庫HElib，利用密文壓縮技術對傳統參數配置下的同態加密算法計算速度提高30～75倍.然而，文獻[49-50]指出：即便在為了提高運算效率犧牲一定數量乘法運算的前提下，公鑰全同態加密的計算復雜度對推薦系統中資源受限的移動用戶而言仍然太大而顯得不實際.

在高效的隱私保護外包計算方面，Liu等人[51]在假定不合謀的云服務器與密碼服務提供商(CSP)環境下，在改進Bresson雙門限加法同態加密的基礎上，提出了高效的隱私保護多密鑰外包計算協議.2017年為進一步降低用戶端的計算開銷，Liu等人[52]設計了具有部分解密功能的可轉換同態加密方案，在合數階群中提出消息預編碼技術和消息擴展編碼技術，設計了隱私保護的模冪運算協議.2018年Liu等人[53]還利用門限Paillier公鑰加法同態加密，構造了隱私保護的有理數外包計算協議.然而，上述工作[51-53]均利用公鑰同態加密技術和安全多方計算技術實現，要求用戶與服務器進行實時在線交互，無法滿足推薦系統中移動用戶計算、通信資源受限的客觀性能要求.同年，Boneh等人[54]基于容錯學習問題(LWE)，利用門限公鑰全同態加密，給出了包括門限公鑰加密、門限簽名等密碼原語在內的門限密碼體制一般性構造方法.然而，輕量化的算法實現還有待進一步發現.

由于利用公鑰(全)同態加密技術實現推薦系統隱私保護難以滿足移動用戶本地存儲、計算資源受限的客觀性能需求，最近我們考慮不依賴公鑰(全)同態加密技術，利用任意單向陷門置換提出高效的基于單用戶時間序列隱私保護數據聚合方案[55-59],即單用戶加法同態數據封裝機制.該方案僅需執行一次單向陷門置換運算便能實現對n個數據的隱私保護外包聚合，給出了在不得不使用公鑰加密算法來保護數據隱私時，如何通過減少公鑰密碼的使用次數(最低一次)來實現n個數據安全的新思路.然而，該工作[55]只能在保護用戶數據隱私的前提下，實現密文域上的加法操作，而推薦系統的預測模型建立與推薦結果計算函數屬于主要由加法和乘法2種原子運算構成的功能更為復雜的統計分析或數據挖掘算法，無法直接應用于推薦系統的隱私保護中；且要求所有輸入數據來源于同一用戶，也無法直接應用來解決跨域的推薦系統隱私保護問題.

為了解決該問題，我們進一步提出了多密鑰加法同態數據封裝機制[44]、單密鑰全同態數據封裝機制[60]與多密鑰全同態數據封裝機制[61-62]，分別高效地解決了單用戶、多數據環境(所有輸入數據由同一個用戶的密鑰加密)和多用戶、多數據環境(所有輸入數據由不同用戶各自持有的不同密鑰加密)下的輕量級隱私保護數據聚合和外包計算協議.所構造協議無論在存儲、計算資源受限的本地用戶端還是在云服務器端的計算開銷和通信開銷，與利用公鑰同態加密(如Paillier公鑰加法同態加密)和公鑰全同態加密(如Brakerski公鑰全同態加密[19]、López-Alt多密鑰公鑰全同態加密[63])相比，都有顯著降低.

表1說明了我們提出的多密鑰加法同態數據封裝機制[44]與傳統的利用Paillier公鑰加法同態加密實現的隱私保護多用戶、多數據聚合方案的性能比較.其中，n,ni,N,p分別表示數據擁有者(發送方)的個數、每個數據擁有者持有的輸入數據個數、Paillier加法同態加密模數中使用的模數(N=pq，其中p和q為大素數)、多密鑰加法同態數據封裝機制中使用的大素數模；Mul和Add分別表示乘法運算和加法運算.單密鑰加法同態數據封裝機制的性能比較可類似得出.

表2說明了我們提出的多密鑰全同態數據封裝機制[62]與傳統的López-Alt多密鑰公鑰全同態加密[63]的性能比較.其中，n,ni,K,degF分別表示數據擁有者(發送方)的個數、每個數據擁有者持有的輸入數據個數、外包多元多項式函數F的項數、外包多元多項式函數F的階.單密鑰全同態數據封裝機制的性能比較可類似得出.上述不依賴公鑰全同態加密技術實現的隱私保護單用戶、多數據和多用戶、多數據聚合與外包計算協議為進一步解決推薦系統隱私保護的輕量化指明了方向.

Table 1 Efficiency Comparison of Multi-key Additively Homomorphic Data Encapsulation Mechanism

Table 2 Efficiency Comparison of Multi-key Fully Homomorphic Data Encapsulation Mechanism

存在問題：現有的基于單用戶、多數據模型的推薦系統隱私保護多基于公鑰(全)同態加密來實現，然而，直接將公鑰(全)同態加密作用于數據本身，違背了混合加密體制基本原則，且其巨大計算開銷無法滿足推薦系統中移動用戶資源受限的性能需求.因此，不從輕量化(全)同態加密算法本身出發，而是著重研究不依賴于(全)同態公鑰加密技術，利用任意公鑰加密算法，且在不得不使用公鑰加密來保護用戶數據安全時，通過盡量減少公鑰加密的使用次數(最低一次)提出推薦系統中對n個用戶歷史數據實現高效隱私保護的(全)同態數據封裝新方法成為實現推薦系統隱私保護的重要手段.目前工作僅局限于不利用公鑰加法同態加密的、高效的隱私保護單用戶時間序列外包數據聚合協議研究，基于單用戶、多數據模型的推薦系統隱私保護一般性構造新方法，包括推薦系統中隱私保護的預測模型建立和推薦結果計算等是一個具有重要理論意義和實際應用價值的研究方向.

此外，現有的基于多用戶、多數據模型的協同過濾推薦系統隱私保護多利用公鑰(全)同態加密技術，通過用戶、推薦服務器與CSP間的安全多方計算實現.然而，對于如何在密文歷史數據集上尋找與目標推薦用戶特征相似的其他用戶的密文歷史數據作為有效參考訓練集的安全搜索問題尚未考慮；此外，多個不同用戶仍然用一個相同的公鑰(CSP的統一公鑰)加密各自的歷史數據集，其本質上還是單用戶多數據模型，不適用于跨域環境(每個域由不同的推薦服務器和CSP負責管理)下的基于多用戶多數據模型的協同過濾推薦.在跨域場景中，隸屬于不同域的用戶用各自域中CSP的公鑰(而非同一個CSP的統一公鑰)加密自己的歷史數據集，為密文域上的預測模型建立和推薦結果計算帶來了新的挑戰.因此，設計高效的密文域上高效的相似用戶歷史數據安全搜索方案；并在此基礎上，通過減少公鑰加密使用次數設計多密鑰全同態數據封裝機制，從而構造多用戶、多數據模型下高效的隱私保護推薦系統預測模型建立與推薦結果計算協議是一個具有挑戰性的重要研究課題.

1.4 推薦系統隱私保護的可驗證與可審計

推薦系統隱私保護的可驗證與可審計是指在惡意敵手環境下，用戶需要對推薦服務器返回的推薦結果的正確性進行有效驗證，并在推薦服務器一旦被發現存在欺詐行為，即推薦結果正確性驗證失敗時，進一步設計高效的抗抵賴可審計機制.

雖然國內外一系列推薦系統隱私保護工作[26-43]在半可信推薦服務器環境下，對保護用戶歷史數據隱私和提高推薦精確性方面做出了重要貢獻，但均未考慮惡意推薦服務器環境下返回的推薦結果正確性可驗證與防欺詐問題.為了解決該問題，要求推薦服務器向用戶證明推薦結果計算的正確性[67-87].其中一個合理性條件是，用戶用于驗證的推薦結果正確性的開銷必須小于用戶自己在本地計算推薦結果的計算開銷.為了在實現推薦系統隱私保護的同時驗證推薦結果的完整性和正確性，Tang等人[87]利用額外數據引入技術，在雙服務器模型下設計了具有權重的安全外包聯合過濾算法Slope One，并在此基礎上給出了一個推薦結果完整性與正確性驗證的有效方法.然而，其推薦結果驗證算法的效率還有待進一步提高.安全外包計算的可驗證與防欺詐技術[67-86]為推薦系統中推薦結果的正確性驗證提供了有利工具.近年來，Gennaro等人[67]首次提出外包計算結果可驗證的概念，利用Yao的混淆電路技術[68]和公鑰全同態加密技術提出了第一個可驗證外包計算方案,然而每次驗證失敗時都要求系統重新初始化.Chung等人[69]在公鑰全同態加密的基礎上構造了非交互的可驗證計算方案，該方案的優勢在于其公鑰長度較短.Benabbas等人[70]則針對某些特殊函數構造了高效的可驗證計算方案.近年來，Barbosa等人[71]以模塊化的方式，利用全同態加密技術、函數加密技術和消息認證碼技術提出了一個可驗證的函數加密方案與可代理的同態加密方案.Fiore等人[72]則基于同態散列函數、針對加密數據給出了高效的可驗證計算方案.

Parno等人[73]首次提出了可公開驗證計算的概念，并基于密鑰策略的屬性加密方案(KP-ABE)構造了可公開驗證計算方案.Fiore等人[74]在Benabbas等人[75]所構造方案的基礎上，構造了針對高階多項式函數和矩陣乘積的支持公開驗證的方案.Catalano等人[76]通過引入代數單向函數來構造針對高階多項式與矩陣乘積的支持公開驗證的方案.Choi等人[77]給出了支持多客戶端、非交互的可驗證計算的構造.Goldwasser等人[78]給出了多輸入的函數加密的構造，并在此基礎之上，對如何將其應用于多客戶端可驗證計算方案的構造作了討論.Gordon等人[79]給出了多客戶端的可驗證計算中更強的安全性和隱私性模型的探討，并分別基于屬性基加密、全同態加密以及Yao’s Garbled Circuit[68]構造了支持多客戶端的可驗證計算方案.Papamanthou等人[80]提出了一個支持多元多項式運算的可驗證外包計算方案SCC，該方案在隨機預言機模型下具有適應性安全，且支持高效更新，即函數的公鑰更新計算復雜性僅與多元多項式系數更新數目成線性關系.但其正確性驗證基于雙線性配對運算實現，開銷較大；且該方案側重考慮外包計算結果的可驗證性，無法保證多元多項式輸入及系數的隱私保護問題.Parno等人[81]基于二次運算程序(quadratic arithmetic program)，僅依賴于密碼學假設提出了一個高效的公開可驗證外包計算方案Pinocchio.盡管與文獻[73]相比，用戶端正確性驗證的計算開銷大大降低，但其證據生成算法的開銷仍然較高.為了解決該問題，Costello等人[82]基于多方二次運算程序(Multi-QAP)，減少了在多個計算間或單個計算內部共享狀態的開銷，使得云服務器產生的數據承諾可以在相關的多個正確性驗證證據生成算法中重復使用，從而大大減少了證據生成算法的計算開銷.2018年Bunz等人[83]在無需可信初始化前提下，提出了一個高效的非交互零知識區間證明協議，其證明長度僅與證據大小成對數關系，證明生成和驗證的計算開銷與證據大小成線性關系.同年，Frederiksen等人[84]基于加法同態多方承諾技術，提出了惡意環境下可抵抗全串謀攻擊的安全多方計算協議.但上述方案[67-84]均未考慮用戶數據隱私與外包計算的結果隱私保護問題.

存在問題：國內外現有的推薦系統隱私保護協議多采用零知識證明、同態承諾和同態消息認證碼等技術實現在惡意敵手環境下對推薦結果正確性的有效驗證.然而，其驗證所帶來的計算開銷巨大，無法滿足存儲、計算資源受限的本地用戶的客觀性能需求.推薦結果正確性可驗證的計算開銷要求小于用戶本地計算推薦模型和預測推薦結果的計算開銷之和；否則外包推薦算法也將失去其實際意義.此外，同時考慮用戶歷史數據集隱私、推薦系統模型隱私、推薦結果隱私和推薦結果正確性高效可驗證的隱私保護推薦系統還鮮有研究.

2 未來研究方向與解決方案

1) 研究標準模型或通用組合(universally com-posable, UC)模型下輕量級、可驗證且適用于推薦系統隱私保護的新型加密方案或協議的安全模型

推薦系統的隱私保護需要從3方面形式化刻畫其安全模型：①用戶數據隱私，即在單用戶、多數據模型下，用戶歷史數據訓練集作為推薦系統預測模型建立與推薦結果計算的輸入，能有效抵抗由半可信或惡意推薦服務器與推薦結果授權用戶發起的合謀攻擊；在跨域的多用戶、多數據模型下，每位用戶的歷史數據訓練集還要求能有效抵抗由本域半可信或惡意推薦服務器、本域未授權用戶、不同域中的推薦服務器以及不同域中的未授權用戶之間發起的合謀攻擊；②推薦結果隱私，即推薦結果對推薦服務器和未授權用戶發起的合謀攻擊實現有效保護，僅用戶本身或推薦結果授權用戶可以成功解密推薦結果；③預測模型隱私，即根據用戶歷史數據集訓練得到的預測模型能有效抵抗由推薦服務器與未授權用戶發起的合謀攻擊.

國內外現有工作僅局限于不依賴于公鑰(全)同態加密設計了單用戶時間序列數據聚合協議；且僅在隨機預言機模型下形式化證明其輸出隱私適應性選擇密文(CCA2)安全.因此，設計用戶數據隱私滿足無條件安全、推薦結果隱私與預測模型隱私滿足對推薦服務器和未授權用戶發起的合謀攻擊在標準模型下具有CCA2安全的、高效的推薦系統隱私保護新方案具有重要的理論意義與實際應用價值.此外，采用UC通用組合技術，設計高效的推薦系統隱私保護方案，滿足用戶數據隱私、推薦結果隱私和預測模型隱私在現實環境下和理想環境下對概率多項式時間能力的敵手計算不可區分，也是一個重要的研究課題.

半可信模型是指被敵手俘獲的一方(歷史數據源用戶、推薦服務器或推薦結果授權用戶)誠實執行個性化推薦協議，并通過與其他未被俘獲實體的交互最大限度地獲取其秘密信息；惡意模型是指被俘獲方能以任意概率多項式時間的策略來破壞協議的執行.具體而言，在半可信推薦服務器環境下，用功能函數Frec來刻畫理想環境下的推薦系統功能，用IDEALFrec,Sim(z)(k,funrec,(x1,x2,…,xn))刻畫在理想環境Frec下的敵手Sim、推薦服務器、歷史數據源用戶和推薦結果授權用戶的輸出，其中k,funrec,x1,x2,…,xn,z分別代表安全參數、預測模型建立或推薦結果計算函數、預測模型建立或推薦結果計算函數funrec的n個用戶歷史輸入數據和輔助輸入；進一步我們用REALπ,Adv(z)(k,funrec,(x1,x2,…,xn))刻畫協議在真實環境π下執行時的敵手Adv、推薦服務器、歷史數據源用戶和推薦結果授權用戶的輸出.那么，我們可以形式化刻畫推薦系統隱私保護的安全性：一個個性化推薦協議π安全地實例化了推薦系統的理想功能模型Frec，當且僅當對任意概率多項式時間能力的真實敵手Adv，存在一個概率多項式時間的理想敵手(模擬者)Sim，使得對任意輸入funrec,x1,x2,…,xn,z，

{IDEALFrec,Sim(z)(k,funrec,(x1,x2,…,xn))}≈c
{REALπ,Adv(z)(k,funrec,(x1,x2,…,xn))}

成立，其中≈c代表計算不可區分.此外，進一步在UC通用組合模型下刻畫半可信推薦服務器與未授權用戶發起的合謀攻擊以及多用戶、多數據模型下多個未授權用戶之間的合謀攻擊也是推薦系統隱私保護安全模型刻畫的重要研究方向.

2) 探索不得不使用公鑰加密實現用戶數據隱私保護時，通過減少公鑰加密解密次數實現輕量級的基于單用戶、多數據推薦系統隱私保護的一般性構造方法

依據“在不得不使用公鑰加密來保護用戶數據隱私的前提下，通過減少公鑰加密的次數(最低一次)來實現n個用戶歷史數據安全”這一總體思路，設計全同態數據封裝機制，在單用戶、多數據模型下探索不依賴于公鑰(全)同態加密技術的、高效的可驗證推薦系統隱私保護一般性構造方法.利用一次任意公鑰加密運算，在n個用戶歷史輸入數據構成的訓練集上實現推薦系統的隱私保護.通過利用特定代數結構上的對稱全同態映射hfhom和任意公鑰加密算法代替傳統的公鑰(全)同態加密技術，來實現單用戶、多數據模型下的推薦系統隱私保護一般性構造新方法；使得資源受限用戶端公鑰加密計算開銷顯著降低(達到O(1),即與用戶歷史數據集大小無關)的前提下，同時保證密文域上隱私保護預測模型建立與推薦結果計算的可用性.上述研究方案遵循混合加密中“公鑰加密用于加密較短的對稱密鑰，對稱密鑰用于加密較大的數據本身”的原則，可實現基于單用戶、多數據推薦系統隱私保護的輕量級一般性構造方法.

3) 探索不得不使用公鑰加密實現用戶數據隱私保護時，通過減少公鑰加密解密次數實現輕量級的基于多用戶、多數據推薦系統隱私保護的一般性構造方法

仍利用基于一次離線任意公鑰加密算法和在線僅包含簡單加法、乘法運算的對稱全同態映射實現基于多用戶、多數據模型的推薦系統隱私保護一般性構造方法.與基于單用戶、多數據推薦系統隱私保護方案構造不同的是：每個域中的用戶采用其所在域的CSP公鑰加密其自身隨機選擇的會話密鑰用作密鑰協商，并用該會話密鑰加密各自的歷史數據訓練集.因此，如何在每個用戶選擇的不同會話密鑰加密(每個域的會話密鑰又是在不同CSP公鑰加密下)的多用戶歷史數據訓練集上實現輕量級的相似用戶歷史數據批量安全搜索，以及密文域上預測模型建立和推薦結果的同態計算是一個難點問題.

為解決該問題，可通過2種方法進行構造：①利用跨域的分布式密鑰協商技術在跨域的多用戶間建立統一的會話密鑰，用于加密各自的歷史輸入數據；然后每個用戶便可利用單用戶、多數據模型下的推薦系統隱私保護方法，在不影響密文域上隱私保護預測模型建立和推薦結果計算可用性的前提下對用統一會話密鑰加密后的用戶歷史數據進行盲化，使得每個用戶的歷史數據對本域或其他域中的非授權用戶實現隱私保護.跨域的分布式密鑰協商協議需要在不同域的不同用戶間在推薦系統隱私保護的初始化階段進行交互，引入了額外的計算開銷與通信開銷，但其可在離線階段完成，且相應開銷可攤派在多次推薦系統的預測模型建議與推薦結果計算中.②為了提高方案的效率，可采取代理重加密技術，將不同密鑰加密下的用戶歷史數據轉換為某一可信第三方的公鑰加密下的密文，從而實現以用戶屬性向量作為關鍵字的多用戶批量安全搜索.此外，隱私保護的相似用戶匹配可通過密文域上2個用戶屬性向量間的隱私保護內積運算與隱私保護比較算法(當2個用戶屬性向量的內積值大于等于某個實現設定的閾值時，認定其相互匹配)來實現.

針對在不同密鑰加密下的用戶歷史數據訓練集上進行密文域預測模型建立和推薦結果的同態計算問題，可采用多密鑰公鑰全同態加密技術(multikey FHE)構造多密鑰全同態數據封裝機制，或通過密文轉換技術(encryption switching)在不同域的推薦服務器和CSP之間構造安全多方計算協議來實現.

4) 通過批量驗證技術提出輕量級推薦結果防欺詐與抗抵賴的一般性理論

國內外現有工作多利用Papamanthou等人[80]提出的計算正確性簽名技術來實現推薦結果的防欺詐性質，但其通過雙線性配對運算實現帶來了巨大的計算開銷.一種高效的推薦結果正確性可驗證方法是將Costello等人[82]在IEEE S&P 2015提出的基于Multi-QAP實現的、示證方(推薦服務器)與驗證方(推薦結果授權用戶)均達到輕量化的可驗證計算技術Geppetto、同態消息認證碼(homomorphic MAC)以及Frederiksen等人在PKC 2018提出的同態承諾(homomorphic commitment)等技術，與基于一次任意公鑰加密運算實現的高效的推薦系統隱私保護新方法相結合，構造同時具有隱私保護性質和輕量級推薦結果正確性可驗證性質的個性化推薦系統.此外，還可利用批量驗證技術，提出通過一次驗證，同時對n個推薦結果實現正確性驗證的新方法；并借鑒屬性基加密中的白盒可追蹤、黑盒可追蹤技術以及二次密鑰分發等方法，在推薦結果正確性驗證失敗時，對惡意推薦服務器的欺詐行為提出有效的抗抵賴審計追蹤機制.

3 結束語

本文圍繞推薦系統隱私保護的關鍵理論與方法，從推薦系統隱私保護的模式、安全模型、輕量化和推薦結果的正確性可驗證、可審計4方面進行闡述.詳細介紹了國內外現有的推薦系統隱私保護方法，指明了利用公鑰全同態加密實現推薦系統隱私保護需要將公鑰加密直接作用在數據上，違背了混合加密的基本原則，從而給資源受限的本地用戶帶來了巨大的計算開銷和通信開銷.

在此基礎上，我們進一步針對基于單用戶、多數據模型的推薦系統隱私保護和基于多用戶、多數據模型的推薦系統隱私保護模式，提出了在不得不使用公鑰加密保護數據隱私時，如何通過減少公鑰加密使用次數(最優時為一次)，在不利用公鑰全同態加密的前提下實現推薦系統隱私保護的核心思想、關鍵理論和新方法.闡述了在非請求-響應模式下，隱私保護的智能推薦系統為用戶自動返回個性化推薦結果在群智感知與5G網絡安全中的重要理論意義與應用價值.最后，我們還指出了當前研究存在的問題、未來研究方向和解決方案，為進一步從事推薦系統的隱私保護、智能安全與隱私保護的理論研究提供了新思路.