基于BCP 的聯(lián)合委托學(xué)習(xí)模型及協(xié)議

高勝，向康，田有亮，譚偉杰，馮濤，吳曉雪

（1.貴州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院公共大數(shù)據(jù)國家重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 550025；2.中央財(cái)經(jīng)大學(xué)信息學(xué)院，北京 100081；3.貴州大學(xué)密碼學(xué)與數(shù)據(jù)安全研究所，貴州 貴陽 550025；4.蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院，甘肅 蘭州 730050；5.貴州省計(jì)量測試院，貴州 貴陽 550000）

1 引言

機(jī)器學(xué)習(xí)等相關(guān)技術(shù)的發(fā)展使大數(shù)據(jù)中的有利信息得以被挖掘和利用。在實(shí)際生活中，數(shù)據(jù)的分布并不是只存在于一個(gè)數(shù)據(jù)站點(diǎn)，而是多樣化地分布于多個(gè)數(shù)據(jù)站點(diǎn)。因此，數(shù)據(jù)共享[1-2]已成為數(shù)據(jù)挖掘等相關(guān)領(lǐng)域的研究熱點(diǎn)，而數(shù)據(jù)隱私泄露等安全問題是數(shù)據(jù)共享技術(shù)中的發(fā)展瓶頸。傳統(tǒng)的基于安全多方計(jì)算（SMC,secure multi-party computation）[3-4]的解決方案效率低下且可行性較差，無法真正實(shí)現(xiàn)對大數(shù)據(jù)[5]的處理。

在實(shí)際的數(shù)據(jù)特征學(xué)習(xí)過程中，對數(shù)據(jù)進(jìn)行較復(fù)雜的分析、模型構(gòu)造以及優(yōu)化通常是比較困難的，導(dǎo)致客戶端背負(fù)著沉重的計(jì)算成本。甚至部分企業(yè)或用戶由于受限于自身對數(shù)據(jù)處理的能力而無法挖掘出有用的信息，只能依托于云服務(wù)[6-7]提供商進(jìn)行特征提取和模型訓(xùn)練。因此，基于傳統(tǒng)的委托計(jì)算思想引出數(shù)據(jù)多點(diǎn)分布時(shí)的數(shù)據(jù)外包挖掘方法具有重要的實(shí)際應(yīng)用價(jià)值。本文將這種數(shù)據(jù)外包挖掘的方式命名為聯(lián)合委托學(xué)習(xí)，如圖1 所示。

圖1 聯(lián)合委托學(xué)習(xí)

在數(shù)據(jù)多點(diǎn)分布時(shí)進(jìn)行聯(lián)合委托學(xué)習(xí)需要考慮以下需求。

1) 在數(shù)據(jù)共享中，不僅要避免用戶隱私數(shù)據(jù)的泄露，而且必須保證加密后的數(shù)據(jù)滿足數(shù)據(jù)挖掘的條件。

2) 避免服務(wù)器從計(jì)算的中間結(jié)果推測出最終構(gòu)建的模型信息。

3) 盡量將計(jì)算任務(wù)委托給云服務(wù)提供商，以降低客戶端的計(jì)算成本。

1.1 本文的貢獻(xiàn)

針對聯(lián)合委托學(xué)習(xí)中的安全性需求，本文的主要貢獻(xiàn)如下。

1) 基于傳統(tǒng)的委托計(jì)算思想提出了一種聯(lián)合委托學(xué)習(xí)模型，并針對決策樹的構(gòu)造設(shè)計(jì)了一種基于虛假記錄的隱私保護(hù)方法（FRPPM,false-based records privacy protection method），該方法利用少量的虛假記錄擾亂最終構(gòu)建的模型結(jié)構(gòu)，增強(qiáng)了數(shù)據(jù)和模型結(jié)構(gòu)的安全性。

2) 基于BCP（Bresson,Catalano,Pointcheval）同態(tài)加密算法分別設(shè)計(jì)了隱私保護(hù)委托點(diǎn)積算法（PPDDPA,privacy preserving delegation dot product algorithm）和隱私保護(hù)委托求熵算法（PPDEA,privacy preserving delegation entropy algorithm），降低了客戶端的隱私數(shù)據(jù)在數(shù)據(jù)共享中的泄露風(fēng)險(xiǎn)。

3) 針對數(shù)據(jù)垂直和水平分布的情況，根據(jù)上述2 種算法分別提出了對應(yīng)的委托學(xué)習(xí)協(xié)議，降低了客戶端在數(shù)據(jù)挖掘中的計(jì)算成本。

1.2 相關(guān)工作

隱私保護(hù)數(shù)據(jù)挖掘技術(shù)[8-9]可分為基于數(shù)據(jù)擾動(dòng)的方法和基于安全多方計(jì)算的方法?；跀?shù)據(jù)擾動(dòng)方面，Agrawal 等[10]提出了用加入隨機(jī)噪聲的方法來進(jìn)行隱私保護(hù)決策樹挖掘的方案。但此種加入隨機(jī)噪聲的方法過于簡單，Kargupta 等[11-12]對加入隨機(jī)噪聲方法的安全性提出了質(zhì)疑，并基于隨機(jī)矩陣?yán)碚撎岢隽藦臄_動(dòng)后的數(shù)據(jù)估計(jì)真實(shí)數(shù)據(jù)的方法。Bu 等[13]給出了一種基于函數(shù)擾動(dòng)的方法，該方法采用反函數(shù)變換方式來將擾動(dòng)數(shù)據(jù)上的虛假?zèng)Q策樹還原為真實(shí)數(shù)據(jù)上的決策樹。

基于安全多方計(jì)算方面，Hamada 等[14]及Bost等[15]分別研究了可以應(yīng)用于SMC 中的決策樹分類算法，在SMC 中向各參與方隱藏了輸入向量，但有關(guān)決策樹的信息被假定對各方公開。其中，Bost等[15]研究了使用同態(tài)加密通過決策樹對信息進(jìn)行安全分類的方法。隨后，Wu 等[16]及Backes 等[17]各自將其擴(kuò)展為一個(gè)隨機(jī)森林。此外，在與本文的工作相似的研究中，Ichikawa 等[18]提出了一種新穎的安全多方協(xié)議，同樣隱藏了輸入向量和輸出類以及樹的結(jié)構(gòu)。Zheng 等[19]及Li 等[20]分別設(shè)計(jì)了基于云服務(wù)器的分類模型，可以保護(hù)樹模型和客戶數(shù)據(jù)隱的分類模型提高了系統(tǒng)的可伸縮性。特別地，Li 等[22]私。另外，Liu等[21]在此基礎(chǔ)上設(shè)計(jì)了支持離線服務(wù)針對數(shù)據(jù)的水平和垂直分布分別設(shè)計(jì)了外包隱私保護(hù)加權(quán)平均協(xié)議（OPPWAP,outsourced privacy preserving weighted average protocol）和外包安全集交叉協(xié)議（OSSIP,outsourced secure set intersection protocol），但不能保護(hù)訓(xùn)練模型結(jié)構(gòu)的安全性。

2 預(yù)備知識

2.1 BCP 同態(tài)加密

BCP 同態(tài)加密算法是由Bresson、Catalano 和Pointcheval 于2003 年提出的，屬于同態(tài)密碼體制，具有以下性質(zhì)。

其中，m1和m2表示明文信息，⊙表示在同一公鑰下加密域中的算術(shù)乘法運(yùn)算。BCP 同態(tài)加密算法的形式化描述包括以下4 個(gè)部分。

1) Setup(λ)。首先給定安全參數(shù)λ表示模數(shù)N的位長，再選定2 個(gè)不同的素?cái)?shù)p'和q'分別計(jì)算p=2p'+1，q=2q'+1以及N=pq；隨后選擇表示在2[1,N]中所有與N2互質(zhì)的數(shù)），并使最后得到公共參數(shù)pp=(N,k,g)，主 密 鑰

3) Encpk(m)。明文m∈ZN，選擇隨機(jī)數(shù)，利用公鑰加密得到密文(A,B)，其中A=grmodN2，B=gtr(1+mN)modN2。

4) Decsk(A,B)。利用私鑰sk=t解密，獲得明文。

2.2 數(shù)據(jù)的分布形式

通常數(shù)據(jù)的分布類型包括2 種情況：水平分布類型，即每個(gè)站點(diǎn)僅包含一部分元組，但每個(gè)元組都是完整的；垂直分布類型，即各個(gè)站點(diǎn)包含所有元組，但每個(gè)元組都不是完整的，僅包含一部分屬性。如表1 中前14 條記錄所示，為方便敘述，此處假設(shè)數(shù)據(jù)分布在站點(diǎn)P1和P2處。數(shù)據(jù)水平分布時(shí)，站點(diǎn)P1和P2分別包含部分完整的記錄，同時(shí)各站點(diǎn)都知道數(shù)據(jù)所對應(yīng)的屬性名稱，即表1 中的第二行信息，但各個(gè)站點(diǎn)對其他站點(diǎn)所包含的具體數(shù)據(jù)一無所知。數(shù)據(jù)垂直分布時(shí)，站點(diǎn)P1和P2都包含所有記錄，但每條記錄都是不完整的，對于所有特征屬性而言站點(diǎn)P1只包含前2 個(gè)屬性的數(shù)據(jù)，站點(diǎn)P2只包含后2 個(gè)屬性的數(shù)據(jù)，但它們都包含標(biāo)簽項(xiàng)數(shù)據(jù)，即表1 中的最后一列信息，同樣各個(gè)站點(diǎn)不愿意對其他站點(diǎn)透露自己所包含的具體數(shù)據(jù)。

表1 數(shù)據(jù)集的分布形式

3 聯(lián)合委托學(xué)習(xí)模型

3.1 系統(tǒng)模型

聯(lián)合委托學(xué)習(xí)的系統(tǒng)模型框架如圖2 所示，系統(tǒng)模型包含2 個(gè)服務(wù)器和n個(gè)客戶端（用戶），并且相互之間采用安全信道連接。其中 S1是主服務(wù)器，S2是副服務(wù)器，分別由不同的服務(wù)提供商提供。首先，由 S2生成公共參數(shù)并發(fā)送給各客戶端，客戶端根據(jù)公共參數(shù)計(jì)算出各自的公私鑰對。其次，客戶端根據(jù)FRPPM 對各自的私有數(shù)據(jù)集進(jìn)行擾動(dòng)處理，并利用各自的公鑰對擾動(dòng)后的數(shù)據(jù)統(tǒng)計(jì)信息進(jìn)行加密。然后，將A、B這2 類密文分別發(fā)送給 S2和 S1進(jìn)行計(jì)算，并由 S1綜合計(jì)算后返回結(jié)果。最后，各客戶端根據(jù)返回的結(jié)果構(gòu)建同樣的決策樹模型。需要注意的是，無論數(shù)據(jù)垂直分布還是水平分布，本文在模型的構(gòu)建過程中都以ID3[23]算法為例。為方便后續(xù)描述，假設(shè)總體數(shù)據(jù)集D分布在n個(gè)客戶端處，即D=D1∪D2∪…∪Dn，并且共有t條記錄、d個(gè)屬性和一個(gè)分類標(biāo)簽項(xiàng)C，其中屬性集a={a1,a2,…,ad}，且各屬性有U個(gè)可能的取值

圖2 聯(lián)合委托學(xué)習(xí)的系統(tǒng)模型框架

3.2 安全模型

假設(shè)所有的參與者和服務(wù)器都是半誠實(shí)的并且不存在共謀行為，即服務(wù)器會認(rèn)真完成客戶端的計(jì)算任務(wù)但對計(jì)算結(jié)果好奇，客戶端會誠實(shí)地提供自己的密文數(shù)據(jù)但同樣好奇其他客戶端的數(shù)據(jù)，并且服務(wù)器不具備數(shù)據(jù)集屬性名及其取值類別信息等先驗(yàn)知識。

模型假設(shè)每個(gè)客戶端都有私有數(shù)據(jù)對(xi,yi)，其中i=(1,2,…,n)，客戶端之間不愿透露數(shù)據(jù)真實(shí)值但又希望利用其他人的數(shù)據(jù)計(jì)算最終結(jié)果R。

初始化階段。由服務(wù)器 S2生成公共參數(shù)pp=(N,k,g)并分發(fā)給每一個(gè)客戶端。各客戶端選擇隨機(jī)數(shù)生成各自的公鑰pki和私鑰ski，即

輸出階段。服務(wù)器 S1將最終計(jì)算結(jié)果R返回給每一個(gè)客戶端。

4 基于虛假記錄的隱私保護(hù)方法

本節(jié)針對決策樹的構(gòu)造提出了一種新的隱私保護(hù)方法。該方法類似于數(shù)據(jù)擾動(dòng)的方法，但與之不同的是客戶端不在原始數(shù)據(jù)中做擾動(dòng)操作，而是添加完整的虛假記錄來達(dá)到擾動(dòng)效果。

以表1 中的數(shù)據(jù)為例，前14 條記錄是真實(shí)的數(shù)據(jù)，最后2 條是添加的虛假記錄。換句話說，在原始數(shù)據(jù)屬性outlook 的取值情況中并沒有foggy類型，同樣其他屬性也都沒有對應(yīng)的cold、low、calm以及breezy 的取值類型。簡而言之，最后2 條記錄是虛構(gòu)的，其目的在于通過添加虛假記錄的方式來生成干擾樹枝，使服務(wù)器無法辨認(rèn)決策樹分支的真實(shí)性。

以ID3 算法為例，表1 中的數(shù)據(jù)可以生成如圖3所示的決策樹T'。

圖3 具有干擾分支的決策樹T '

圖3 中，虛線框中的分支就是生成的干擾分支，當(dāng)所有節(jié)點(diǎn)以及分支信息處于加密狀態(tài)時(shí)，服務(wù)器是很難猜測或分辨分支的真實(shí)性的，而客戶端解密后通過后剪枝的方式剪掉虛假的分支可以輕松獲得真實(shí)決策樹T。

在添加虛假記錄進(jìn)行擾動(dòng)時(shí)，有以下兩點(diǎn)是需要注意的。

1) 由于ID3 算法的核心是以屬性的信息增益大小來確定決策樹各節(jié)點(diǎn)的劃分屬性的，因此，在添加虛假記錄后要保證真實(shí)數(shù)據(jù)中原本信息增益最高的屬性仍保持最高。例如，在表1 的真實(shí)數(shù)據(jù)中，屬性outlook 的信息增益最大，當(dāng)加入虛假記錄后仍要保證屬性outlook 的信息增益最大，否則就破壞了真實(shí)決策樹的結(jié)構(gòu)，根節(jié)點(diǎn)不再是屬性outlook，也就是說，降低了決策樹模型的分類精度。

2) 添加虛假記錄的方法在提高安全的同時(shí)，也由于增加虛假數(shù)據(jù)集D'導(dǎo)致挖掘計(jì)算量增大。因此本文限定添加的虛假數(shù)據(jù)集為原真實(shí)數(shù)據(jù)集的2%～15%，當(dāng)增加的計(jì)算量在可接受的范圍內(nèi)時(shí)，客戶端應(yīng)盡量增加更多根節(jié)點(diǎn)可能取值的虛假類別以提高決策樹的安全性，這一點(diǎn)將在后續(xù)的安全性分析章節(jié)進(jìn)行具體介紹。另外，n個(gè)客戶端在聯(lián)合委托學(xué)習(xí)之前可以通過協(xié)商確定添加的虛假數(shù)據(jù)集D'或由某一個(gè)客戶端設(shè)定虛假數(shù)據(jù)集分發(fā)給其他客戶端。當(dāng)數(shù)據(jù)垂直分布時(shí)，各客戶端也應(yīng)將數(shù)據(jù)集D'垂直分割，因此各客戶端添加的記錄數(shù)為|D'|；當(dāng)數(shù)據(jù)水平分布時(shí)，則每個(gè)客戶端添加的數(shù)據(jù)量為

5 聯(lián)合委托學(xué)習(xí)協(xié)議

根據(jù)第3 節(jié)和第4 節(jié)提出的聯(lián)合委托學(xué)習(xí)模型及基于虛假記錄的隱私保護(hù)方法，可以設(shè)計(jì)以下數(shù)據(jù)在不同分布形式時(shí)的委托學(xué)習(xí)協(xié)議。

5.1 數(shù)據(jù)垂直分布的委托學(xué)習(xí)協(xié)議

當(dāng)數(shù)據(jù)垂直分布時(shí)，各客戶端雖然包含的記錄信息不完整，但可以使用布爾化向量表示數(shù)據(jù)在各屬性上的取值情況。例如，在表1 中，P1使用向量表示所有記錄在屬性 outlook 上取值為sunny 的情況

其中，“1”表示該記錄在屬性outlook 上取值為sunny，“0”表示取其他值。同理，P2可以表示所有記錄在屬性humidity 上取值為high 的情況

盡管P1和P2之間都不愿透露各自的數(shù)據(jù)信息，但可以通過向量點(diǎn)積來獲得同時(shí)滿足在屬性outlook 和humidity 上分別取值為sunny 和high 的記錄數(shù)。其中，求解點(diǎn)積的過程可以看作第3.2 節(jié)安全模型中假設(shè)的一部分，如

根據(jù)以上描述，各客戶端可以將各自的私有向量加密后發(fā)送給服務(wù)器，由服務(wù)器代理進(jìn)行點(diǎn)積運(yùn)算，具體如算法1 所示。

算法1隱私保護(hù)委托點(diǎn)積算法

輸入每個(gè)客戶端分別輸入各自(t+|D'|)維的隱私向量Vi

輸出結(jié)果R

1) 服務(wù)器 S2采用BCP 同態(tài)加密算法生成公共參數(shù)pp 并分發(fā)給各客戶端。

3) 各客戶端利用各自的公鑰對向量Vi中每一個(gè)元素進(jìn)行加密，得到密文向量對并將分別發(fā)送給服務(wù)器 S2和 S1。

4) 服務(wù)器 S2接收到各方發(fā)送的向量后做如下計(jì)算。

令j=1，中的第

j個(gè)元素vi,j計(jì)算，將vj加入向量VA中，j=j+1}，最后將向量VA發(fā)送給服務(wù)器 S1。

5) 服務(wù)器 S1接收到各客戶端及服務(wù)器 S2發(fā)送的向量后做如下計(jì)算。

令j=1，R=0，while(j≤t+|D'|) do {取及VA中第j個(gè)元素vi,j及vj計(jì)算

if(m≤ 1)令m=0,else 令m=1,R=R+m,

j=j+1}

6) 服務(wù)器 S1將結(jié)果R返回給各客戶端。

根據(jù)上述算法，可以設(shè)計(jì)數(shù)據(jù)垂直分布時(shí)的聯(lián)合委托學(xué)習(xí)協(xié)議，具體介紹如下。

1) 各客戶端利用自身的數(shù)據(jù)計(jì)算出數(shù)據(jù)集D的信息熵

其中，K表示數(shù)據(jù)集D中分類標(biāo)簽項(xiàng)可能取值的類別數(shù)，pk表示第k個(gè)類別的樣本所占的比例，k={1,2,…,K}。

2) 各客戶端計(jì)算出各自所具有的屬性信息增益大小，以此來共同確定信息增益最大的屬性并作為決策樹的根節(jié)點(diǎn)。

其中，Du表示在第u個(gè)分支中包含的D中所有在屬性ai上取值為的樣本集，u={1,2,…,U}。

3) 各客戶端共同協(xié)商決定添加虛假記錄的數(shù)量以及虛假數(shù)據(jù)的具體值，并將數(shù)據(jù)集D和D'布爾化，用布爾型向量表示所有記錄在某一個(gè)屬性上的取值情況。

4) 由當(dāng)前劃分（只有一個(gè)節(jié)點(diǎn)時(shí)指根節(jié)點(diǎn)）屬性所屬的客戶端計(jì)算出各分支的信息熵并發(fā)送給其他客戶端。若某分支的信息熵為零，則直接標(biāo)記該分支為葉子節(jié)點(diǎn)，否則共同委托服務(wù)器計(jì)算該分支的其他信息，以便選取該分支的劃分屬性。

5) 各客戶端將各自的私有向量加密后發(fā)送給服務(wù)器，并由服務(wù)器返回計(jì)算結(jié)果。

6) 各客戶端根據(jù)結(jié)果R計(jì)算出各屬性的信息增益并確定信息增益最大的屬性為該分支節(jié)點(diǎn)。再返回到步驟4)，以類似的方式遞歸地構(gòu)造樹的其他節(jié)點(diǎn)。

下面，以表1 中的數(shù)據(jù)為例，說明上述協(xié)議的具體執(zhí)行過程。

1) 由于站點(diǎn)P1和P2都擁有標(biāo)簽項(xiàng)數(shù)據(jù)和不完整的記錄數(shù)據(jù)，因此各客戶端可以利用自身的數(shù)據(jù)計(jì)算出數(shù)據(jù)集D的信息熵

2) 站點(diǎn)P1和P2也可以計(jì)算出各自所具有的屬性信息增益大小，并發(fā)布給其他客戶端。

因此選擇屬性outlook 為根節(jié)點(diǎn)。

3) 雖然P1和P2可以在不透露具體數(shù)據(jù)的情況下共同確定根節(jié)點(diǎn)，但余下的所有分支節(jié)點(diǎn)必須利用整個(gè)數(shù)據(jù)集信息計(jì)算才能確定。因此在確定根節(jié)點(diǎn)后，P1和P2需要將各自數(shù)據(jù)的統(tǒng)計(jì)信息委托給服務(wù)器進(jìn)行整合計(jì)算，為了保證數(shù)據(jù)以及模型的安全，首先P1和P2需要共同協(xié)商決定添加虛假記錄并將數(shù)據(jù)集布爾化。

4) 由P1計(jì)算outlook 屬性劃分的4 個(gè)分支的信息熵，其中包括foggy 分支。例如，式(12)計(jì)算的sunny 分支不為零，因此該分支下的節(jié)點(diǎn)為非葉子節(jié)點(diǎn)。

P1將Ent(Ds)發(fā)送給P2，并聯(lián)合P2將各自數(shù)據(jù)的統(tǒng)計(jì)信息發(fā)送給服務(wù)器計(jì)算其余3 個(gè)屬性在該分支下的信息增益情況。例如計(jì)算humidity 屬性的信息增益值。用Ds_h和Ds_n分別表示當(dāng)屬性outlook 取sunny、屬性humidity 取high 和normal時(shí)的樣本集，則

其中，Ds_h_y和Ds_h_n分別表示當(dāng)屬性outlook 及humidity 取值為sunny 和high 時(shí)，標(biāo)簽項(xiàng)play 取值為yes 和no 的樣本集。同理，Ds_n_y和Ds_n_n也分別表示對應(yīng)的樣本集。

5) 在計(jì)算各屬性的信息增益過程中，各站點(diǎn)需要知道當(dāng)前分支的樣本數(shù)等數(shù)據(jù)信息，但由于各站點(diǎn)之間不愿透露自己的數(shù)據(jù)樣本信息，因此通過第三方服務(wù)器進(jìn)行代理計(jì)算。例如，若站點(diǎn)P2想要知道在sunny 分支中的樣本數(shù)，則可以聯(lián)合站點(diǎn)P1分別將向量V和Vs加密后發(fā)送給服務(wù)器，讓其代理計(jì)算出在sunny 分支中的樣本數(shù)|Ds|=Vs?V，并返回給站點(diǎn)P2。其中，向量V是(t+|D'|)維的通用向量，其所有元素都為1。

類似地，站點(diǎn)P1使用向量

表示所有記錄在屬性outlook 及標(biāo)簽項(xiàng)play 上的取值情況，其中“1”表示該條記錄同時(shí)滿足在屬性outlook 及標(biāo)簽項(xiàng)play 上分別取值為sunny 和yes，“0”表示不滿足。同理，向量Vs_n表示所有記錄在屬性outlook 及標(biāo)簽項(xiàng)上分別取值sunny 和no 的情況。在站點(diǎn)P2的數(shù)據(jù)中，向量Vh表示所有記錄在humidity 屬性上取值為high 的情況，向量Vn表示所有記錄在humidity 屬性上取值為normal 的情況。站點(diǎn)P1和P2分別將

加密后發(fā)送給服務(wù)器，可以得到對應(yīng)的計(jì)算結(jié)果。

6) 站點(diǎn)P1和P2收到服務(wù)器返回的結(jié)果后，各自可以計(jì)算出相同的humidity 屬性信息增益數(shù)據(jù)。再返回到步驟4)，以相同的方式，站點(diǎn)P1和P2可以計(jì)算出余下2 個(gè)屬性的信息增益大小，并選擇信息增益最大的屬性作為sunny 分支下的劃分節(jié)點(diǎn)。以類似的方式遞歸地構(gòu)造樹的其他節(jié)點(diǎn)，最后站點(diǎn)P1和P2都可以構(gòu)造出圖3 中完整的決策樹T'，經(jīng)過剪掉虛假的分支后獲得真正的決策樹T。

5.2 數(shù)據(jù)水平分布的委托學(xué)習(xí)協(xié)議

與數(shù)據(jù)垂直分布的情況不同，數(shù)據(jù)水平分布時(shí)各客戶端無法根據(jù)自身的數(shù)據(jù)計(jì)算出總體數(shù)據(jù)的信息熵和各屬性的信息增益，只能委托服務(wù)器作為中間節(jié)點(diǎn)進(jìn)行代理計(jì)算。

根據(jù)式(7)可以看出，計(jì)算總體數(shù)據(jù)的信息熵需要各客戶端提供各自數(shù)據(jù)的統(tǒng)計(jì)信息，即

其中，Di,k表示在第i個(gè)客戶端的數(shù)據(jù)中屬于第k類樣本的數(shù)據(jù)集。式(17)同樣可以看作第3.2 節(jié)中安全模型的假設(shè)形式

假設(shè)各客戶端使用向量

表示該客戶端的數(shù)據(jù)所屬類別的統(tǒng)計(jì)信息，其中，|Di|表示該客戶端具有的數(shù)據(jù)量；使用向量

下面，給出多個(gè)客戶端委托服務(wù)器代理計(jì)算的具體算法，如算法2 所示。

算法2隱私保護(hù)委托求熵算法

輸入每個(gè)客戶端{(lán)Pi|1≤i≤n}分別輸入各自的隱私向量Vi,D、Vi,j以及向量組

輸出以第j個(gè)屬性劃分的信息增益Gain(D,aj)

根據(jù)算法2，可以設(shè)計(jì)如下數(shù)據(jù)水平分布的聯(lián)合委托學(xué)習(xí)協(xié)議。

1) 各客戶端以向量的形式表示自身數(shù)據(jù)所屬類別信息。經(jīng)過各自公鑰加密后將A、B兩類密文分別發(fā)送給服務(wù)器 S2和 S1，計(jì)算得到整體數(shù)據(jù)集（或分支包含的子數(shù)據(jù)集）的信息熵。

2) 類似地，各客戶端以向量Vi,j和的形式表示數(shù)據(jù)在第j個(gè)屬性上的取值情況。通過委托服務(wù)器進(jìn)行代理計(jì)算，可以獲得所有屬性的信息增益數(shù)據(jù)，將信息增益最大的屬性作為節(jié)點(diǎn)（當(dāng)前沒有節(jié)點(diǎn)時(shí)作為根節(jié)點(diǎn)）屬性。

3) 確定根節(jié)點(diǎn)后，各客戶端協(xié)商確定添加虛假記錄的數(shù)量|D'|及具體數(shù)據(jù)值，并且每一個(gè)客戶端添加的虛假記錄數(shù)都為

4) 返回執(zhí)行步驟1)，客戶端采用同樣的方式發(fā)送虛假的統(tǒng)計(jì)信息委托服務(wù)器計(jì)算根節(jié)點(diǎn)下各分支的信息熵。若某分支的信息熵為零，即表示該分支所包含的樣本屬于同一類別，則客戶端直接標(biāo)記該分支為此類別的葉子節(jié)點(diǎn)。否則執(zhí)行步驟2)，委托服務(wù)器計(jì)算出該分支下的所有屬性信息增益，選擇信息增益最大的屬性作為該分支的節(jié)點(diǎn)屬性。

5) 反復(fù)執(zhí)行步驟1)和步驟2)，以類似的方式遞歸地構(gòu)造樹的其他節(jié)點(diǎn)。

6 安全性及性能分析

6.1 安全性分析

本節(jié)從客戶端的數(shù)據(jù)與最終構(gòu)建的決策樹模型2 個(gè)方面分析本文所提出的隱私保護(hù)委托算法和學(xué)習(xí)協(xié)議的安全性。

1) 當(dāng)服務(wù)器 S2不能同時(shí)獲得數(shù)據(jù)的密文A和B時(shí)，客戶端的數(shù)據(jù)是安全的。

證明服務(wù)器 S2利用主密鑰MK=(p',q')解密的過程如下。

①利用客戶端的公鑰計(jì)算出對應(yīng)的私鑰。

其中，k?1表示k模N的逆。

②利用密文A計(jì)算出客戶端在加密過程中選擇的隨機(jī)數(shù)r。

③令δ表 示p'q'模N的 逆，并 且γ=(sk ?r)modN，則明文為

從上述解密過程可以看出，當(dāng)服務(wù)器 S2利用主密鑰解密時(shí)，必須同時(shí)具有密文(A,B)才能獲得明文m，但在本文所設(shè)計(jì)的安全模型中，各客戶端是將其密文A和B分別發(fā)送給不同的服務(wù)器做求和運(yùn)算，并最終由服務(wù)器 S1計(jì)算出構(gòu)建決策樹模型的中間結(jié)果。因此當(dāng)服務(wù)器 S1和 S2之間不存在共謀行為時(shí)，任何一個(gè)服務(wù)器都不會具備解密數(shù)據(jù)的基本條件。綜上所述，客戶端的數(shù)據(jù)是安全的。

2) 當(dāng)數(shù)據(jù)集的屬性個(gè)數(shù)d等基本參數(shù)足夠大時(shí)，最終構(gòu)建的決策樹模型是安全的，即服務(wù)器不能從中間結(jié)果推測出真正的模型。

證明在數(shù)據(jù)垂直分布的情況中，隱私保護(hù)委托點(diǎn)積算法只要求服務(wù)器對布爾化后的向量做內(nèi)積運(yùn)算，因此服務(wù)器并不了解數(shù)據(jù)的真實(shí)意義和計(jì)算目的，所以，很難猜測出有關(guān)決策樹模型的任何信息。而在數(shù)據(jù)水平分布的情況中，服務(wù)器 S1根據(jù)計(jì)算信息熵和信息增益的結(jié)果，可以構(gòu)造出如圖4所示的空模型框架。

圖4 決策樹空模型框架

為方便描述，假設(shè)客戶端在添加虛假記錄的過程中，將根節(jié)點(diǎn)屬性的取值類別增加了l個(gè)可能的虛假取值，并且最終構(gòu)建的決策樹模型有e個(gè)非葉子節(jié)點(diǎn)、f個(gè)中間葉子節(jié)點(diǎn)和h個(gè)底層葉子節(jié)點(diǎn)。首先，服務(wù)器能夠正確匹配所有非葉子節(jié)點(diǎn)對應(yīng)的節(jié)點(diǎn)屬性的概率可以表示為

其次，服務(wù)器能正確匹配所有葉子節(jié)點(diǎn)對應(yīng)的類別信息的概率可表示為

最后，服務(wù)器能正確剪掉虛假分支的概率可以表示為

因此，服務(wù)器能正確獲得完整的決策樹模型的概率為

根據(jù)式(29)可知，當(dāng)數(shù)據(jù)集的屬性個(gè)數(shù)d等基本參數(shù)以及根節(jié)點(diǎn)屬性可能的虛假取值數(shù)l足夠大時(shí)，服務(wù)器能猜測模型的概率p是可以忽略的，同時(shí)也說明了當(dāng)增加虛假記錄的數(shù)量在可接受的范圍時(shí)，l的值越大越能提高模型的安全性。

另外，值得注意的是，上述服務(wù)器能夠正確獲得完整決策樹的概率p是基于服務(wù)器了解數(shù)據(jù)集基本信息的情況下才成立的。即只有當(dāng)服務(wù)器知道該數(shù)據(jù)集有哪些具體的屬性名及各屬性可能的取值時(shí)，才能了解該數(shù)據(jù)集的用途并對模型框架進(jìn)行匹配和猜測。然而在本文提出的算法中，客戶端并未透露任何關(guān)于數(shù)據(jù)集的基本信息，因此進(jìn)一步降低了服務(wù)器根據(jù)中間計(jì)算結(jié)果對模型進(jìn)行推測的概率。

綜上所述，本文提出的聯(lián)合委托學(xué)習(xí)協(xié)議構(gòu)建的決策樹模型是安全的。

6.2 性能分析

本節(jié)通過對比客戶端與服務(wù)器的時(shí)間開銷來評估本文所提出的算法和協(xié)議的性能。實(shí)驗(yàn)測試中使用Python 實(shí)現(xiàn)了PPDDPA 和PPDEA，建立了安全參數(shù)λ為1 024 的BCP 密碼系統(tǒng)，并在Ubuntu 18.04（CPU主頻為2.6 GHz，型號為Core i5-3230M，內(nèi)存為4 GB）的設(shè)備上進(jìn)行了測試。為了避免網(wǎng)絡(luò)時(shí)延的影響，本文在同一設(shè)備上模擬所有客戶端和服務(wù)器。

首先，對PPDDPA 和PPDEA 的性能進(jìn)行了測試，設(shè)定每個(gè)客戶端的隱私向量是1 000 維，相當(dāng)于數(shù)據(jù)集的記錄數(shù)為1 000，特征屬性個(gè)數(shù)d＞500。如圖5 所示，在PPDDPA 的性能測試中可以看出，兩服務(wù)器的時(shí)間花銷總和及各參與的客戶端的時(shí)間花銷幾乎不隨著客戶端的數(shù)量增加而增加，這表明PPDDPA 的性能幾乎不受客戶端數(shù)量的影響。其實(shí)在該算法的執(zhí)行過程中也可以看出這一點(diǎn)，每當(dāng)該算法執(zhí)行一次時(shí)，不管客戶端的數(shù)量是多少，實(shí)際上只有2 個(gè)客戶端參與其中并只對各自的向量進(jìn)行加密操作，同時(shí)服務(wù)器也只對2 個(gè)向量做點(diǎn)乘運(yùn)算。

圖5 PPDDPA 性能測試

在PPDEA 的測試中，每個(gè)客戶端都有1 000 條數(shù)據(jù)記錄，因此每一個(gè)客戶端都會參與其中，從圖6可以看出，服務(wù)器的時(shí)間花銷隨著客戶端數(shù)量的增加而顯著增加，而各客戶端的時(shí)間花銷幾乎不受影響。同樣也可以從該算法的執(zhí)行過程看出，各客戶端僅執(zhí)行向量加密操作，而服務(wù)器的計(jì)算量隨著客戶端數(shù)量的增加而增大。綜上所述，本文提出的算法不僅適用于少量客戶端聯(lián)合委托學(xué)習(xí)的情況，而且在大量客戶端參與時(shí)也能保證各客戶端的數(shù)據(jù)加密成本不隨客戶端數(shù)量的增加而增大。

圖6 PPDEA 性能測試

其次，利用急性肝功能衰竭疾病預(yù)測數(shù)據(jù)集對本文提出的協(xié)議與OPPC4.5[22]協(xié)議進(jìn)行了對比測試。由于該數(shù)據(jù)集只包含29 個(gè)特征屬性，因此設(shè)定參與的客戶端數(shù)量最大為29，并且插入的虛假記錄數(shù)為200條。如圖7 所示，當(dāng)數(shù)據(jù)垂直分布時(shí)，在本文所提出的協(xié)議中由于客戶端需要提前計(jì)算出整體數(shù)據(jù)集的信息熵并布爾化數(shù)據(jù)集，因此計(jì)算成本略高于OPPC4.5 協(xié)議，但從整體來看客戶端與服務(wù)器對模型訓(xùn)練的總成本略低于OPPC4.5 協(xié)議。從圖8 中可以看出，當(dāng)數(shù)據(jù)水平分布時(shí)，在本文所提出的協(xié)議中客戶端的計(jì)算成本顯著低于OPPC4.5 協(xié)議，因?yàn)槟Ｐ陀?xùn)練的計(jì)算過程幾乎完全由服務(wù)器處理，客戶端僅需對數(shù)據(jù)進(jìn)行統(tǒng)計(jì)和加密操作。因此也說明當(dāng)數(shù)據(jù)水平分布時(shí)，客戶端的計(jì)算負(fù)擔(dān)得到了顯著改善。

圖7 數(shù)據(jù)垂直分布的協(xié)議性能測試

圖8 數(shù)據(jù)水平分布的協(xié)議性能測試

最后，以表1 中的數(shù)據(jù)對本文提出的基于虛假記錄的隱私保護(hù)方法進(jìn)行了測試。如圖9 所示，無論數(shù)據(jù)分布情況如何，客戶端最終都可以構(gòu)建正確的決策樹模型T。而在服務(wù)器側(cè)，當(dāng)數(shù)據(jù)垂直分布時(shí)，兩服務(wù)器都得不到任何關(guān)于模型的信息。當(dāng)數(shù)據(jù)水平分布時(shí)，只有服務(wù)器S1可以推測出如圖10 所示的模型框架，且僅能使用不確定的信息（字母）代替節(jié)點(diǎn)和分支的信息。對于機(jī)器學(xué)習(xí)模型訓(xùn)練而言，學(xué)習(xí)的過程就是對模型參數(shù)的調(diào)參過程，而沒有參數(shù)的模型是毫無價(jià)值的。通常隱私保護(hù)的決策樹挖掘方法均使用隱藏節(jié)點(diǎn)名稱達(dá)到保密的目的，本文在此基礎(chǔ)上增加了虛假分支的方法（圖10 中A 節(jié)點(diǎn)下的分支中(a,c,d)必有一個(gè)分支是虛假的）以此來擾動(dòng)決策樹模型結(jié)構(gòu)，進(jìn)一步提升了決策樹模型的安全性。

圖9 客戶端最終獲得的模型T

圖10 S1 可推測的虛假模型框架

7 結(jié)束語

為降低用戶隱私數(shù)據(jù)在數(shù)據(jù)共享過程中的泄露風(fēng)險(xiǎn)，同時(shí)減少客戶端在數(shù)據(jù)挖掘過程中的計(jì)算成本，本文基于傳統(tǒng)的委托計(jì)算思想和BCP 同態(tài)加密算法提出了一種聯(lián)合委托學(xué)習(xí)模型，該模型采用雙服務(wù)器分別計(jì)算客戶端的部分密文信息的方式來降低數(shù)據(jù)共享中的隱私泄露風(fēng)險(xiǎn)。進(jìn)一步地，針對決策樹的安全構(gòu)造，提出了一種基于虛假記錄的隱私保護(hù)方法，該方法利用少量的虛假記錄改變了數(shù)據(jù)統(tǒng)計(jì)的真實(shí)結(jié)果，并對決策樹的模型結(jié)構(gòu)進(jìn)行擾動(dòng)，避免了服務(wù)器獲得真實(shí)的中間計(jì)算結(jié)果和最終訓(xùn)練的模型結(jié)構(gòu)。另外，分別對數(shù)據(jù)垂直分布和水平分布的情況設(shè)計(jì)了隱私保護(hù)委托算法及聯(lián)合委托學(xué)習(xí)協(xié)議，在保證數(shù)據(jù)安全共享的同時(shí)降低了客戶端的計(jì)算成本。最后，通過實(shí)驗(yàn)測試結(jié)果表明，在聯(lián)合委托學(xué)習(xí)過程中，各客戶端的數(shù)據(jù)加密成本不隨客戶端數(shù)量的增加而增大，并且最終獲得的模型與真實(shí)數(shù)據(jù)構(gòu)建的模型具有一致性，即最終挖掘得到的模型準(zhǔn)確度沒有任何損失，而服務(wù)器很難推測和匹配出真實(shí)的模型結(jié)構(gòu)。