基于理性密碼學的分布式隱私保護數據挖掘框架*

程小剛,郭 韌,周長利

(1.華僑大學計算機科學與技術學院，福建 廈門 361021；2.廈門市數據安全與區塊鏈技術重點實驗室，福建 廈門 361021;3.華僑大學工商管理學院，福建 泉州 362021)

1 引言

在今天的大數據時代，數據挖掘技術越來越重要，因其是從大量數據中發掘出有價值的信息或知識的有效手段。數據挖掘中的一個研究重點是如何保護個人隱私。

一種常用的保護隱私的方法是對數據添加噪聲，即在公布數據供科學研究之前對數據模糊化。首先一些標識字段，如姓名、身份證號碼等,必須要刪除或模糊化處理，但僅僅如此簡單處理還不能有效保護隱私，因為通過其他一些準標識符字段，如年齡、性別和住址等，可以很容易推出此人的具體身份。為此，研究人員提出了一些更強的隱私保護手段，如k-匿名性[1]、l-多樣性[2]和t-相似性[3]及差分隱私保護[4]等。k-匿名性就是通過加上噪聲，使得發布的數據中存在至少k個在準標識符上不可區分的記錄；在k-匿名性的基礎之上提出的l-多樣性要求每個相同的準標識符下至少有l類條目；t-相似性要求在任何等價類中敏感屬性的分布同整體的分布是相似的；差分隱私保護是用于對數據庫進行統計查詢時，在最大化查詢準確性的同時最大程度地降低識別出某條記錄的概率。

加入噪聲可以保護隱私，但同時也會降低數據的準確性，所以若采用此種方法就需要在隱私保護和數據的準確性之間尋求一個平衡。有沒有既能保護隱私又能保證數據準確的數據挖掘方法呢？解決方案之一是分布式隱私保護數據挖掘，在此情形下隱私數據是由參與的各方擁有，然后各方通過合作來進行數據挖掘，挖掘出統計數據或函數結果的同時又不泄露各方的私有數據。這就是密碼學中的核心問題——安全多方計算SMPC(Secure Multi-Party Computation)[5],這方面有眾多理論研究成果和實現方案[6-11]，但經典密碼學中的實現方案大都是理論性的結果，效率較低,不能應用于實際。比如，利用Yao[5]提出的加密電路(Garbled Circuit)方案在實現SMPC時，首先把需要實現的函數轉換為等價的布爾電路(與門、或門、非門等構成的電路)，該電路可能非常龐大，實現起來效率極低，無法應用于實際。本文的目的之一就是提高分布式隱私保護數據挖掘的效率。

另外,本文從實際和理性參與方的角度來考慮分布式隱私保護數據挖掘問題，而不是像經典密碼學中所有的參與方都被簡單地劃分為誠實方或惡意方。本文假設各個參與方都是理性的，在此基礎上提出實現許多數據挖掘函數的高效協議，如求和、平均數、求積、頻繁數據項等。

理性密碼學是一個結合了博弈論與密碼學的研究領域[12-16]。文獻[17]研究了理性的秘密分享方案。Gordon等[18]對文獻[17]的方案進行了改進。文獻[19]提出K-彈性納什均衡的概念，是對經典納什均衡概念的加強，在此種均衡下，即使K個參與方共謀也不能提升他們的收益(傳統的納什均衡中K=1)。文獻[20]考慮了如何構建實用的隱私保護數據挖掘PPDM(Privacy-Preserving Data Mining)軟件工具箱，同本文的區別在于文獻[20]沒有半可信的第三方TP(Third Party)，而且不是從理性密碼學的角度來分析其安全性，所以本文的方案更高效、更安全。

本文給出了理性PPDM R-PPDM(Rational PPDM)框架和一些常用統計函數的具體例子，對本文構建的方案進行了安全分析，最后進行了總結并給出下一步研究的方向。

2 R-PPDM方案構建

2.1 R-PPDM具體方案構建

(1)求和。

設有n(n≥2)個參與方，每個參與方持有一個秘密數字Si(1≤i≤n)，數據挖掘方Miner希望計算所有Si之和，即:

S=S1+S2+S3+…+Sn

而每個參與方又不想公布共同擁有的秘密數字，因可能會涉及隱私,如Si可能代表的是工資、年齡、身高、體重、血壓等，即參與方的隱私要得到保護，在此前提下，各方愿意配合Miner來計算S值。

一個簡單的解決方案如下所示：

步驟1參與方Pi隨機選擇一個參與方Pj(i≠j,1≤i,j≤n)，并用兩方秘鑰分發協議[21]或量子秘鑰分發(Quantum Key Distribution)協議[22]等，來共同生成一個隨機數Rij；

步驟2參與方Pi更新其秘密Si為S′i=Si+Rij，參與方Pj更新其秘密值為S′j=Sj-Rij；

步驟3各方把更新后的秘密數字發送給Miner，Miner執行以下計算得到S′：

S′=S′1+S′2+S′3+…+S′n

顯然,雖然Si≠S′i,但S=S′。

圖1是一個有4個參與方(P1,P2,P3和P4)的簡單例子，其中TP表示可信第3方，設P1選擇了P3，那么P1和P3可協商一個隨機數R13，然后S1更新為S′1=S1+R13，而S3更新為S′3=S3-R13，P2選擇P4生成隨機數R24，更新S′2=S2+R24和S′4=S4-R24，P3選擇P4生成隨機數R34，那么S′3=S3-R13+R34和S′4=S4-R24-R34，最后P4選擇P1生成隨機數R41，更新S′4=S4-R24-R34+R41和S′1=S1+R13-R41，即：

S′1=S1+R13-R41

S′2=S2+R24

S′3=S3-R13+R34

S′4=S4-R24-R34+R41

顯然可見：

?i,Si≠S′i

S′1+S′2+S′3+S′4=S1+S2+S3+S4

求和，即求平均值(參與人數n已知)顯然有眾多的實用領域和價值，比如在研究某種疾病，如糖尿病、艾滋病和COVID-19等，研究人員希望獲取病人的某個生理指標的平均值，如體溫、血壓、血糖、身高和體重等，但這涉及到個人隱私，而利用前述方法則可在保護病人隱私的前提下得到這些生理指標平均值，有助于疾病的研究和防治。

(2)求積。

求積方法同前述求和方法類似，區別只在于求積要計算S′i=S′i*Rij和S′j=Sj/Rij，而不是S′i=Si+Rij和S′j=Sj-Rij。如上述4個參與方計算的例子，若此時要求積，那么可執行以下計算：

S′1=S1*R13/R41

S′2=S2*R24

S′3=S3/R13*R34

S′4=S4/R24/R34*R41

則有：

S′1*S′2*S′3*S′4=S1*S2*S3*S4

(3)比較與求距離。

設有2個百萬富翁，若要比較他們的財富多少，即哪個更富有，同時又不想公布他們的具體財產，那么，可用一個半可信的TP(Miner)進行如下操作：

步驟12個富翁相互通信來協商一個隨機數R，如利用上述的量子QKQ或兩方秘鑰分發協議；

步驟2然后他們各自對自己的財富值更新如下：S′1=S1+R和S′2=S2+R；

步驟3將更新后的財富值S′i(i=1,2)匿名發送給Miner，例如各自隨機選一個Miner計算機的接收端口號來傳輸；

步驟4Miner可以簡單地比較收到的2個值的大小，從而判斷出某個端口號的財富值勝出，而無需公布這2個值(若公布這2個值，雙方的隱私也能得到部分保護，因為此時雙方已知道了對方的財富值，但別人只知道雙方的財富差值而不知道各自具體的值是多少或誰更富有)。

此處雖然以歐氏距離為例進行了說明，但該方法同樣可以計算其他方式定義的距離。所以，結合前述平均值可以計算方差，如在疾病研究中計算某個生理指標的方差和概率分布等，這對疾病研究非常重要。另外，在車載互聯網中和交通規劃之中，利用此方法可在保護隱私的前提下計算車輛之間的距離，從而實現各種基于位置的規劃和應用，例如自動駕駛等?；诰嚯x的應用還有很多，比如廣告，即當用戶靠近某個地方時(在保證其隱私的前提下)向用戶手機發送特定廣告，還可用于在COVID-19防治中跟蹤病例的密切接觸者等。

(4)求頻繁項。

在頻繁項挖掘的應用中，n個參與方利用多方秘鑰協商協議[23]來協商一個隨機置換σ和一個隨機數R，對每種商品的標簽index進行如下隨機化處理：

index→σ(index)→σ(index)+R

然后把各自的商品/購買次數({index1,index2,…},times)對都發送給Miner，Miner可在本地運行Apriori等算法來挖掘出頻繁項后進行公布，這樣各個參與者可簡單地解碼得到真正的頻繁項挖掘結果。對Miner來說,收到的數據是經過隨機化處理的數據，沒有什么意義，從而保證了各個參與方的隱私。

2.2 R-PPDM一般框架

理性隱私保護數據挖掘的框架描述如下(如圖2所示)：

(1)參與角色：半可信的數據挖掘方Miner和n個參與方Pi，Pi擁有秘密值Si；

(2)給定一事先約定好的數據挖掘函數f(S1,S2,…,Sn)；

(3)理性假設：假設Miner和各參與方都是理性的。

接下來設計實用的協議安全地計算函數f，計算結果可公布，也可能不公開，僅供Miner做科學研究之用：

(1)針對要計算的數據挖掘函數f，n個參與方相互通信對各自的秘密信息Si進行有限隨機化(類似秘密分享)，即各自的Si隨機化為S′i，但總體上滿足：f(S1,S2,…,Sn)=f(S′1,S′2,…,S′n)；

(2)各方把隨機化的S′i發送給Miner，Miner可以通過簡單地計算f(S′1,S′2,…,S′n)得到數據挖掘的結果，即函數f(·)的值；

(3)函數f(·)的值對Miner可能有意義(如上述的求和)，也可能無意義(如上述的財富比較)，函數f(·)的值公布之后參與方才能解讀。

3 安全性分析

對R-PPDM的安全性分析是基于如下的理性假設和博弈模型：

(1)參與方(即秘密數據擁有者)：

①各參與方希望保護自己的隱私不被泄露，即各自的秘密信息不被其他方獲取(可以從挖掘結果中推出的信息除外)；

②在上述前提基礎上，各參與方希望Miner能獲得預定好的數據挖掘函數的函數值(比如Miner是科研工作者，那么其挖掘研究成果可能推動科學技術進步、預防控制疾病等)。

(2)數據挖掘方Miner：

①希望能獲得事先商定好的數據挖掘函數的函數值；

②不與任何一個參與方共謀來試圖獲取其他參與方的隱私數據(否則曝光后會影響其聲譽)；

③可以利用自己收到的數據進行任何的分析、計算來試圖獲取其他參與方的隱私數據(即使半可信的TP方)。

構建的具體博弈模型如下所示：

參與方為P1,P2,…,Pn,其中,

Pi的可選策略集合為{合作，不合作，合謀};數據挖掘方Miner的策略集為{誠實，合謀}，這里合謀指的是Pi與Miner合作幫助Miner獲取他人的隱私數據。

Pi的效用函數值：Up(正確結果)>Up(錯誤結果)>Up(自己的隱私數據暴露)；Miner的效用函數值：Um(正確結果且獲得他人隱私數據)>Um(正確結果)>Um(錯誤結果)>Um(丑聞曝光名譽受損)。

下面證明在平均意義下策略(合作，合作，…，誠實)為上述博弈(Game)的納什均衡，假設P1與Miner合謀，即(合謀，合作，…，合謀)，那么對P1來說收益沒有變化，而對Miner來說收益提高了，但此時也有行為曝光名譽受損的風險。設曝光概率為30%，并假設Miner的收益為1(結果正確并獲得他人隱私)> 0.6(結果正確)> 0(結果錯誤)>-1(曝光名譽受損)，則其收益的期望值為1*0.7+0.3*(-1)=0.4，小于其誠實而獲得的收益0.6。教訓就是在實踐中，只要對不誠實的Miner的處罰夠大，那么就能基本保證不會出現試圖偷竊他人數據的行為。其他策略的組合如(不合作，合作，…，誠實),顯然雙方收益都減少了，所以前述策略為納什均衡。

但是，如果相關參數發生變化，可能上述策略組合就不是納什均衡了，具體分析如下：

在作弊和誠實收益固定的情況下，期望收益與被曝光概率的關系如表1所示。

表1中,√標識了行為分界線，曝光的概率小于20%時，Miner的理性選擇為作弊，而大于此值其理性選擇為誠實。

當曝光概率固定(設為20%)時，懲罰力度與期望收益的關系如表2所示。

表2中,√標識了行為分界線，當懲罰力度小于-1時，Miner的理性選擇為作弊，而加大懲罰力度則其理性選擇為誠實。

Table 1 Relationship between exposure probability and expected payoff

Table 2 Relationship between punishment and expected payoff

由上述分析可知，在實際應用中要根據具體情況設置博弈模型參數，保證誠實和合作為納什均衡。

下面對前文構建的具體協議進行安全性分析：

(1)求和與求積協議的安全性分析：

①首先對于Miner來說，各參與方發給Miner的數據都是隨機值，如Pi發送的是Si+Rij，其中隨機數Rij只有參與方Pi和Pj掌握，而根據本文的安全性假設，Miner不會與其他參與方如Pj共謀，所以Miner無法知道Rij，那么他就不可能知道Pi的秘密值Si。

②對任一參與方Pi而言，只將加了隨機數的加密數據發送給Miner，不接收任何數據，所以不可能了解他人的秘密數據(除了能夠從最終挖掘結果和自身秘密數據推出的數據)；參與方可以提供虛假的數據，但此行為在經典密碼學中也不認為是安全威脅，而且本文理性假設各方愿意進行合作并提供真實的數據，以挖掘出真正有價值的信息和知識。

基于上述分析，還可以進一步加強本文求和協議的安全性，原來每個參與方的秘密值Si至少被一個隨機值掩蓋，因每個參與方Pi都要隨機選擇另一方Pj生成一個隨機數Rij，比如上述例子中的S′2=S2+R24，而有些秘密數據是被幾個隨機數所掩蓋，如上述例子中的S′3=S3-R13+R34；如果一個秘密數據Si只被一個隨機值Rij掩蓋，Miner只要與Pj同謀得到Rij就可獲取秘密數據Si，如前例中Miner只要和P4共謀獲取R24就可獲取P2的秘密數據S2=S′2-R24；而如果秘密數據被多個隨機數掩蓋，Miner就要與多個參與方同謀才能獲取秘密數據，如前例中若Miner想獲取P3的秘密數據S3，那么Miner就要與P1和P42個參與方同時共謀得到R13和R34，才能計算出S3=S′3+R13-R34，即此時秘密數據更安全。由此可以按如下方式來增強安全性：

當第1輪結束后，如果某方發現其秘密數據只被一個隨機數掩蓋(如上例中的P2)，那么此參與方就重復其在第1輪所做的操作，再隨機選擇一個其他參與方(同第1輪不同)生成一個隨機數對他們各自的秘密數據進行隱藏；所以經過第2輪之后，就能夠保證每個參與方的秘密數據都至少被2個以上的隨機數掩蓋，也即假如Miner想獲取某個參與方的秘密數據，那么他必須至少同2個以上的參與方合謀，而且Miner不知道此兩方的ID，類似地可以通過增加第三或更多的輪來進一步增強安全性，使得假如Miner若要獲取他人隱私數據就要同三方或更多方合謀才行。

(2)對前文中其他協議的安全性分析是類似的。比如對比較協議：Miner通過2個隨機的端口收到的是2個隨機值，不能得到2個參與方的具體財富值，對Miner而言方程組S′1=S1+R和S′2=S2+R有3個未知數，方程只有2個，也即有無窮多解，即任一R都是可能的解；而2個參與方只是向Miner發送數據和獲得公開的最終比較結果(如端口號1161的財富值更高)，不能了解另一方的具體財富值。

4 結束語

本文提出了一種基于理性密碼學的分布式隱私保護數據挖掘的框架，同傳統經典密碼學中的安全多方計算的安全性(即考慮每個成員是完全誠實的或是完全惡意的)相比，本文從實際應用角度、從每個參與方的內在激勵動機的角度出發，安全性假設更符合實際，所得出的協議比經典密碼學中的安全多方計算的協議效率更高，更適合在實際中應用，并通過具體的例子展示了如何在此框架下構建高效實用的協議。

未來的工作方向：(1)研究更多的數據挖掘函數，直至一般的任意函數，如何在所提框架下實現理性安全計算；(2)如何提升安全性、效率及其均衡性，即根據Miner的可信程度動態調整協議來適應不同的場合；(3)如何引入量子計算、糾纏來提升安全性和效率。