基于理性密碼學(xué)的分布式隱私保護數(shù)據(jù)挖掘框架*

程小剛,郭 韌,周長利

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

1 引言

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

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

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

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

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

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

2 R-PPDM方案構(gòu)建

2.1 R-PPDM具體方案構(gòu)建

(1)求和。

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

S=S1+S2+S3+…+Sn

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

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

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

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

步驟3各方把更新后的秘密數(shù)字發(fā)送給Miner，Miner執(zhí)行以下計算得到S′：

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

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

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

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

(2)求積。

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

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)比較與求距離。

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

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

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

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

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

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

(4)求頻繁項。

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

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

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

2.2 R-PPDM一般框架

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

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

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

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

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

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

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

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

3 安全性分析

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

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

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

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

(2)數(shù)據(jù)挖掘方Miner：

①希望能獲得事先商定好的數(shù)據(jù)挖掘函數(shù)的函數(shù)值；

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

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

構(gòu)建的具體博弈模型如下所示：

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

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

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

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

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

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

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

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

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

Table 1 Relationship between exposure probability and expected payoff

Table 2 Relationship between punishment and expected payoff

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

下面對前文構(gòu)建的具體協(xié)議進行安全性分析：

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

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

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

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

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

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

4 結(jié)束語

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

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