高效的決策樹隱私分類服務(wù)協(xié)議

馬立川，彭佳怡，裴慶祺，朱浩瑾

（1.西安電子科技大學(xué)綜合業(yè)務(wù)網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室，陜西 西安 710071；2.陜西省區(qū)塊鏈與安全計算重點實驗室，陜西 西安 710071；3.上海交通大學(xué)計算機(jī)學(xué)院，上海 200240）

1 引言

隨著信息化和網(wǎng)絡(luò)化進(jìn)程的加快以及嵌入式設(shè)備的普及，物聯(lián)網(wǎng)（IoT,Internet of things）技術(shù)已經(jīng)成為學(xué)術(shù)界和工業(yè)界的研究熱點。作為聯(lián)接網(wǎng)絡(luò)空間和物理世界的“橋梁”，物聯(lián)網(wǎng)已經(jīng)在智能醫(yī)療、智慧城市、無人駕駛等與民生息息相關(guān)的領(lǐng)域扮演了越來越重要的角色[1]。相關(guān)調(diào)研報告指出，2025年全球物聯(lián)網(wǎng)設(shè)備的數(shù)量將會達(dá)到754.4億[2]。

數(shù)以億計的物聯(lián)網(wǎng)終端設(shè)備持續(xù)對其所處的環(huán)境狀態(tài)進(jìn)行捕捉，并源源不斷地產(chǎn)生諸如日志、聲音、視頻等多樣化的海量數(shù)據(jù)。然而，由于物聯(lián)網(wǎng)設(shè)備是計算、通信、存儲等資源受限的小型設(shè)備，其本身難以執(zhí)行復(fù)雜的運(yùn)算。因此，物聯(lián)網(wǎng)終端產(chǎn)生的海量數(shù)據(jù)一般被上傳到云計算中心，利用大數(shù)據(jù)分析技術(shù)對數(shù)據(jù)中蘊(yùn)含的價值進(jìn)行充分挖掘。在此背景下，便產(chǎn)生了“物聯(lián)網(wǎng)大數(shù)據(jù)”的概念[3]。

與此同時，能夠從多樣化數(shù)據(jù)中進(jìn)行模式挖掘與特征提取的機(jī)器學(xué)習(xí)算法已經(jīng)被成功地應(yīng)用于語音視頻分析、自然語言處理、趨勢預(yù)測等領(lǐng)域，其已經(jīng)構(gòu)成了大數(shù)據(jù)分析技術(shù)的重要組成部分。其中，基于規(guī)則空間劃分的決策樹分類算法因其易于實現(xiàn)和高效性，已經(jīng)成為機(jī)器學(xué)習(xí)中應(yīng)用最廣泛的分類算法之一[4]。在物聯(lián)網(wǎng)大數(shù)據(jù)中，往往采用“機(jī)器學(xué)習(xí)即服務(wù)”（MLaaS,machine learning as a service）的方式來對用戶提供分類服務(wù)，即云數(shù)據(jù)中心將來自物聯(lián)網(wǎng)終端設(shè)備的海量數(shù)據(jù)進(jìn)行匯聚并進(jìn)行訓(xùn)練得到最終的決策樹分類模型，然后通過該模型對外提供分類服務(wù)[5-6]。

然而，用戶在以MLaaS 的方式便利地使用決策樹分類服務(wù)的同時，面臨著嚴(yán)重的隱私泄露風(fēng)險。一方面，服務(wù)提供商在提供決策樹分類服務(wù)時，需要保護(hù)其所訓(xùn)練出來的分類模型不被泄露。另一方面，用戶在請求分類服務(wù)時，一般需要向服務(wù)提供商提交其需要進(jìn)行分類預(yù)測的數(shù)據(jù)，而這些數(shù)據(jù)往往包含用戶的行為習(xí)慣、偏好、位置、收入等敏感信息，隨著用戶隱私保護(hù)的意識越來越強(qiáng)，在進(jìn)行分類時需要兼顧用戶的數(shù)據(jù)隱私。此外，各國頒布的隱私保護(hù)法規(guī)（如歐盟的《通用數(shù)據(jù)保護(hù)條例》，美國的《加利福尼亞消費者隱私法案》[7]和我國的《中華人民共和國網(wǎng)絡(luò)安全法》）嚴(yán)格要求服務(wù)提供商在提供服務(wù)時需要對用戶的隱私信息進(jìn)行保護(hù)[7-9]。因此，在物聯(lián)網(wǎng)大數(shù)據(jù)背景下，服務(wù)提供商對用戶提供決策樹的分類服務(wù)時要求保護(hù)預(yù)測模型和用戶的屬性數(shù)據(jù)不被泄露，即服務(wù)提供商需要提供決策樹隱私分類服務(wù)。

目前，為了實現(xiàn)決策樹隱私分類服務(wù)，一般采用可搜索加密[10]、同態(tài)加密[11-12]以及安全多方計算[13]等工具。然而，文獻(xiàn)[10]所提基于可搜索加密的決策樹隱私分類方法泄露了樹形分類模型的整體結(jié)構(gòu)。文獻(xiàn)[11-12]基于同態(tài)加密所設(shè)計的方法雖然能夠同時保護(hù)分類模型結(jié)構(gòu)和用戶數(shù)據(jù)不被泄露，但給服務(wù)提供商和用戶帶來了巨大的計算負(fù)擔(dān)。文獻(xiàn)[13]引入安全多方計算框架，將Yao 混淆電路和不經(jīng)意傳輸（OT,oblivious transfer）協(xié)議相結(jié)合，提升了決策樹隱私分類的效率，但是其中涉及了多個按固定順序依次計算的混淆電路，故在一定程度上限制了該方法的實際應(yīng)用。

為了保證服務(wù)提供商能夠提供決策樹隱私分類服務(wù)，并克服現(xiàn)有工作的缺點，本文提出了一種面向物聯(lián)網(wǎng)大數(shù)據(jù)的決策樹隱私分類服務(wù)方法，進(jìn)一步提升了決策樹隱私服務(wù)分類方法的效率。本文具體的研究工作如下。

1) 提出了面向物聯(lián)網(wǎng)大數(shù)據(jù)的決策樹隱私分類服務(wù)系統(tǒng)模型，基于該模型，給出了威脅模型以及安全定義。

2) 設(shè)計了一種高效的決策樹隱私分類服務(wù)協(xié)議，其包括決策樹分類模型混淆、基于布爾共享的隱私比較和基于不經(jīng)意傳輸?shù)碾[私分類結(jié)果獲取3 個階段。該協(xié)議能夠保護(hù)服務(wù)提供商決策樹分類模型參數(shù)及結(jié)構(gòu)特征和用戶需要進(jìn)行分類的特征數(shù)據(jù)。

3) 通過安全性分析證明了所提決策樹隱私分類服務(wù)能夠抵抗“誠實好奇”的惡意攻擊者。同時，將所提協(xié)議用于通過公開數(shù)據(jù)集得到的決策樹分類模型，以分類準(zhǔn)確率和完成隱私分類服務(wù)的時間效率為指標(biāo)，與現(xiàn)有方法進(jìn)行對比，驗證了本文所提隱私分類服務(wù)協(xié)議的高效性。

2 相關(guān)研究工作

作為機(jī)器學(xué)習(xí)中的一種典型方法，決策樹因其易于實現(xiàn)和分類性能高效被廣泛應(yīng)用于移動通信[14]、智慧醫(yī)療診斷[15]、網(wǎng)絡(luò)安全防護(hù)[16]等各個方面。決策樹分類方法的工作原理如下。通過訓(xùn)練數(shù)據(jù)得到一種樹形的分類模型，其包括內(nèi)部節(jié)點和葉子節(jié)點。每個內(nèi)部節(jié)點具有一個屬性標(biāo)簽和閾值，葉子節(jié)點則代表一個分類。在利用決策樹模型進(jìn)行分類時，需要從根節(jié)點開始，將對應(yīng)節(jié)點屬性標(biāo)簽的屬性值與閾值進(jìn)行比較，根據(jù)比較結(jié)果選擇其相應(yīng)的子節(jié)點，直至到達(dá)葉子節(jié)點，得到最終的分類結(jié)果。上述分類過程可以總結(jié)為：利用數(shù)據(jù)的屬性值找到?jīng)Q策樹中一條從根節(jié)點到葉子節(jié)點的路徑，葉子節(jié)點所對應(yīng)的分類為該條數(shù)據(jù)的最終分類結(jié)果。

隨著用戶隱私保護(hù)意識的增強(qiáng)以及世界各國法規(guī)對隱私信息保護(hù)的要求越來越嚴(yán)苛，在物聯(lián)網(wǎng)大數(shù)據(jù)環(huán)境下使用機(jī)器學(xué)習(xí)模型提供分類服務(wù)時，需要同時保護(hù)分類模型及用戶數(shù)據(jù)不被泄露[17]。近年來，為了在兼顧隱私的同時實現(xiàn)決策樹分類方法，一般引入可搜索加密、同態(tài)加密和安全多方計算等工具。其中，文獻(xiàn)[10]將決策樹中根據(jù)每一個內(nèi)部節(jié)點所定義的閾值對決策樹從根節(jié)點到葉子節(jié)點的路徑進(jìn)行編碼，并將路徑的編碼與葉子節(jié)點所定義的類別建立映射，此時，可以將決策路徑選取問題轉(zhuǎn)化為以路徑編碼為關(guān)鍵詞的搜索問題。然而，該方法泄露了決策樹的整體結(jié)構(gòu)，并且難以處理內(nèi)部節(jié)點所定義的閾值為非整數(shù)的情況。文獻(xiàn)[11]給出了包括決策樹模型在內(nèi)的多種隱私分類方法，其采用了全同態(tài)加密方法，給服務(wù)提供商和用戶帶來了巨大的計算負(fù)擔(dān)。文獻(xiàn)[12]對上述方法進(jìn)行了改進(jìn)，其方案僅需要利用加法同態(tài)加密即可。文獻(xiàn)[11-12]的方法復(fù)雜度均取決于決策樹內(nèi)部節(jié)點的數(shù)量，當(dāng)決策樹規(guī)模變大時，便變得不實用。文獻(xiàn)[13]引入安全多方計算框架，將Yao 混淆電路與不經(jīng)意傳輸協(xié)議相結(jié)合，使決策樹隱私分類服務(wù)的復(fù)雜度只與決策樹的深度相關(guān)。雖然文獻(xiàn)[13]所提方法在這些方法中性能最優(yōu)，但是其每次迭代的需要引入多個混淆電路的計算，故其實用性仍受到限制。

因此，本文綜合考慮了現(xiàn)有決策樹隱私分類服務(wù)協(xié)議的優(yōu)缺點，將決策樹分類模型與安全多方計算框架相結(jié)合，提出了一種更加高效的決策樹隱私分類服務(wù)協(xié)議。

3 系統(tǒng)模型

決策樹隱私分類服務(wù)系統(tǒng)模型如圖1 所示。服務(wù)提供商在向用戶提供決策樹隱私分類服務(wù)時，考慮了云計算中典型的Server-Client 模型。服務(wù)器（用S 表示）位于云計算中心，其主要負(fù)責(zé)收集來自物聯(lián)網(wǎng)設(shè)備的數(shù)據(jù)，并對數(shù)據(jù)進(jìn)行標(biāo)記。本文充分利用云數(shù)據(jù)中心的計算和存儲能力，對所收集的數(shù)據(jù)進(jìn)行訓(xùn)練，得到樹形結(jié)構(gòu)的決策樹分類模型，并利用該模型為用戶提供分類服務(wù)。用戶（用C 表示）可以向S 提供用于分類的數(shù)據(jù)，經(jīng)過計算后由S 返回分類結(jié)果。

圖1 決策樹隱私分類服務(wù)系統(tǒng)模型

決策樹的分類模型用T表示，其為樹形結(jié)構(gòu)，包括根節(jié)點、內(nèi)部節(jié)點和葉子節(jié)點。使用集合表示T中除去葉子節(jié)點的所有節(jié)點集合，。節(jié)點的標(biāo)號從根節(jié)點開始，逐層從左往右依次標(biāo)記，v1表示根節(jié)點。T中葉子節(jié)點的集合為，標(biāo)記的順序仍為從左到右。此時，樹T包含節(jié)點的數(shù)量為m+n。分類模型T為V中的每個節(jié)點vk（k=1,…,m）分配權(quán)重wk、布爾函數(shù)fk(x)=1（x≤wk），以及標(biāo)記函數(shù)I:V→[1,…,d]，此處，I(vk)返回的是內(nèi)部節(jié)點vk所對應(yīng)的屬性序號，記為ik。

假設(shè)用戶的數(shù)據(jù)用x表示，其具有d個屬性，則x∈Rd。在不考慮隱私保護(hù)的前提下通過決策樹分類模型T對x進(jìn)行分類時，首先從根節(jié)點v1開始，計算f1(xi1)并根據(jù)其取值確定接下來需要考慮的子節(jié)點，依次類推，最終到達(dá)葉子節(jié)點，該葉子節(jié)點所對應(yīng)的類別即為x的最終分類結(jié)果。此時，可以將T看作函數(shù)T:Rd→Z(={z1,…,zn})。

與文獻(xiàn)[12-13]中的假設(shè)條件不同，本文中考慮的決策樹分類模型T不一定是一個深度t的完全二叉樹。

考慮到隱私保護(hù)的要求，本文與大多數(shù)隱私保護(hù)相關(guān)工作的惡意模型假設(shè)相同，即服務(wù)提供商和用戶均為“誠實好奇”的，其能夠遵循協(xié)議的規(guī)定正確地完成各自的任務(wù)，但試圖從接收到的數(shù)據(jù)中推斷另一方的原始輸入。嚴(yán)格的“誠實好奇”模型下安全定義如下[18]。

定義1 令π表示一個協(xié)議。如果π能夠在“誠實好奇”攻擊者A 存在的前提下安全計算指定函數(shù)ε，那么存在一個可信的模擬器Sim，其能夠模擬協(xié)議π的運(yùn)行過程，Sim 與A 共同完成協(xié)議π，在此過程中，Sim 以產(chǎn)生隨機(jī)比特串的方式模擬實際情況下另一方的輸入，并且滿足

定義1 表明，如果協(xié)議π在“誠實好奇”攻擊者存在的情況下是安全的，那么該攻擊者在完成協(xié)議的過程中僅僅能獲得輸入和協(xié)議規(guī)定的輸出，無法獲取除此之外的任何信息。

在本文所提決策樹隱私分類服務(wù)協(xié)議中，“誠實好奇”攻擊者具有兩層含義：1) 當(dāng)擁有決策樹分類模型的S 為“誠實好奇”攻擊者時，其基于完成隱私分類服務(wù)協(xié)議過程中所接收到的交互數(shù)據(jù)，試圖推斷用戶進(jìn)行分類的私密數(shù)據(jù)；2) 當(dāng)C為攻擊者時，則會基于交互數(shù)據(jù)去推斷S 所擁有決策樹分類模型的相關(guān)信息。本文第5 節(jié)將綜合考慮上述2 種情況，給出所提出隱私分類協(xié)議的安全性證明。

4 決策樹隱私分類協(xié)議設(shè)計

本節(jié)首先給出了所提決策樹隱私分類協(xié)議的概述和基本工作原理；其次，分別從決策樹模型變換、分類路徑確定及分類結(jié)果獲取3 個方面詳細(xì)地介紹了該協(xié)議每個步驟的實現(xiàn)細(xì)節(jié)。

4.1 協(xié)議概述

本文所提協(xié)議聚焦在決策樹分類環(huán)節(jié)，服務(wù)提供商擁有決策樹分類模型T，用戶擁有屬性數(shù)據(jù)x。在不考慮隱私保護(hù)的情況下，服務(wù)提供商將x輸入模型T，得到一個分類結(jié)果zx并將其返回給用戶。然而，在隱私保護(hù)的前提下，服務(wù)提供商不能將T泄露給用戶，而用戶則不希望將x和zx泄露給服務(wù)提供商。為此，在決策樹隱私分類協(xié)議設(shè)計時，需要同時保護(hù)服務(wù)提供商的分類模型T以及用戶的數(shù)據(jù)x及分類結(jié)果zx。

在使用決策樹分類模型T對x進(jìn)行分類時，需要從T的根節(jié)點v1開始，得到根節(jié)點所對應(yīng)的屬性序號i1，然后w1與1ix進(jìn)行比較，根據(jù)比較結(jié)果選擇v1的左子節(jié)點或右子節(jié)點繼續(xù)同樣的步驟，直至到達(dá)葉子節(jié)點，葉子節(jié)點所對應(yīng)的分類即為x的分類結(jié)果。為了在上述過程中保護(hù)分類模型T、用戶數(shù)據(jù)x和分類結(jié)果zx不被泄露，需要滿足以下條件。

1) 對T所定義的內(nèi)部節(jié)點閾值比較順序地進(jìn)行混淆，使用戶無法通過進(jìn)行比較操作的屬性值順序推斷出T除葉子節(jié)點以外的樹形結(jié)構(gòu)。

2) 對需要進(jìn)行比較操作的閾值及用戶數(shù)據(jù)的屬性值進(jìn)行保護(hù)，使用戶無法推斷出內(nèi)部節(jié)點所對應(yīng)的閾值且服務(wù)提供商無法推斷出用戶數(shù)據(jù)。

3) 對分類結(jié)果zx進(jìn)行保護(hù)，使服務(wù)提供商無法獲取用戶數(shù)據(jù)x所對應(yīng)的分類結(jié)果。

為了滿足上述3 個針對決策樹分類的隱私保護(hù)條件，本文所提樹隱私分類協(xié)議由決策樹分類路徑混淆、基于布爾共享的隱私比較和基于不經(jīng)意傳輸?shù)姆诸惤Y(jié)果獲取三部分構(gòu)成。本文用到的數(shù)學(xué)符號以含義如表1 所示。

表1 數(shù)學(xué)符號及含義

4.2 決策樹分類模型混淆

通過決策樹模型進(jìn)行分類時，可以將從根節(jié)點到葉子節(jié)點的一條路徑稱為分類路徑，每一條分類路徑對應(yīng)一個唯一的分類結(jié)果。文獻(xiàn)[12-13]將決策樹擴(kuò)展為一個深度t的完全二叉樹，每一條分類路徑包含d-1 個根節(jié)點和一個葉子節(jié)點。如果在每個非葉子節(jié)點，用0 表示屬性值小于閾值，1 表示其他情況。那么，可以將T看作函數(shù)。由于在T中包含了m個內(nèi)部節(jié)點，文獻(xiàn)[12]將{0,1}t-1擴(kuò)展到{0,1}m，其中每個比特對應(yīng)一個內(nèi)部節(jié)點的比較結(jié)果，此時分類模型變?yōu)椤?/p>

然而，在獲取長度為m的比特串作為輸入時，首先，記決策樹分類模型內(nèi)部節(jié)點的標(biāo)號序列為IV0={1,…,m}，其中將根節(jié)點的序號標(biāo)為1；然后，按照廣度優(yōu)先搜索的原則逐層從左到右依次對內(nèi)部節(jié)點進(jìn)行標(biāo)號。由標(biāo)號序列I0V 所確定的內(nèi)部節(jié)點序列記為V0，那么將V0中每個內(nèi)部節(jié)點所對應(yīng)的屬性標(biāo)號序列和閾值序列分別記為IX0和W0，其中IX0={I(v0,k):k=1,…,m}，W0={w(v0,k):k=1,…,m}。此時，決策樹分類模型T由IV0、IX0和W0唯一確定，即可以看作函數(shù)T[IV0,IX0,W0]:x∈Rd→{z1,…,zn}。

服務(wù)提供商在提供決策樹分類服務(wù)時，如果直接將IX0發(fā)送給用戶，則會暴露分類模型T的樹形結(jié)構(gòu)。為了保護(hù)IX0，文獻(xiàn)[12]采用了樹變換的方法，然而此方法仍會暴露根節(jié)點所對應(yīng)的數(shù)據(jù)屬性標(biāo)號。本文直接采用隨機(jī)置換的方法，通過I0V 的隨機(jī)置換對IX0進(jìn)行混淆，從而保護(hù)樹形結(jié)構(gòu)信息不被泄露。

定義函數(shù)rδ為I0V 的隨機(jī)置換，即δr:IV0→IVr，由IVr所確定的內(nèi)部節(jié)點序列表示為Vr，那么由Vr中內(nèi)部節(jié)點所確定的屬性標(biāo)號序列IXr={I(vr,k):k=1,…,m}。此時，通過作用在IV0上的隨機(jī)置換函數(shù)δr將T[IV0,IX0,W0]進(jìn)行混淆得到新的決策樹分類模型T[IVr,IXr,Wr]。該過程如算法1 所示。

對于任意的用戶數(shù)據(jù)x∈Rd，利用原始分類模型進(jìn)行分類時，可以將x映射為σx∈{0,1}m，此時，定義函數(shù)φ0:σ∈{0,1}m→{1,…,n}表示決策路徑σ與分類標(biāo)號之間的映射。而利用經(jīng)過混淆后的決策樹分類模型進(jìn)行分類時，x被φr映射為σrx∈{0,1}m，其可以看作σx在函數(shù)δr作用下的一個置換。用戶在請求分類服務(wù)后，φr與IXr可以由服務(wù)提供商發(fā)送給請求用戶。

值得注意的是，通過該方法得到的IXr，攻擊者能夠猜對的概率為1/(m!) ；而文獻(xiàn)[12]中作者通過決策樹變換方法得到IrV，攻擊者能夠猜對的概率為1/2m，并且攻擊者總是能夠獲取根節(jié)點所對應(yīng)的數(shù)據(jù)屬性標(biāo)號。

4.3 基于布爾共享的隱私比較

用戶C 提交隱私分類服務(wù)請求后，服務(wù)提供商S將φr與IXr發(fā)送給用戶C。接下來，用戶C 將根據(jù)IXr所確定的屬性標(biāo)號，選擇對應(yīng)的屬性值與服務(wù)提供商擁有的閾值序列Wr中對應(yīng)的閾值進(jìn)行比較，進(jìn)而確定最終的決策路徑σrx∈{0,1}m，隨后可以通過公開的函數(shù)φr得到數(shù)據(jù)x所對應(yīng)的類別標(biāo)號。

在上述過程中，對于IXr中的任意屬性標(biāo)號τj(j=1,…,m)，需要將xτj與對應(yīng)的wj進(jìn)行比較，如果xτj＜wj，σrx,j=1；否則，σrx,j=0。此時，用戶C 擁有xjτ，服務(wù)提供商S 擁有wj。為了滿足隱私保護(hù)要求，在進(jìn)行比較的時候，不能向?qū)Ψ叫孤秞jτ和wj的具體數(shù)值，并且只有用戶C 能夠獲取最終的比較結(jié)果。為了實現(xiàn)隱私比較，文獻(xiàn)[11]應(yīng)用了全同態(tài)加密[19]的方法得到最終比較結(jié)果；文獻(xiàn)[12]使用基于加法同態(tài)加密的比較方法[20-21]，減少了使用全同態(tài)加密時服務(wù)提供商和用戶的計算負(fù)擔(dān)。然而，無論是基于全同態(tài)加密還是加法同態(tài)加密，其給服務(wù)提供商和用戶帶來的計算負(fù)擔(dān)仍然很大。為進(jìn)一步提升隱私比較的效率，本文采用了基于布爾共享的隱私比較方法，其基本思路將需要比較的屬性值和閾值轉(zhuǎn)化為定長（長度設(shè)為l）的比特串并產(chǎn)生對應(yīng)的布爾共享，按照經(jīng)典的GMW（Goldreich-Micali-Wigderson）協(xié)議[22]確定完成比較操作的布爾電路，確定每個參與方（S 或C）所要進(jìn)行的運(yùn)算。在整個過程中，沒有涉及復(fù)雜的密文運(yùn)算，故可以提升隱私比較的效率。

在實現(xiàn)基于布爾共享的隱私比較時，對于任意j(=1,…,m)，用戶C 將xτj轉(zhuǎn)化為長度為l的二進(jìn)制表示[xτj]，然后隨機(jī)產(chǎn)生長度為l的比特串[xτj]C，并令

接下來，需要確定實現(xiàn)比較操作的布爾電路，如圖2 所示，本文所提方法采用了CMP 布爾電路[23]。可以看到，在實現(xiàn)比較操作時，涉及了2 種運(yùn)算：“異或”運(yùn)算⊕和“與”運(yùn)算?。

圖2 CMP 布爾電路

對于任意的α,β∈{0,1}，假設(shè)α=αS⊕αC，β=βS⊕βC，則有

要求α?β的布爾共享，則需要借助能夠預(yù)先計算得到的三元組＜aC,bC,gC＞和＜aS,bS,gS＞使[24]

此時，按照文獻(xiàn)[24]給出的步驟得到[α?β]S和[α?β]C。

利用上述的布爾電路CMP 以及布爾共享的前提下進(jìn)行異或運(yùn)算和與運(yùn)算，算法2 給出了S和C 基于其所擁有的布爾共享實現(xiàn)隱私比較的過程。

算法2基于布爾共享的隱私比較

將算法2 執(zhí)行m次即可得到σrx∈{0,1}m。值得注意的是，雖然基于布爾共享的隱私比較需要進(jìn)行多次，但是不同的隱私比較操作相互獨立，故可以用并行的方式完成該m對數(shù)的比較，進(jìn)一步提升實現(xiàn)隱私比較的效率。此時，用戶C 便可以根據(jù)公開的φr和σrx得到x所對應(yīng)的葉子節(jié)點標(biāo)號。

4.4 基于不經(jīng)意傳輸?shù)碾[私分類結(jié)果獲取

經(jīng)過基于布爾共享的隱私比較之后，用戶C 獲得了數(shù)據(jù)x所對應(yīng)的葉子節(jié)點標(biāo)號，記為γ。而對于服務(wù)提供商S 而言，葉子節(jié)點集合Z={z1,…,zn}中的每個葉子節(jié)點對應(yīng)一個類別，假設(shè)zj(j=1,…,n)為一個長度為λ的比特串，即zj∈{0,1}λ。在獲取最終的分類結(jié)果時，C 希望在S無法知曉γ的前提下獲取zγ，S 則希望C 只能得到zγ而無法獲取其余葉子節(jié)點所對應(yīng)的類別信息。

此時，C 從S 處獲取隱私分類結(jié)果的過程為典型的1-out-of -n不經(jīng)意傳輸過程，記為，其中S 的輸入為{z1,…,zn}，C 的輸入為γ。該過程與文獻(xiàn)[12]中用戶獲取最終分類結(jié)果的方法保持一致。

算法3基于不經(jīng)意傳輸?shù)碾[私分類結(jié)果獲取

至此，決策樹分類模型混淆、基于布爾共享的隱私比較和基于不經(jīng)意傳輸?shù)碾[私分類結(jié)果獲取便構(gòu)成了本文所提的面向物聯(lián)網(wǎng)大數(shù)據(jù)的決策樹隱私分類協(xié)議。

5 性能分析

本節(jié)首先通過嚴(yán)格的安全性分析證明了所提決策樹隱私分類服務(wù)協(xié)議在抵抗“誠實好奇”攻擊者的安全性。其次，通過設(shè)置實驗，分別對所提協(xié)議的分類準(zhǔn)確率和實現(xiàn)效率進(jìn)行驗證。此處，在驗證分類準(zhǔn)確率時，將本文協(xié)議的分類準(zhǔn)確率與明文下的分類準(zhǔn)確率進(jìn)行對比，對比結(jié)果表明，兩者的分類準(zhǔn)確率保持一致，該結(jié)果進(jìn)一步驗證了所提分類協(xié)議的正確性。在估計實現(xiàn)效率時，以完成一次決策樹分類服務(wù)所需的時間為指標(biāo)，將本文所提方法與文獻(xiàn)[12-13]中的方法進(jìn)行比較，實驗結(jié)果表明，無論是對小型決策樹分類模型還是內(nèi)部節(jié)點和深度比較大的決策樹分類模型，本文所提方法均優(yōu)于其余2 種方法。

5.1 安全性分析

根據(jù)定義1 所給出的安全定義，如果本文所提方案對于“誠實好奇”攻擊者而言是安全的，那么在整個隱私分類服務(wù)實現(xiàn)的過程中，服務(wù)提供商或者用戶僅能獲取其協(xié)議所規(guī)定的數(shù)據(jù)，無法獲取任何與其原始輸入相關(guān)的任意信息。在進(jìn)行安全性分析時，本文考慮了2 種情況，即服務(wù)提供商和用戶分別變?yōu)椤罢\實好奇”攻擊者的情形。

服務(wù)提供商通過訓(xùn)練數(shù)據(jù)得到原始的決策樹分類模型T0=T[IV0,IX0,W0]后，進(jìn)入決策樹分類模型混淆階段，得到Tr=[IVr,IXr,Wr]，此時不存在與用戶的交互，故可以得到

假設(shè)存在一個可信的模擬器SimS，其能夠以隨機(jī)產(chǎn)生的方式模擬用戶的輸入，并與服務(wù)提供商進(jìn)行交互完成隱私分類服務(wù)協(xié)議。此時，用表示在該過程中服務(wù)提供商所能夠獲取的數(shù)據(jù)，與協(xié)議真實的實現(xiàn)過程類似，引入和使

由于在決策樹分類模型混淆階段不存在與用戶的交互，故此時不存在與SimS的交互，因此有

同時，根據(jù)基于布爾共享的隱私比較以及1-out-of-n不經(jīng)意傳輸協(xié)議的安全性，可以得到，因此

基于定義1 給出的安全性定義，本文所提的協(xié)議能夠很好地抵制服務(wù)提供商變?yōu)椤罢\實好奇”惡意攻擊者的情形。類似地，可以證明在用戶變?yōu)椤罢\實好奇”惡意攻擊者，本文所提隱私分類服務(wù)協(xié)議仍然是安全的。綜上所述，本文所提協(xié)議能夠很好地抵制“誠實好奇”的惡意攻擊者。

5.2 分類準(zhǔn)確率驗證及時間效率對比

安全性分析證明，本文所提決策樹隱私分類服務(wù)協(xié)議能夠很好地抵抗“誠實好奇”模型下的惡意攻擊者。本節(jié)通過實驗驗證本文所提隱私分類協(xié)議的分類準(zhǔn)確率和實現(xiàn)效率。

本節(jié)實驗通過C++實現(xiàn)，代碼運(yùn)行于裝有Ubuntu 18.04 的虛擬機(jī)上，該虛擬機(jī)的內(nèi)存和硬盤容量分別為16 GB 和50 GB，處理器個數(shù)為6。在決策樹分類模型混淆算法的實現(xiàn)過程中，由于混淆的本質(zhì)是對原始的內(nèi)部節(jié)點序列進(jìn)行隨機(jī)置換，因此實驗中利用標(biāo)準(zhǔn)的AES-128 對稱加密算法來保證混淆過程的安全性。在實現(xiàn)基于布爾共享的隱私比較時，其安全性主要基于隨機(jī)產(chǎn)生長度為l的比特串以實現(xiàn)數(shù)據(jù)以及決策樹內(nèi)部節(jié)點閾值的布爾共享，為此，具體的實現(xiàn)過程中調(diào)用了開源的Openssl 庫來產(chǎn)生滿足條件的隨機(jī)數(shù)。在實現(xiàn)基于不經(jīng)意傳輸?shù)碾[私分類結(jié)果獲取時，采用了基于文獻(xiàn)[25]所設(shè)計的OTExtension 開源框架[26]來實現(xiàn)高效的1(n)OTλ協(xié)議，該框架中所涉及的大數(shù)運(yùn)算、對稱密碼以哈希運(yùn)算則基于Openssl庫和GMP庫來實現(xiàn)，以確保其安全性。此外，所有的數(shù)據(jù)均用長度為64 的比特串表示，前48 bit 表示整數(shù)位，后16 bit表示小數(shù)位。

為了得到真實的決策樹分類模型，本文采用了與文獻(xiàn)[12-13]相同的數(shù)據(jù)集，包括來自加州大學(xué)歐文分校機(jī)器學(xué)習(xí)標(biāo)準(zhǔn)測試數(shù)據(jù)集UCI 的Nursery、Breast-cancer、Housing、Credit-screening 和Spambase，以及來自PhysioBank 的ECG 數(shù)據(jù)集。利用Python 編程調(diào)用sklearn 庫中的DictVectorizer模塊對數(shù)據(jù)集進(jìn)行特征提取，并使用tree 模塊得到對應(yīng)于不同數(shù)據(jù)集的決策樹分類模型，對協(xié)議的分類正確性和時間效率進(jìn)行驗證。

在驗證所提模型的分類準(zhǔn)確率時，首先針對明文狀態(tài)下訓(xùn)練得到的決策樹分類模型，對測試數(shù)據(jù)進(jìn)行分類，得到其分類準(zhǔn)確率。然后，基于本文所設(shè)計的隱私分類協(xié)議和已經(jīng)得到的決策樹分類模型，使用相同的測試數(shù)據(jù)集，得到利用本文協(xié)議的數(shù)據(jù)分類準(zhǔn)確率。分類準(zhǔn)確率結(jié)果是對不同數(shù)據(jù)集分別進(jìn)行50 次實驗得到分類準(zhǔn)確率的平均值，如表2 所示。通過表2 的結(jié)果可以看出，通過本文協(xié)議得到的分類準(zhǔn)確率與明文狀態(tài)下直接使用分類模型得到的分類準(zhǔn)確率保持一致。這主要是由于本文協(xié)議包括決策樹分類模型、基于布爾共享的隱私比較和基于不經(jīng)意傳輸?shù)碾[私分類結(jié)果獲取3 個階段，每個階段的處理均不影響決策樹分類模型與分類結(jié)果之間的一一對應(yīng)關(guān)系。因此，本文所提決策樹隱私分類服務(wù)協(xié)議的分類準(zhǔn)確率得以驗證。

表2 分類準(zhǔn)確率對比

下面對本文協(xié)議的實現(xiàn)效率進(jìn)行評估。本文以完成隱私分類服務(wù)的時間效率為指標(biāo)，將所提協(xié)議分別與文獻(xiàn)[12-13]方法進(jìn)行對比，驗證本文協(xié)議的高效性。值得注意的是，通過數(shù)據(jù)集Housing 和Spambase訓(xùn)練得到的決策樹分類模型中所包含的內(nèi)部節(jié)點數(shù)量及其深度遠(yuǎn)大于其余4 個數(shù)據(jù)集，即完成一次隱私分類服務(wù)所需的時間要遠(yuǎn)大于其余分類模型。

本文協(xié)議與文獻(xiàn)[12]方法進(jìn)行對比得到的結(jié)果如圖3 所示。由于通過Breast-cancer、Nursery、ECG和Credit-screening訓(xùn)練得到的決策樹分類模型規(guī)模比較小，故2 種方法均能很快地完成一次隱私分類服務(wù)，本文協(xié)議的時間效率優(yōu)于文獻(xiàn)[12]方法。而對于數(shù)據(jù)集Housing 和Spambase 而言，經(jīng)過訓(xùn)練得到的決策樹分類模型規(guī)模比較大，無論是本文協(xié)議還是文獻(xiàn)[12]方法，完成一次隱私分類服務(wù)所需的時間均大量增加，但是本文協(xié)議仍能將運(yùn)行時間控制在0.5 s左右，而文獻(xiàn)[12]方法在決策樹規(guī)模變大時完成隱私分類服務(wù)所需的時間急劇增加，這主要是因為在進(jìn)行隱私保護(hù)下的比較運(yùn)算時，文獻(xiàn)[12]引入了基于同態(tài)加密的比較方案，同態(tài)加密在處理算術(shù)運(yùn)算時效率較高，而進(jìn)行比較運(yùn)算時則需要進(jìn)行復(fù)雜的密文運(yùn)算，使該運(yùn)算的時間開銷較大。當(dāng)決策樹分類模型規(guī)模比較大時，其存在大量的內(nèi)部節(jié)點，使完成隱私分類服務(wù)所需的比較運(yùn)算數(shù)量較大，故文獻(xiàn)[12]方法在分類模型規(guī)模變大時所需的時間大量增加。而本文協(xié)議在進(jìn)行比較運(yùn)算時使用布爾共享的思路，比較運(yùn)算效率較高，因此，即使在決策樹分類模型規(guī)模變大時，本文協(xié)議仍能高效地完成隱私分類服務(wù)。

圖3 本文協(xié)議與文獻(xiàn)[12]方法的時間效率對比

圖4 給出了本文協(xié)議與文獻(xiàn)[13]方法在完成一次隱私分類服務(wù)時的時間效率對比。實驗結(jié)果表明，無論是通過 Breast-cancer、Nursery、ECG 和Credit-screening 訓(xùn)練得到規(guī)模較小的決策樹分類模型，還是通過Housing 和Spambase 得到規(guī)模較大的分類模型，2 種方法均能夠高效地完成隱私分類服務(wù)。雖然文獻(xiàn)[13]方法時間復(fù)雜度只與決策樹分類模型的深度有關(guān)，但是其每次迭代引入了大量的混淆電路生成與解析，而本文協(xié)議只涉及相對比較簡單的比較運(yùn)算和最后的1-out-of -nOT 協(xié)議，故本文協(xié)議的時間效率根據(jù)所選的數(shù)據(jù)集實現(xiàn)隱私分類服務(wù)時全面優(yōu)于文獻(xiàn)[13]方法。

圖4 本文協(xié)議與文獻(xiàn)[13]方法的時間效率對比

綜上所述，本文協(xié)議不僅能夠很好地抵制“誠實好奇”模型下的惡意攻擊者，還能準(zhǔn)確并高效地提供決策樹隱私分類服務(wù)。

6 結(jié)束語

本文面向物聯(lián)網(wǎng)大數(shù)據(jù)場景，兼顧越來越迫切的隱私保護(hù)需求，將決策樹分類模型與安全多方計算框架相結(jié)合，設(shè)計了一種高效的決策樹隱私分類服務(wù)協(xié)議。該協(xié)議包括：決策樹分類模型混淆、基于布爾共享的隱私比較和基于不經(jīng)意傳輸?shù)碾[私分類結(jié)果獲取3 個階段。通過該協(xié)議，能夠同時保護(hù)服務(wù)提供商決策樹分類模型參數(shù)及結(jié)構(gòu)特征和用戶需要進(jìn)行分類的特征數(shù)據(jù)。安全性分析表明，本文所提決策樹隱私分類服務(wù)協(xié)議能夠抵抗“誠實好奇”的惡意攻擊者。同時，將本文協(xié)議應(yīng)用于通過Breast-cancer、Nursery、ECG、Credit-screening、Housing 及Spambase 等6 個公開數(shù)據(jù)集得到的決策樹分類模型，以分類準(zhǔn)確率和完成單次隱私分類服務(wù)的平均時間為指標(biāo)，驗證了該決策樹隱私分類服務(wù)協(xié)議的準(zhǔn)確性和高效性。本文的研究能夠在不同的決策樹分類場景中，兼顧隱私保護(hù)需求的前提下，進(jìn)一步提高物聯(lián)網(wǎng)大數(shù)據(jù)場景中的決策樹隱私分類服務(wù)效率。