云計算輔助的高效決策樹隱私保護查詢協議

秦寶東，李媛媛，余沛航

(西安郵電大學 網絡空間安全學院，陜西 西安 710121)

機器學習[1]是一種使用歷史數據訓練出模型，然后通過對模型輸入新的數據來進行預測的方法。在當今的大數據時代，機器學習技術取得了突破性的進展，在無人駕駛汽車、垃圾郵件過濾等領域應用廣泛，在醫療診斷領域也有著良好的發展前景[2]。然而，機器學習本身面臨著許多安全與隱私問題[3-4]。模型訓練需要大量的訓練數據，其預測的準確性與訓練數據的多少以及數據質量相關。訓練數據通常包含諸如個人工作、愛好、身份信息和家庭狀況等涉及到個人隱私的信息，必須利用密碼技術進行保護[5]。如果將這些信息以明文的形式傳輸，一旦被泄露，可能會造成嚴重后果。而且，大量訓練數據的計算全部交給服務器完成，可能會超出服務器的計算能力，從而導致整個系統效率減慢甚至系統崩潰。

在早期的工作中，機器學習隱私保護主要重視模型訓練階段數據的隱私保護，如基于差分隱私[6]、(全)同態加密[7-8]和安全多方計算[9]等密碼技術的安全機器學習模型。除了保護訓練數據的隱私，近年來，越來越多的學者更加關注隱私保護的機器學習分類研究，特別是用戶特征向量、分類模型和預測結果的隱私保護[10-11]。

2015年，Bost等[10]研究了超平面分割(Hyperplane Decision)、樸素貝葉斯(Na?ve Bayes)和決策樹(Decision Trees)等3種分類模型的隱私預測協議，主要使用半同態加密技術實現協議中的加、乘、比較等基本運算。但是，對于決策樹模型，需要將決策樹模型表示成一個高次多項式函數，并使用效率較低的全同態加密技術實現密文數據上的高次多項式運算。2016年1月，Gilad-Bachrach等[11]提出一種基于同態加密的深度學習隱私保護方案用于醫療系統中，對患者病歷中的敏感信息進行保護。醫院將患者的信息加密后發送給服務器，服務器對加密數據進行預測，并將預測結果返回給醫院進行解密使用，該方案在MNIST(Mixed National Institute of Standards and Technology database)數據集上訓練的準確率為98.95%，不但保證了準確性和安全性，同時也實現了較高的吞吐量。同年7月，Wu等[12]利用不經意傳輸協議和加法半同態加密技術替代全同態加密實現Bost等人的決策樹隱私預測協議，從而提高了協議的效率。但是Wu等人的協議需要將決策樹模型發送給用戶，在發送給用戶之前，服務器需要先對決策樹模型進行隨機化并且轉化為完全二叉樹，從而增加了用戶與服務器之間的通信及計算開銷。 2017年，Tai等[13]改進了Wu等人協議的效率，提出一種基于線性函數的決策樹隱私保護查詢協議，用線性函數取代高次多項式函數表示決策樹模型，并利用路徑權重是否為零判斷二叉樹葉子節點是否包含分類結果，從而降低決策樹預測協議的總體運行時間。但是，當決策節點稀疏時，該協議需要用戶與服務器交互兩輪，用戶端的計算效率并沒有提高。

除了解決用戶和模型提供者之間的隱私預測協議，還有一部分工作將用戶特征向量和決策模型同時外包給兩個云服務器來實現隱私預測協議[14-15]。該類協議一般通過秘密拆分和安全計算解決協議中的一些常規運算，而不需要同態加密方案，因此效率一般較高。但是，該類協議需要引入可信密鑰中心預分配一些秘密信息到兩個服務器，從而保護用戶數據和預測模型的隱私性。針對基于線性函數的決策樹隱私保護查詢協議存在的不足之處，擬提出一種云計算輔助的高效決策樹隱私保護查詢協議，以期在一定程度上改善客戶端的計算和通信開銷。該協議包含用戶、決策服務器和云計算輔助服務器等3個實體。以醫療系統為例，協議的用戶是擁有一些疾病特征向量的患者，決策服務器是擁有一個決策樹分類模型的醫院。首先，用戶利用云計算輔助服務器的公鑰將自身的疾病特征向量加密后安全地傳送給醫院。其次，醫院和云計算輔助服務器通過運行比較協議，計算出決策樹中每條路徑的權重和，將該權重和利用云計算輔助服務器的公鑰進行加密，而相應的分類結果用云計算輔助服務器的公鑰和用戶的公鑰進行雙重加密，并將密文發送給云計算輔助服務器。再次，云計算輔助服務器通過判斷每條路徑的權重和是否為零，將正確的分類結果部分解密后返回給用戶。最后，用戶利用自己的私鑰恢復出正確的分類結果。

1 基礎知識

1.1 同態加密

同態加密是一種加密形式，用戶對密文進行特定運算得到的結果仍然是密文，且和對明文進行相同運算后再加密得到的結果具有相同的分布，其分為全同態和半同態兩種形式。半同態加密是指已知兩個密文E(e,m1)和E(e,m2)，用戶可以計算出明文m1+m2的密文E(e,m1+m2)。下面給出同態加密的形式化定義。

定義1一個(加法)同態加密方案包含以下4個概率多項式時間算法并滿足正確性和同態性。

1)系統參數生成算法S(1λ)。輸入安全參數λ，輸出系統參數s=S(1λ)。無特殊說明外，其他算法都將s作為其輸入參數的一部分。

2)密鑰生成算法G(s)。輸入系統參數s，輸出公鑰e和私鑰d，其中公鑰定義了消息空間M和密文空間C。

3)加密算法E(e,m)。輸入公鑰e和消息空間上的一個消息m，輸出密文c=E(e,m)。無特殊說明外，[m]e表示消息m在公鑰e下的密文。當公鑰明確時，可省略其下標，簡記為[m]。

4)解密算法D(d,c)。輸入私鑰d和密文c，輸出明文m=D(d,c)。

正確性對于任意系統參數s，密鑰(e,d)←G(s)和消息m∈M，則有

D[d,E(e,m)]=m

同態性對于任意消息m1,m2∈M及其密文c1和c2，存在一個多項式時間算法H，則H(c1,c2)輸出一個密文c并滿足D(d,c)=m1+m2。

LEE[16](Lifted ElGamal Encryption)同態加密方案在DDH(Decisional Diffie-Hellman)假設下滿足不可區分選擇明文攻擊安全性，即語義安全性，具體構造如下。

1)系統參數生成算法S(1λ)。λ選取一個循環群(,p,g)，其中p和g分別是群的階和生成元，輸s=(,p,g)。

(c1,c2)=(gr,hrgm)

H([m1],[m2])=(grc1,1c1,2,hrc2,1c2,2)

顯然，H([m1],[m2])≡[m1+m2]。

下面介紹雙重LEE加密方案滿足的3個性質。

性質1交換加密順序，其密文是等價的，即兩個密文的解密結果一樣，表示為

[[m]e1]e2=[[m]e2]e1

根據性質1，將消息m的雙重LEE加密簡記為[[m]]。

性質2雙重LEE加密方案滿足同態性，即已知消息m1和m2的雙重加密密文，存在算法H1計算消息m1+m2的雙重加密密文，即

H1([[m1]],[[m2]])≡[[m1+m2]]

性質3已知消息m1在公鑰e1下的LEE密文[m1]e1、消息m2和公鑰e2，存在算法H2計算消息m1+m2的雙重LEE加密密文，即

H2([m1]e1,m2)≡[[m1+m2]]

類似地，已知公鑰e1和e2下的兩個密文[m1]e1和[m2]e2，則存在算法H3計算消息m1+m2的雙重LEE加密密文，即

H3([m1]e1,[m2]e2)≡[[m1+m2]]

1.2 比較協議

2008年，Damg?rd、Geisler和Kr?igaard提出一種安全比較協議[17](簡稱DGK安全比較協議)。該協議假設用戶A和用戶B分別持有t比特的正整數x和y，并且A擁有一對同態加密算法的公私鑰(e,d)，通過運行DGK安全比較協議，B將獲得加密后的比較結果，即[b]=[(x

圖1 DGK安全比較協議運行過程

[x]表示對x按比特加密的結果，即

[x]=([xt-1],…,[x1],[x0])

PvtCmpA(d,c)算法的具體步驟如下。

輸入私鑰d和密文向量c=(ct-1,…,c1,c0)。

輸出bA。

步驟1對于任意0≤i≤t-1，利用私鑰d計算密文ci的解密結果mi←D(d,ci)。

步驟2如果存在解密結果滿足mi=0，則返回bA=1。

步驟3如果所有解密結果都不滿足mi=0，則返回bA=1。

PvtCmpB([x],y)算法的具體步驟如下。

輸出c和bB。

步驟1選擇一個隨機比特bB∈{0,1}。

步驟2令s=1-2bB。

步驟4輸出密文向量c=(ct-1,…,c1,c0)和隨機比特bB。

1.3 決策樹模型

決策樹是一種常見的機器學習模型。一個決策樹模型包含若干中間節點(決策節點)和葉節點(分類結果)。每個決策節點具有一個決策陷門值yi，每個葉節點具有一個分類值vj。因此，一個決策樹可以用所有決策節點的限門值構成的決策向量y=(y1,y2,…,ym)和相應的分類結果向量v=(v1,v2,…,vl)表示，其中m和l分別為決策節點和葉節點的數量。當決策樹是一個滿二叉樹時，決策節點和葉子節點的數量滿足關系l=m+1。決策樹模型的輸入是一組特征值向量，記作x=(x1,x2,…,xn)，其中n是特征值的數量，輸出是某一分類結果vi。決策樹模型示例如圖2所示，該模型示例包含m=4個決策節點和l=m+1=5分類結果。

圖2 決策樹模型示例

圖2中，特征向量包含3個特征值，即輸入特征向量x=(6,8,10)，根據模型，輸出分類結果v5。在明文狀態下，通過比較特征值和決策節點值，很容易判斷出分類結果。但是，這樣會泄露輸入的特征向量信息。通過DGK安全比較協議，決策模型持有者僅能獲取比較結果，如b=(x

2 協議設計

2.1 協議描述

云計算輔助的高效決策樹隱私保護查詢協議包含決策服務器D、用戶U和云輔助服務器C等3個實體。以醫療系統為例，決策服務器(醫院)擁有一套訓練好的疾病預測模型，用戶(患者)具有某種疾病的特征值并期望利用預測模做出疾病診斷，其具體工作模式如圖3所示。

圖3 協議工作模式

假設每個特征向量包含n個特征值，決策樹是一個滿二叉樹，即包含m個決策節點和l=m+1個葉子節點。令(x1,x2,…,xn)∈n和(y1,y2,…,ym)∈m分別表示特征向量和所有決策節點的限門值。每個特征值和決策限門值不超過t比特。用戶和云輔助服務器分別擁一對LEE同態加密方案的公鑰和私鑰，記作(eU,dU)和(eC,dC)。該協議的詳細執行步驟如下。

步驟1用戶利用云輔助服務器的公鑰將特征向量的每個元素按比特加密，并通過安全信道將加密結果[x1]C,[x2]C,…,[xn]C傳送給決策服務器。

步驟2對于每個決策節點元素yi，令xj表示相應的特征值，其中1≤i≤m,1≤j≤n。決策服務器執行算法(ci,bi,0)←PvtCmpB([xj],yi)并將密文c1,c2,…,cm發送給云輔助服務器。

步驟3對于每個密文ci，云輔助服務器首先利用算法PvtCmpA(dC,ci)計算共享比特bi,1，然后利用自己的公鑰加密每個共享比特bi,1，最后將密文[b1,1]C,[b2,1]C,…,[bm,1]C發送給決策服務器。

步驟4當收到密文[b1,1]C,[b2,1]C,…,[bm,1]C后，決策服務器進行以下計算。

(a)對于任意決策節點1≤i≤m，利用bi,0和密文[bi,1]C計算比較結果bi=bi,0⊕bi,1的密文，即[bi]C←[bi,0⊕bi,1]C。令決策節點i的左分支和右分支權重分別為wi,L=[1-bi]C和wi,R=[bi]C。

(b)對于任意葉節點Lk(1≤k≤l)，計算從根節點到該葉節點路徑權重之和Pk。

最后，決策服務器按上述排序結果發送給云輔助服務器。

2.2 正確性分析

2.3 安全性分析

假設用戶、決策服務器和云輔助服務器都是誠實可信但好奇的，通過協議，3個實體能夠獲取以下信息。

1)用戶可以提交任意(加密后的)特征向量給決策服務器，并從云輔助服務器獲取正確的決策結果。

2)決策服務器可以獲取任意特征向量的密文以及比較結果的密文。

3)云輔助服務器可以獲取算法PvtCmpB輸出的密文以及所有從根節點到葉節點路徑權重和的密文和對應分類結果的密文。

此外，任意實體可以監聽其他實體之間通信的內容，即模擬外部攻擊者和單一實體共謀情況。協議的隱私性意味著用戶僅能獲取決策結果，而決策服務器和云輔助服務器不能夠獲取用戶特征向量和分類結果的任何信息，除了特征向量的維數和長度。同時，云輔助服務器不能獲取決策服務器的分類模型信息。

定理1若LEE同態加密方案是語義安全的，DGK安全比較協議是隱私保護的，并且決策服務器與云輔助服務器之間不共謀，則上述決策樹查詢協議是隱私保護的。

證明在協議的步驟1中，用戶的特征向量用云輔助服務器的公鑰加密后通過安全信道將加密結果傳遞給決策服務器。盡管云輔助服務器擁有解密私鑰，但是利用安全信道的語義安全性，云輔助服務器等外部用戶無法獲取用戶和決策服務器之間通信的真實信息，即特征向量的密文[x1]C,[x2]C,…,[xn]C，保證用戶特征向量的語義安全性。決策服務器盡管可以獲取特征向量的密文，但是沒有云輔助服務器的解密密鑰。根據LEE方案的語義安全性，決策服務器無法從特征向量的密文中獲取任何有用信息。因此，用戶與決策服務器之間的通信內容不會泄露用戶特征向量的信息。協議中步驟2、步驟3和步驟4(a)，相當于在云輔助服務器和決策服務器之間執行了一次DGK安全比較協議，根據DGK比較協議的安全性，決策服務器僅能獲取比較結果的密文，即[bi]C根據加密方案的語義安全性，決策服務器從該密文中獲取不到bi的任何有用信息。云輔助服務器僅能獲取比較結果的隨機拆分結果，即共享比特bi,1。

總之，通過上述決策查詢協議，用戶可以正確地獲取分類結果，而不會獲取其他決策模型的其他信息。決策服務器除了獲取用戶特征向量的長度，也不會獲取特征值的其他信息。云輔助服務器除了能夠獲取決策模型的葉子節點數量，也不會獲取決策模型以及用戶特征向量的其他任何信息。

3 性能分析

為了分析所提決策樹隱私查詢協議的性能，將其與基于線性函數的決策樹隱私保護查詢協議[13]進行對比。令n和t分別表示特征向量的維數和每個特征值的比特長度，m表示決策樹中的決策節點個數。將一個實體到另一個實體的單向通信記作半次交互，雙向通信記作1次交互。假設同態加密方案定義在循環群(,p,g)上，用群元素的數量表示通信量。用戶、決策服務器和云輔助服務器端的理論計算復雜度及用戶特征向量和決策模型泄露的信息對比如表1所示，各實體間協議交互次數和通信量對比如表2所示。

表1 兩種協議計算復雜度對比

表2 兩種協議通信量對比

通過表1和表2可知，所提協議利用云輔助服務器可以將文獻[13]協議中用戶端的O(mt)計算量轉移至云輔助服務器，從而將用戶端的計算復雜度從O((n+m)t)降至O(nt)。此外，用戶與決策服務器的交互次數也由2次降至0.5次，同時增加0.5次用戶與云輔助服務器的交互。因此，在所提協議中，用戶參與的協議交互次數僅為1次，比文獻[13]協議減少了50%。在信息泄露方面，兩種協議都不會泄露用戶特征向量的任何信息，而僅會泄露決策模型中決策節點的數量信息，即m。在通信量方面，用戶參與的通信量之和為(2nt+2)個群元素，比文獻[13]協議減少了(2mt+6m+2)個群元素。總而言之，借助云輔助服務器，所提協議不僅能夠降低用戶端的計算和通信復雜度，而且可以減少用戶參與協議的交互次數。

下面利用鳶尾花和乳腺癌兩種數據集訓練的決策樹模型檢測上述兩種協議的實際效率。鳶尾花品種預測模型和乳腺癌預測模型分別如圖4和圖5所示。在鳶尾花品種預測模型中，特征向量維數為n=10，決策樹深度為d=5，決策節點數量為m=7，分類結果有“setosa”“versicolor”和“virginnica”等3種。在乳腺癌預測模型中，特征向量維數為n=15，決策樹深度為d=9，決策節點數量為m=20，分類結果有“benign”和“malignant”兩種。實驗環境為一臺電腦配備Inter(R) Core(TM) i5-4210M (2.6 GHz)處理器，4G運行內存和64位Windows 10操作系統。令p=2q+1是一個1 024比特的素數，其中q是一個強素數。實驗選取的El-Gamal加密方案定義在模p生成的q階循環子群上。兩種協議的實驗結果如表3所示。

圖4 鳶尾花分類模型

圖5 乳腺癌分類模型

表3 兩種協議的實驗結果

由表3可以看出，對于不同的數據集，由于訓練出來的模型參數不同，使得兩種協議的具體時間和通信開銷并不相同，這與表1和表2中的理論分析結果是一致的。對于鳶尾花數據集，由于決策節點數量和特征向量維數較小，所提協議的用戶計算時間與文獻[13]協議區別并不明顯。但是，當決策節點數量和特征向量維數較高時，如乳腺癌數據集，文獻[13]協議的用戶計算時間為11.27 s，而所提僅需要將近一半的時間，即6.61 s。在通信量方面，對于鳶尾花數據集，所提協議用戶與兩個服務器的通信量之和為0.16 MB，而文獻[13]協議需要0.22 MB。對于乳腺癌數據集，所提協議用戶的通信量比文獻[13]協議的用戶通信量減少0.23 MB，約為53%。

4 結語

借助云計算技術，提出一種高效的決策樹隱私保護查詢協議。該協議通過同態加密技術保護用戶特征向量信息不會泄露給決策服務器和云輔助服務器，同時保護決策樹信息不會泄露給用戶和云輔助服務器。性能分析結果表明，通過云輔助服務器，該協議用戶的計算時間和通信量較以往相關工作都有一定程度的改進。但是，決策服務器和云輔助服務器之間的效率仍然較低。下一步，將考慮如何在保證協議安全的前提下提高服務器的效率以及如何將決策樹模型安全、高效地外包給云輔助服務器。