李興鑫, 朱友文,2,3, 王 箭

1. 南京航空航天大學計算機科學與技術(shù)學院, 南京 210016

2. 廣西師范大學廣西多源信息挖掘與安全重點實驗室, 桂林 541004

3. 桂林電子科技大學廣西可信軟件重點實驗室, 桂林 541004

1 引言

樸素貝葉斯分類是一種有效的機器學習算法, 在文本檢測以及醫(yī)療診斷等領(lǐng)域有著重要應用[1]. 樸素貝葉斯分類算法由兩個階段組成: 訓練階段以及預測階段. 訓練階段從標記好的訓練集中訓練出樸素貝葉斯分類器模型. 預測階段利用訓練好的樸素貝葉斯分類器判斷樣本的類標簽. 通常在訓練階段需要大量的數(shù)據(jù)進行模型訓練, 這會產(chǎn)生巨大的計算和存儲負擔, 因此無法在一些資源受限的設(shè)備上進行. 另一方面,一些大型組織和機構(gòu)通過機器學習即服務(machine learning as a service)[2]將其訓練好的機器學習模型提供給個人以及小型公司. 為了支持處理用戶頻繁的任務請求, 這些大型機構(gòu)需要支付高昂的費用部署和維護本地設(shè)備. 隨著云計算的逐漸普及, 將數(shù)據(jù)和訓練分類任務外包給云服務器, 利用云強大的計算能力減輕用戶本地負擔, 是上述問題的一個可行解決方案. 然而外包數(shù)據(jù)中通常包含一些隱私信息, 比如個人健康或生物特征信息, 并且訓練好的模型也被視為所有者的私人財產(chǎn). 因此, 外包樸素貝葉斯模型訓練和分類過程中的數(shù)據(jù)隱私安全問題不容忽視.

同態(tài)加密[3,4]是一種保護外包數(shù)據(jù)隱私和實現(xiàn)安全計算的有效方式. 用戶在本地利用同態(tài)加密算法加密自身數(shù)據(jù), 隨后將加密數(shù)據(jù)外包到云服務器. 同態(tài)加密的語義安全性質(zhì)能夠為外包數(shù)據(jù)隱私提供強有力的保障, 同時同態(tài)性質(zhì)也使得云服務器能夠在加密數(shù)據(jù)上進行訓練和分類所需的相關(guān)運算. 文獻[5–9]借助同態(tài)加密實現(xiàn)了不同的安全外包機器學習算法, 比如: 加密數(shù)據(jù)安全k近鄰分類和安全卷積神經(jīng)網(wǎng)絡. 但是這些方案都只適用于安全實現(xiàn)特定機器學習算法, 無法直接應用于實現(xiàn)安全貝葉斯訓練和分類.

文獻[10,11] 實現(xiàn)了分布式環(huán)境下的安全貝葉斯模型訓練和分類. 這些方案中各個參與方擁有訓練集的部分數(shù)據(jù), 并能從中推測出部分參數(shù)用于貝葉斯模型訓練以及進行樣本分類. 這與本文考慮的外包模型有所不同, 在外包場景下為了保護數(shù)據(jù)隱私, 數(shù)據(jù)集被加密后上傳到云服務器中, 因此云服務器無法從中獲得明文數(shù)據(jù)的任何有效信息. 文獻[7,12–14] 考慮了一方持有貝葉斯模型另一方持有待分類樣本的場景,在不泄漏模型和待分類樣本隱私的情況下安全運用訓練好的模型對樣本進行分類. 文獻[7,15,16] 運用全同態(tài)加密將樸素貝葉斯模型加密后外包到云服務器, 并且基于同態(tài)性質(zhì)提出了安全外包樸素貝葉斯分類方案. 這些方案均假設(shè)貝葉斯模型已經(jīng)訓練完成, 主要考慮的是預測階段中如何在保護模型和待分類樣本隱私的情況下完成安全貝葉斯分類計算, 無法用于實現(xiàn)加密數(shù)據(jù)上的安全貝葉斯模型訓練. 文獻[17] 提出的方案實現(xiàn)了從加密數(shù)據(jù)安全獲取部分貝葉斯模型參數(shù), 這些參數(shù)隨后返回給一個服務器用于生成最終的貝葉斯模型. 該方案需要將訓練好的貝葉斯模型泄漏給一個服務器. 文獻[18] 提出的方案結(jié)合Paillier 同態(tài)加密算法和不合謀云服務器模型實現(xiàn)加密數(shù)據(jù)集上的貝葉斯模型安全訓練和分類運算. 但是這一方案在用戶端和云服務器端的計算和通信開銷太高, 無法處理大規(guī)模外包數(shù)據(jù). 與上述基于密碼學方法的工作不同, 文獻[19,20] 提出了(本地) 差分隱私下的安全樸素貝葉斯訓練和分類方案. 雖然這些工作相比于基于密碼學方法的方案具有更好的運行效率, 但其一方面會泄漏數(shù)據(jù)集或者模型的隱私給參與方, 另一方面也會造成分類準確率的損失.

本文結(jié)合somewhat 同態(tài)加密算法(SHE)、SIMD 技術(shù)和混淆電路提出了加密數(shù)據(jù)上的安全高效樸素貝葉斯訓練和分類方案. 本文提出的方案對貝葉斯模型訓練和分類算法進行轉(zhuǎn)換并且設(shè)計了新的明文編碼方式, 從而避免了計算過程中在密文上進行除法運算以及中間結(jié)果溢出問題. 基于兩個不合謀云服務器模型、SHE 的同態(tài)性質(zhì)和SIMD 技術(shù), 本文提出了一系列交互協(xié)議批量地在加密數(shù)據(jù)上實現(xiàn)了外包樸素貝葉斯訓練和分類階段所需的安全類標簽頻數(shù)計算和待分類樣本頻數(shù)統(tǒng)計, 并且通過結(jié)合混淆電路提出了加密數(shù)據(jù)安全類標簽判斷協(xié)議. 本文在半誠實模型下分析了提出方案的安全性. 提出方案能夠保護外包數(shù)據(jù)集、樸素貝葉斯分類器模型、待分類樣本以及分類結(jié)果的隱私. 通過實驗對提出方案的性能進行了評估, 實驗結(jié)果表明本文方案與目前最新的安全樸素貝葉斯訓練和分類方案[18] 相比具有更好的運行效率.

2 預備知識

2.1 符號描述

論文中的符號標記和描述顯示在表1 中.

表1 符號描述Table 1 Notations

2.2 樸素貝葉斯分類器

假定存在一個包含n個已標記樣本的數(shù)據(jù)集D={q1,q2,··· ,qn}, 所有類標簽的集合為CL ={l1,l2,··· ,lλ}. 每個樣本qi(i ∈[1,n]) 有d個屬性可以看成一個d維向量qi=(qi1,qi2,··· ,qid), 并且對應的類標簽為Ci ∈CL. 給定一個待分類樣本S= (S1,S2,··· ,Sd), 樸素貝葉斯分類器根據(jù)最大后驗概率預測樣本S的類標簽CS ∈CL, 也即

由貝葉斯定理可知

在上述公式中,P(S) 對于不同的后驗概率都是相同的, 因此公式(1)可以轉(zhuǎn)換為

在樸素貝葉斯分類器中假設(shè)樣本的屬性之間是相互獨立的, 因此可得

進一步將類標簽判斷轉(zhuǎn)換為

在公式(4)中, 概率P(CS=lt) 和P(Sj|CS=lt) 通過如下公式從訓練集D中計算獲得.

其中n是D中樣本的個數(shù),mt表示訓練集D中類標簽為lt(t ∈[1,λ]) 的樣本個數(shù),mjt表示D中類標簽為lt并且第j(j ∈[1,d]) 個屬性值等于Sj的樣本個數(shù).

2.3 Somewhat 同態(tài)加密

Somewhat 同態(tài)加密(SHE) 是一種公鑰加密系統(tǒng), 能夠?qū)崿F(xiàn)密文上任意數(shù)量的同態(tài)加法運算和有限次的同態(tài)乘法運算. 本文采用文獻[21] 提出的算法作為SHE 的實現(xiàn)方案. 這一方案的明文空間是一個多項式環(huán)Rp=Zp[x]/Φu(x), 其中p是一個大素數(shù), Φu(x) 是u階的分圓多項式. Somewhat 同態(tài)加密系統(tǒng)包括: 密鑰生成算法(SHE.Gen)、加密算法(SHE.Enc) 以及解密算法(SHE.Dec). SHE.Gen 是一個概率算法, 接收安全參數(shù)u、p以及L作為輸入, 輸出一個公私鑰對(pk,sk). 這里u和p決定明文空間,L決定somewhat 同態(tài)加密能夠支持的同態(tài)乘法的深度. SHE.Enc 是一個概率算法, 接收pk 和明文m作為輸入, 輸出密文Epk(m). SHE.Dec 是一個確定性算法, 輸入為密文Epk(m) 和私鑰sk, 輸出為明文m.SHE 是語義安全的并且具有如下的同態(tài)性質(zhì):

同態(tài)加法: 給定兩個密文Epk(x) 和Epk(y), 存在運算?使得Epk(x+y)=Epk(x)?Epk(y). 給定一個密文Epk(x) 和一個公開的常數(shù)a,Epk(x+a)=Epk(x)?a.

同態(tài)乘法: 給定兩個密文Epk(x) 和Epk(y), 存在運算?使得Epk(xy) =Epk(x)?Epk(y). 給定密文Epk(x) 和公開常數(shù)a,Epk(ax)=Epk(x)?a.

2.4 混淆電路

對于任意函數(shù)f, 混淆電路(garbled circuits) 允許兩個參與方在不泄漏各自持有數(shù)據(jù)x和y的情況下安全計算函數(shù)值f(x,y). 混淆電路的核心思想是一方(記為電路生成方) 先對函數(shù)f所對應的布爾電路和自己的輸入x加密, 并將加密的布爾電路和輸入發(fā)送給另一方(電路計算方). 電路計算方與電路生成方交互獲得自身輸入y的加密值, 隨后結(jié)合收到的x的加密值在加密布爾電路上進行運算. 最終雙方能夠在不獲得對方輸入有效信息的情況下計算得到函數(shù)值f(x,y).

混淆電路已經(jīng)被證實在半誠實模型下是安全的, 并且能夠高效處理非線性運算操作[23]. 本文中主要運用混淆電路進行比較操作, 這需要用到一個比較混淆電路(CMP). CMP 的線路和功能描述如下: 給定兩個σ比特的輸入x,y, CMP 安全比較x和y的大小, 輸出1 如果x

3 問題描述和運算原語

3.1 系統(tǒng)模型

如圖1 所示, 本文提出方案的系統(tǒng)模型由多個數(shù)據(jù)擁有者DO、云服務器CS1和CS2以及用戶Usr組成. 每個數(shù)據(jù)擁有者DOi持有部分數(shù)據(jù)集Di并希望通過云服務器聚合數(shù)據(jù)進行訓練以提供更精確的樸素貝葉斯分類器. 為了保護外包數(shù)據(jù)的隱私, DOi選擇在本地加密自身數(shù)據(jù)集. 為此云服務器CS2生成SHE 同態(tài)加密的公私鑰(pk,sk) 并發(fā)布公鑰pk. DOi利用pk 加密自身數(shù)據(jù)集Di并將加密數(shù)據(jù)集Epk(Di) 上傳到云服務器CS1. 用戶Usr 持有樣本S, 利用公鑰pk 加密樣本并發(fā)送Epk(S) 給云服務器CS1. 在收到加密樣本Epk(S) 后, CS1與CS2從加密數(shù)據(jù)集Epk(D) 中訓練得到樸素貝葉斯分類器模型的參數(shù)并且安全地判斷樣本S的類別. 由于Usr 無法接觸到私鑰sk, 本文通過如下方式將分類結(jié)果返回給Usr. CS1向加密類標簽Epk(CS) 添加隨機數(shù), 并將擾動的結(jié)果發(fā)送給CS2. 隨后CS1將隨機數(shù)返回給Usr, CS2解密收到的加密數(shù)據(jù)并返回給Usr. 在收到兩個云服務器發(fā)送的數(shù)據(jù), Usr 能夠從中恢復得到最終的分類結(jié)果CS.

圖1 安全樸素貝葉斯方案系統(tǒng)模型Figure 1 System model

3.2 安全模型

在本文模型中, 數(shù)據(jù)擁有者DO 是誠實的, 并且用戶Usr 與數(shù)據(jù)擁有者之間也是相互信任的. 本文方案中DO 和Usr 只需要加密自身數(shù)據(jù)并將其上傳至云服務器, 此后并不參與后續(xù)的計算, 所有計算任務都由兩個云服務器CS1和CS2交互完成. 這種方式能夠顯著地減少DO 和Usr 的計算負擔. 在設(shè)計安全外包方案時主要考慮的攻擊者是兩個云服務器CS1和CS2. 本文假設(shè)兩個云服務器CS1和CS2是半誠實的[24]并且是不合謀的. 這種不合謀假設(shè)已經(jīng)被現(xiàn)有的許多工作[5]所采用, 在現(xiàn)實應用中也是比較實用的假設(shè). 可以將兩個云服務器分別部署在不同的云服務器提供商中, 比如: Amazon 和阿里云, 這些大型的IT 公司出于商業(yè)信譽的考慮一般不會相互合謀. 半誠實模型的定義描述如下:

定義1令f(x,y) 是一個計算函數(shù),f1(x,y) 和f2(x,y) 分別表示f(x,y) 第一部分和第二部分. Π 是計算f(x,y) 的一個兩方協(xié)議, View1(x,y) 和View2(x,y) 分別是兩個參與方執(zhí)行協(xié)議Π 過程中的視圖.View1(x,y) = (x,r,M1,M2,··· ,Mt), View2(x,y) = (y,r,M1,M2,··· ,Mt), 其中x和y分別代表兩個參與方的輸入,r表示隨機數(shù),Mi表示在協(xié)議執(zhí)行過程中收到的第i個消息. Π 安全地計算了函數(shù)f, 也即Π 在半誠實模型下是安全的, 如果存在多項式時間內(nèi)的模擬器S1和S2使得

3.3 明文數(shù)據(jù)編碼

3.4 安全運算原語

3.4.1 安全批量乘法協(xié)議

協(xié)議1 安全批量相等判斷協(xié)議(SBEP)Input: CS1 持有密文Epko(?x),Epko(?y), CS2 持有解密密鑰sko Output: CS1 獲得Epko(?z) 滿足zi = 1 如果xi = yi; 否則zi = 0 (i ∈[1,l])1 CS1 選取一個隨機數(shù)向量r = (r1,r2,··· ,rl) ∈Zlpo, 計算Epko(?u) = Epko(?x)?(?Epko(?y))?Pack(r)并將其發(fā)送給云服務器CS2.2 CS2 解密得到u = (u1,u2,··· ,ul) ∈Zl po.3 for i = 1 to l do 4CS2 將ui 分解成比特(u(σ?1)i,u(σ?2)i,··· ,u(0)i ), 其中σ 是模數(shù)po 的比特長度.5CS1 同時將ri 分解成比特(r(σ?1)i,r(σ?2)i,··· ,r(0)i ).6 end 7 for j = 0 to σ ?1 do 8CS2 將向量u(j) = (u(j)1 ,u(j)2 ,··· ,u(j)l ) 打包成?u(j), 加密得到Epko(?u(j)), 將其發(fā)送給CS1.9CS1 計算v(j) = Pack(1)?(?(Epko(?u(j))?Pack(r(j)1 ,r(j)2 ,··· ,r(j)l )?(?2Pack(r(j)1 ,r(j)2 ,··· ,r(j)l )?Epko(?u(j)))),其中1 是長度為l 的全1 向量.10 end 11 CS1 和CS2 調(diào)用SBMP 對σ 個密文v(0),v(1),··· ,v(σ?1) 安全相乘, 得到Epko(?z) = SBMP(v(0),v(1),··· ,v(σ?1)). 這一過程中的SBMP 只需要在一個密鑰對(pko,sko) 上運算.

3.4.3 安全比較協(xié)議

安全比較協(xié)議(SCP) 中CS1擁有E(x),E(y) 其中0≤x,y

y; 否則輸出θ=E(0). 由于0≤x,y

y;否則z0=0. CS1隨后選取一個隨機數(shù)r ∈Zp計算E(v)=E(z)?r并將E(v) 發(fā)送給CS2. 這里v=z+rmodp, 并且z0=β ⊕r0⊕v0其中β是(v

4 安全樸素貝葉斯訓練和分類方案

本文提出的安全樸素貝葉斯方案由以下幾個階段組成.

4.1 初始化

在這一階段中, 云服務器 CS2從數(shù)據(jù)擁有者 DO 處獲得數(shù)據(jù)集D中樣本的總個數(shù)n, 每一個樣本的屬性個數(shù)d以及所有類標簽 CL ={l1,l2,··· ,lλ}, 并確定系統(tǒng)所需的明文空間模數(shù)p1,p2,··· ,ph. 隨后CS2利用SHE 同態(tài)加密的密鑰生成算法Gen 輸入?yún)?shù)u、pi以及L, 生成公私鑰對{pki,ski}1≤i≤h. 同時CS2生成系統(tǒng)的擴展因子γ用于將浮點數(shù)轉(zhuǎn)化為整數(shù). 最后CS2發(fā)送公共系統(tǒng)參數(shù)n,d,CL,u,{pi}1≤i≤h,L給其它參與方. CS2發(fā)送公鑰{pki}1≤i≤h給CS1, 從公鑰集合{pki}1≤i≤h中隨機選取一個公鑰pko(o ∈[1,h]) 發(fā)送給數(shù)據(jù)擁有者DOs 和用戶Usr 用于加密數(shù)據(jù)集和待分類樣本.

4.2 數(shù)據(jù)集加密

這一階段中各個數(shù)據(jù)擁有者DO 利用SHE 同態(tài)加密和SIMD 技術(shù)對各自的數(shù)據(jù)集加密, 并將加密的數(shù)據(jù)集上傳到云服務器CS1中. 這里以數(shù)據(jù)集D被一個數(shù)據(jù)擁有者DO 持有為例說明數(shù)據(jù)集的加密過程. 詳細的數(shù)據(jù)集加密過程顯示在協(xié)議2 中. 在加密過程中DO 首先用擴展因子γ對每個樣本數(shù)據(jù)擴展取整, 并將每一個樣本的類標簽Ci轉(zhuǎn)換成一個0,1 向量ci滿足如果Ci=lt則ci中第t位為1, 其余位都為0. 隨后DO 將數(shù)據(jù)集D劃分成s個數(shù)據(jù)塊, 每個數(shù)據(jù)塊中包含l個樣本. 假設(shè)樣本總數(shù)n是l的倍數(shù). 對于每一個數(shù)據(jù)塊i, DO 將同一屬性j下的l個數(shù)據(jù)記錄打包在一起并用公鑰pko對其加密得到Aij. 同時DO 也加密數(shù)據(jù)塊i中每個樣本對應的類標簽得到Cit. 最終DO 得到加密數(shù)據(jù)集Epko(D)并將其發(fā)送給CS1.

本文方案可以稍微改動以支持數(shù)據(jù)集D水平分布以及垂直分布在多個DO 的情況.

? 如果D水平分布在各個數(shù)據(jù)擁有者, 也即每個數(shù)據(jù)擁有者DOi持有部分數(shù)據(jù)集Di, 其中包含ni個樣本的全部屬性和相應的標簽. 數(shù)據(jù)集Di加密的步驟與協(xié)議2 相同, 只需要將n換成ni.

? 如果D垂直分布在各個數(shù)據(jù)擁有者, 每個數(shù)據(jù)擁有者DOi持有數(shù)據(jù)集D全部樣本的部分屬性di. DOi加密Di時, 需將協(xié)議2 中的d換成自己持有屬性di. 此外只由持有樣本類標簽的數(shù)據(jù)擁有者需要加密每個樣本的類標簽.

協(xié)議2 數(shù)據(jù)集加密Input: 數(shù)據(jù)擁有者持有明文數(shù)據(jù)集D 和公鑰pko Output: CS1 獲得加密數(shù)據(jù)集Epko(D)1 DO 執(zhí)行如下操作:2 for i = 1 to n do qij = ?γqij」.5end 6將Ci 轉(zhuǎn)換成λ 維向量ci. 對于t ∈[1,λ], 如果Ci = lt, cit = 1, ci 其余部分全部為0.7 end 8 for i = 1 to s = n/l do 3for j = 1 to d do 4 9計算k = (i ?1)?l+1.10for j = 1 to d do 11?qij = Pack(qk,j,qk+1,j,··· ,qk+l?1,j), Aij = Epko(?qij).12end 13for t = 1 to λ do 14?cit = Pack(ck,t,ck+1,t,··· ,ck+l?1,t), Cit = Epko(?cit).15end 16 end 17 發(fā)送加密數(shù)據(jù)集Epko(D) = {Aij,Cit}1≤i≤s,1≤j≤d,1≤t≤λ 給云服務器CS1.18 CS1 獲得加密數(shù)據(jù)集Epko(D).

4.3 安全類標簽頻數(shù)計算

4.4 安全待分類樣本頻數(shù)統(tǒng)計

協(xié)議3 安全類標簽頻數(shù)計算Input: CS1 持有加密數(shù)據(jù)集的類標簽{Cit}1≤i≤s,1≤t≤λ, CS2 持有私鑰(ski)1≤i≤h Output: CS1 獲得E( ?md?1)1 for t = 1 to λ do 3 CS1 選擇隨機比特向量bit ∈Zl2, 計算發(fā)送Epko(?uit) = Cit ??bit ?(?2?bit ?Cit) 給CS2.2for i = 1 to s do 4 CS2 用私鑰sko 解密Epko(?uit) 得到uit.5 CS2 計算發(fā)送E(?uit) = {Epk1(?uit),Epk2(?uit),··· ,Epkh(?uit)} 給CS1.CS1 計算C′it = E(?u)??bit ?(?2?bit ?E(?u)).7end 8CS1 計算E(?vt) = C′1t ?C′2t ?···?C′st.9CS1 選擇隨機向量rt ∈Zlp, 計算E(?vt + ?rt) = E(?vt)??rt 并發(fā)送給CS2.10CS2 解密得到vt +rt, 并計算τt = ∑lk=1(vtk +rtk).6 11 end 12 CS2 將τ = (τ1,τ2,··· ,τλ) 打包成?τ, 發(fā)送密文E(?τ) 給CS1.13 CS1 計算E( ?m) = E(?τ)?Pack(?∑l k=1 r1k,··· ,?∑l k=1 rλk).14 CS1 和CS2 執(zhí)行SBMP 獲得E( ?md?1) =SBMP(E( ?m),E( ?m),··· ,E( ?m)).

協(xié)議4 安全待分類樣本頻數(shù)統(tǒng)計Input: CS1 持有加密數(shù)據(jù)集Epko(D) 和加密待分類樣本Epko(?S), CS2 持有私鑰(skw)1≤w≤h Output: CS1 獲得E(?μ) 其中μt = ∏d j=1 mjt (t ∈[1,λ])1 for j = 1 to d do 2for i = 1 to s do CS1 與CS2 運行SBEP 得到Epko(?xij) = SBEP(Aij,Epko(?Sj)).4end 5 end 6 for j = 1 to d do 3 7for t = 1 to λ do 8 for i = 1 to s do CS1 計算Epko(?yijt) = Epko(?xij)?Cit.10CS1 選擇隨機比特向量bijt ∈Zl2, 計算發(fā)送Epko(?zijt) = Epko(?yijt)??bijt ?(?2?bijt ?Epko(?yijt)) 給CS2.11CS2 解密得到?zijt, 發(fā)送E(?zijt) = {Epk1(?zijt),Epk2(?zijt),··· ,Epkh(?zijt)} 給CS1.12CS1 計算E(?yijt) = E(?zijt)??bijt ?(?2?bijt ?E(?zijt)).13end 14CS1 計算E(?ejt) = E(?y1jt)?E(?y2jt)?···?E(?ysjt).15CS1 選擇隨機向量rjt ∈Zlp, 計算E(?ejt + ?rjt) = E(?ejt)??rjt 并發(fā)送給CS2.16CS2 解密得到ejt +rjt, 并計算fjt = ∑lk=1(ejt[k]+rjt[k]).9 17end 18CS2 將fj = (fj1,fj2,··· ,fjλ) 打包成 ?fj, 發(fā)送密文E( ?fj) 給CS1.19CS1 計算E(?gj) = E( ?fj)?Pack(?∑l k=1 rj1[k],··· ,?∑l k=1 rjλ[k]).20 end 21 CS1 和CS2 計算E(?μ) = SBMP(E(?g1),E(?g2),··· ,E(?gd)).

4.5 安全類標簽判斷

協(xié)議5 安全類標簽判斷Input: CS1 持有加密數(shù)據(jù)E(?μ) 和E( ?md?1), CS2 持有私鑰(skw)1≤w≤h Output: Usr 獲得樣本S 的類標簽CS 1 CS1 選取隨機數(shù)向量r,R ∈Zλp, 計算E(?μ)??r 和E( ?md?1)??R 發(fā)送給CS2.2 CS2 用私鑰{skw}1≤w≤h 解密得到μ+r 和md?1 +R.3 for t = 1 to λ do 4CS2 加密得到E(μt +rt) 和E(md?1 t+Rt) 發(fā)送給CS1.5CS1 計算E(μt) = E(μt +rt)?(?rt) 和E(md?1t ) = E(md?1t+Rt)?(?Rt).6 end 7 CS1 設(shè)置E(idx) = E(1), α = E(μ1), β = E(md?11 ). for t = 2 to λ do 8CS1 計算得到α ?E(md?1 t ) 和β ?E(μt), 并和CS2 執(zhí)行SCP 協(xié)議得到θ = SCP(α ?E(md?1 t ),β ?E(μt)).9CS1 計算E(idx) = t ?(θ ?(E(idx)?(?t))),α = E(μt)?(θ ?(α ?E(?μt))),β = E(md?1t )?(θ ?(β ?E(?md?1t ))).10 end 11 CS1 選取隨機數(shù)a ∈Zp, 計算E(idx)?a. CS1 發(fā)送E(idx)?a 給CS2, a 給用戶Usr.12 CS2 解密E(idx)?a 得到idx+a, 發(fā)送idx+a 給Usr.13 Usr 收到CS1 和CS2 的數(shù)據(jù)后計算得到idx, 設(shè)置樣本的類標簽為CS = lidx.

5 方案分析

5.1 安全性分析

在本文提出的方案中, 數(shù)據(jù)擁有者DO 加密數(shù)據(jù)集上傳到云服務器后不再參與后續(xù)安全樸素貝葉斯分類計算, 用戶Usr 僅僅加密待分類樣本發(fā)送給云服務器并從云服務器接收樣本的分類結(jié)果. 兩個不合謀的云服務器CS1和CS2通過運行設(shè)計的交互協(xié)議實現(xiàn)安全樸素貝葉斯訓練和分類計算. 因此本文考慮CS1和CS2是潛在的攻擊者, 并證明提出方案在運行過程中不會泄漏隱私信息給半誠實的CS1和CS2.半誠實模型的安全性定義顯示在定義1中. 本節(jié)首先證明提出的安全原語SBMP、SBEP 和SCP 在半誠實模型下是安全.

定理1安全批量乘法協(xié)議SBMP 在半誠實模型下是安全的, 不會泄漏任何有效信息給CS1和CS2.

定理2提出的安全批量相等判斷協(xié)議SBEP 在半誠實模型下是安全的, 不會泄漏任何有效信息給CS1和CS2.

證明:SBEP 協(xié)議中調(diào)用了SBMP 協(xié)議, 已經(jīng)在定理1 中證明了其安全性, 因此這里分析SBEP協(xié)議中除去SBMP 協(xié)議部分CS1和CS2的視圖. CS1的視圖為View1={pko,Epko(?x),Epko(?y),r,Epko(?u),{Epko(?u(j))}0≤j≤σ?1,{v(j))}0≤j≤σ?1,Epko(?z)}. 可以看出CS1的視圖中包含的是SHE 同態(tài)加密的密文和選取的隨機數(shù). 因此能夠構(gòu)造出一個與View1計算不可區(qū)分的模擬器S1. CS2的視圖為View2={pko,sko,Epko(?u),u,{Epko(?u(j))}0≤j≤σ?1}. View2中除去u都是SHE 同態(tài)加密的密文.u是被隨機向量r擾動的, 與隨機數(shù)是計算不可區(qū)分的. 可以構(gòu)造出一個與View2計算不可區(qū)分的模擬器S2. 綜上所述, SBEP 在半誠實模型下是安全的, 不會泄漏任何有效信息給CS1和CS2.

定理3提出的安全比較協(xié)議SCP 在半誠實模型下是安全的, 不會泄漏任何有效信息給CS1和CS2.

綜上所述, 安全類標簽頻數(shù)計算階段在半誠實CS1和CS2模型下是安全, 不會泄漏數(shù)據(jù)集D和樸素貝葉斯分類器的隱私信息.

定理5安全待分類樣本頻數(shù)統(tǒng)計階段在半誠實CS1和CS2模型下是安全, 不會泄漏數(shù)據(jù)集D、待分類樣本S和樸素貝葉斯分類器的隱私信息.

定理6安全類標簽判斷階段在半誠實CS1和CS2模型下是安全, 不會泄漏數(shù)據(jù)集D、待分類樣本S、樸素貝葉斯分類器以及分類結(jié)果CS的隱私信息.

綜上所述, 安全類標簽判斷階段在半誠實CS1和CS2模型下是安全, 不會泄漏數(shù)據(jù)集D、待分類樣本S、樸素貝葉斯分類器以及分類結(jié)果CS的隱私信息.

5.2 復雜性分析

這一節(jié)分析提出方案的計算和通信復雜度. 主要考慮方案中計算開銷比較大的運算: (1) 加密(Enc);(2) 解密(Dec); (3) 密文同態(tài)乘(Mul); (4) 明密文同態(tài)乘(Pml); (5) 密文同態(tài)加(Add); (6) 混淆電路中非異或門數(shù)目. 與其它運算比如打包、明文密文相加以及相乘相比, 這些運算的計算開銷較大, 決定了提出方案的運行效率. 同樣在統(tǒng)計通信開銷時, 只考慮傳輸?shù)拿芪?Ctx) 個數(shù). 提出方案中每個階段的計算和通信復雜度顯示在表2 中, 詳細的分析過程描述如下.

表2 本文方案計算和通信復雜度Table 2 Computational and communication cost of proposed scheme

數(shù)據(jù)集加密階段中數(shù)據(jù)擁有者DO 將數(shù)據(jù)集分為s=n/l個數(shù)據(jù)塊, 并對每一數(shù)據(jù)塊的每個屬性和和標簽分別加密, 總共需要O(s(d+λ))Enc 運算, 上傳到云服務器CS1的數(shù)據(jù)量為O(s(d+λ)) Ctx.

在安全類標簽頻數(shù)計算階段, CS1和CS2需要O(hsλ) Pml、O(hsλ) Add、O(sλ) Dec 和O(hsλ)Enc 計算{}1≤i≤s,1≤t≤λ,這一過程CS1和CS2的通信為O(hsλ)Ctx. 隨后通過O(hsλ)Add、O(hλ)Dec 和O(h) Enc 計算得到E(?m), 通信量為O(hλ) Ctx. 通過調(diào)用SBMP 協(xié)議計算E(), 這需要O(hd) Pml、O(hd) Add、O(hd) Enc 和O(hd) Dec 并且CS1和CS2通信量為O(hd) Ctx. 因此安全類標簽頻數(shù)計算階段需要O(h(sλ+d)) Enc、O((s+h)λ+hd) Dec、O(h(sλ+d)) Pml、以及O(h(sλ+d))Add 運算. CS1和CS2通信量為O(h(sλ+d)) Ctx.

5.3 對比分析

表3 顯示了本文方案和現(xiàn)有工作的對比分析, 詳細的分析描述如下. 文獻[10,14] 實現(xiàn)了分布式環(huán)境下的安全貝葉斯模型分類, 但這些方案中各個參與方能夠接觸到訓練集的明文數(shù)據(jù), 因此無法應用于外包環(huán)境. 文獻[16] 實現(xiàn)了安全外包樸素貝葉斯分類, 但這一方案不僅需要用戶和云服務器進行多輪的交互,而且運算過程中會泄漏貝葉斯模型的部分信息給用戶. 文獻[15] 在[16] 的基礎(chǔ)上進一步保護了貝葉斯模型的隱私. 然而文獻[15] 和[16] 均假設(shè)貝葉斯模型已經(jīng)預先訓練完成, 沒有實現(xiàn)樸素貝葉斯訓練階段的安全外包. 文獻[17] 提出的方案在外包環(huán)境下實現(xiàn)了加密數(shù)據(jù)上的貝葉斯模型訓練, 但該方案泄漏了訓練完成的貝葉斯模型給云服務器. 文獻[20] 采用本地差分隱私構(gòu)建了隱私保護樸素貝葉斯分類方案, 但這一方案同樣將貝葉斯模型泄漏給了服務器. 現(xiàn)有工作中只有文獻[18] 提出的方案實現(xiàn)了與本文方案相同的功能, 保護貝葉斯模型的同時在加密數(shù)據(jù)上實現(xiàn)訓練和分類過程, 但這一方案的計算和通信開銷較高. 本文結(jié)合SHE、SIMD 和混淆電路提出了安全外包樸素貝葉斯訓練和分類方案, 克服了現(xiàn)有工作的不足, 保護外包數(shù)據(jù)和模型隱私的同時高效實現(xiàn)了樸素貝葉斯訓練和分類過程. 后續(xù)通過實驗將本文方案與實現(xiàn)相同功能的文獻[18] 提出的方案進行性能對比, 驗證了本文方案的高效性.

表3 本文方案與現(xiàn)有工作對比分析Table 3 Comparative analysis between proposed scheme and existing works

6 實驗評估

本節(jié)通過不同的實驗來評估提出方案的性能并將其與現(xiàn)有工作進行對比. 我們主要與文獻[18] 提出的方案進行對比. 據(jù)我們所知, 現(xiàn)有工作中只有這個方案實現(xiàn)了與本文方案相同的設(shè)計目標, 同時實現(xiàn)了加密數(shù)據(jù)上樸素貝葉斯分類器的安全訓練和分類. 實驗中假設(shè)只存在一個DO 擁有外包數(shù)據(jù)集, DO 和Usr 是配置為Intel CoreTMi5-8259U CPU@2.3 GHz 和8 GB 內(nèi)存的筆記本電腦,云服務器CS1和CS2是配置為Intel CoreTMi3-3220 CPU @ 3.3 GHz 和16 GB 內(nèi)存的兩個臺式機. 這些設(shè)備運行Ubuntu 16.04 LTS 系統(tǒng)并且連接在一個局域網(wǎng)中. 實驗采用Python 語言, 使用SEAL-Python 庫1https://github.com/Huelse/SEAL-Python實現(xiàn)SHE, 使用Gabes 庫2https://github.com/nachonavarro/gabes來實現(xiàn)混淆電路. 實驗采用縮放后的數(shù)據(jù)集Shuttle3https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/multiclass/shuttle.scale, 包含57 000 個已標記樣本和7 個類標簽(λ=7), 每個樣本有9 個屬性.

實驗首先測試了不同擴展因子γ對與樸素貝葉斯分類器準確率的影響. 為此設(shè)置數(shù)據(jù)集中70% 的數(shù)據(jù)為訓練集, 30% 的數(shù)據(jù)為訓練集. 運用不同γ對樣本的屬性值放大取整, 隨后構(gòu)建分類器測試分類準確率. 實驗結(jié)果顯示γ ≥105時, 放大取整數(shù)據(jù)集上構(gòu)建的分類器準確率與原始樸素貝葉斯分類器準確率基本一致. 因此, 本文后續(xù)的實驗中設(shè)置γ=105, 用于將樣本屬性值放大取整變?yōu)檎麛?shù).

6.1 方案性能評估

實驗測試了在不同數(shù)據(jù)集樣本數(shù)目n和樣本屬性d下提出方案各個階段所需的運行時間和通信開銷.實驗中n選取為l= 8192 的整數(shù)倍, 從而方便對數(shù)據(jù)集進行打包運算. 數(shù)據(jù)集加密階段、安全類標簽頻數(shù)計算階段和安全待分類樣本頻數(shù)統(tǒng)計階段的實驗結(jié)果顯示在圖2、圖3和圖4.

圖2 數(shù)據(jù)集加密階段所需計算和通信開銷Figure 2 Computational and communication costs of dataset encryption stage

圖3 安全類標簽頻數(shù)計算階段所需計算和通信開銷Figure 3 Computational and communication cost of secure class label count stage

圖4 安全待分類樣本頻數(shù)統(tǒng)計階段所需計算和通信開銷Figure 4 Computational and communication cost of secure smple count stage

數(shù)據(jù)集加密階段在數(shù)據(jù)擁有者DO 端進行運算, DO 將外包數(shù)據(jù)集進行編碼和加密. 從圖2 中可以看出數(shù)據(jù)集加密階段的計算和通信開銷隨著n和d的增加線性增長, 比如: 固定d= 3,n從8192 增加到49 152 時, 數(shù)據(jù)集加密階段的計算時間從0.12 秒變?yōu)?.7 秒, 通信開銷從2.41 MB 增長到14.42 MB;d=9 時, 隨著n的增加, 數(shù)據(jù)集加密階段的計算時間從0.19 秒變?yōu)?.14 秒, 通信開銷從3.84 MB 增長到23.04 MB. 此外, 與其余階段的實驗結(jié)構(gòu)對比可知數(shù)據(jù)集加密階段的計算和通信開銷相對較小. 實驗結(jié)果表明提出方案在DO 端產(chǎn)生較低的計算通信負擔.

安全類標簽頻數(shù)計算發(fā)生在云服務器CS1和CS2之間, 通過打包的方式安全批量計算出加密數(shù)據(jù)集中每個類標簽的數(shù)目以及相應的d ?1 次冪. 從圖3 可以觀察到這一階段的計算和通信開銷同樣與n和d成線性相關(guān). 例如: 當d= 9 時, 隨著n從8192 增加到49 152, 安全類標簽頻數(shù)計算階段的計算時間從5.99 秒變?yōu)?2.98 秒, 通信開銷從123.65 MB 增長到241.15 MB. 此外, 可以從圖3(a) 和圖3(c) 中觀察到, 在不同d下, 這一階段的計算時間和通信量隨著n的增長幅度基本一致; 同樣從圖3(b) 和圖3(d) 可以觀察到, 在不同n下, 這一階段的計算時間和通信量隨著d的增長幅度基本一致. 這主要是由于固定了h和λ, 這一階段的計算和通信復雜度變?yōu)镺(s+d) 其中s=n/l, 因此變化n和d不會改變安全類標簽頻數(shù)計算階段計算時間和通信量的增長幅度.

在安全類標簽判斷階段中, 云服務器CS1與CS2根據(jù)安全類標簽頻數(shù)計算階段和安全待分類樣本頻數(shù)統(tǒng)計階段的輸出E(?md?1) 和E(?μ) 進行計算和比較, 得到待分類樣本類標簽所對應索引idx 的密文并返回給用戶Usr. 這一階段的計算和通信開銷與明文空間模數(shù)的個數(shù)h和外包數(shù)據(jù)集中的類標簽個數(shù)λ有關(guān). 實驗中由于固定了h= 13 和λ= 7, 在不同n和d下這一階段的運行時間固定為28.14 秒, 通信量固定為91.58 MB.

綜上所述, 實驗結(jié)果與5.2 節(jié)的理論分析一致: 提出方案的計算和通信開銷與外包數(shù)據(jù)集大小n和樣本屬性d線性相關(guān). 此外, 能夠從實驗結(jié)果中觀察到本文方案將開銷大的計算任務都外包給了云服務器CS1與CS2, 用戶端的計算和通信開銷較小.

6.2 與現(xiàn)有工作對比

我們還將本文提出方案與文獻[18] 提出的方案進行對比. 文獻[18] 通過Paillier 同態(tài)加密算法設(shè)計了加密數(shù)據(jù)安全貝葉斯模型訓練和分類協(xié)議, 實現(xiàn)了與本文相同的功能. 由文獻[18] 中的理論分析可知其計算和通信開銷同樣隨外包數(shù)據(jù)集大小n和樣本屬性個數(shù)d的增加線性增長. 實驗設(shè)置n= 8192 和d=3, 分別測量數(shù)據(jù)擁有者DO 和云服務器CS1和CS2的計算和通信開銷. 本文方案中數(shù)據(jù)擁有者DO計算和通信開銷主要發(fā)生在數(shù)據(jù)集加密階段, 云服務器的計算和通信開銷發(fā)生在其余三個階段包括: 安全類標簽頻數(shù)計算階段、安全待分類樣本頻數(shù)統(tǒng)計階段和安全類標簽判斷階段. 實驗中采用較小的n和d主要是由于文獻[18] 提出的方案的計算開銷太高, 只能在規(guī)模較小的數(shù)據(jù)集上完成運算. 實驗采用Paillier庫4https://python-paillier.readthedocs.io/en/develop/實現(xiàn)Paillier 同態(tài)加密算法, 設(shè)置Paillier 加密算法的密鑰長度為1024 比特. 實驗結(jié)果顯示在表4 中.

表4 本文提出的安全樸素貝葉斯模型方案與文獻[18] 性能對比Table 4 Performance comparison between proposed scheme and Ref. [18]

從表中可以看出, 文獻[18] 提出的方案中數(shù)據(jù)擁有者DO 需要470.89 秒加密外包數(shù)據(jù)集, 云服務器CS1和CS2需要4298.84 秒完成加密數(shù)據(jù)安全貝葉斯模型訓練和分類, 而本文方案完成相應任務所需的時間分別為0.12 秒和45.57 秒. 相比較于文獻[18], 本文方案在DO 端實現(xiàn)了3924.08 倍的計算效率提升, 在云服務器端實現(xiàn)了94.33 倍的計算效率提升. 考慮到現(xiàn)實場景中, DO 通常是資源受限的用戶并且希望通過外包來減少本地的計算負擔. 本文方案在DO 端的低計算負擔顯然更符合外包計算的需求. 對于通信開銷, 本文方案中DO 和云服務器CS1之間僅需2.41 MB, 云服務器CS1和CS2之間需要372.24 MB. 文獻[18] 中方案相應的通信開銷為7.94 MB 和517.81 MB, 也同樣大于本文方案. 實驗結(jié)果表明,相比于現(xiàn)有工作, 本文提出的加密數(shù)據(jù)安全貝葉斯模型訓練和分類方案有效降低了外包加密數(shù)據(jù)集上進行貝葉斯模型訓練和分類的開銷. 這主要是由于本文通過結(jié)合SHE 和SIMD 打包技術(shù)設(shè)計的交互協(xié)議能夠批量地對外包數(shù)據(jù)進行處理計算, 而文獻[18] 需要對單個數(shù)據(jù)進行加密和計算, 從而產(chǎn)生了較高的計算和通信成本.

7 相關(guān)工作

Vaidya 等人[10]運用安全多方計算中的安全求和協(xié)議和安全lnx運算協(xié)議設(shè)計了水平分布數(shù)據(jù)集下的安全樸素貝葉斯分類方案. 文獻[11] 運用基于秘密分享的協(xié)議設(shè)計了水平分布、垂直分布以及任意分布數(shù)據(jù)集下的安全貝葉斯模型訓練以及分類方案. 這些方案主要考慮的是分布式場景, 參與方可以接觸到部分的明文數(shù)據(jù)集, 無法直接應用于外包環(huán)境中的安全樸素貝葉斯分類.

Bost 等人[12]運用加法同態(tài)加密設(shè)計了一個加密數(shù)據(jù)安全樸素貝葉斯分類方案. 在他們的方案中, 服務器端擁有樸素貝葉斯分類模型, 用戶擁有待分類的樣本. 為了實現(xiàn)安全貝葉斯分類, 服務器運用加法同態(tài)加密將貝葉斯分類器加密發(fā)送給用戶. 用戶在收到加密貝葉斯模型后, 利用加同態(tài)的性質(zhì)計算不同類標簽下待分類樣本概率的密文. 隨后通過安全比較協(xié)議用戶能夠從加密的概率中獲得分類結(jié)果. 許多后續(xù)的工作如文獻[13,14,29,30] 考慮了這一用戶服務器模型下的安全貝葉斯分類問題. 文獻[13] 結(jié)合加法同態(tài)加密、茫然傳輸和提出的雙重擾動技術(shù)設(shè)計了能夠抵抗替代比較攻擊的安全貝葉斯分類方案. Gao 等人[14]設(shè)計了一個MAS 加密框架并將其應用于安全樸素貝葉斯分類, 減少了用戶和服務器之間的交互次數(shù), 提升了文獻[12] 中方案的運行效率. 這些方案[12–14,30]均假設(shè)貝葉斯模型已經(jīng)被訓練完成并且參與方能夠接觸到貝葉斯模型或者待分類樣本.

Khedr 等人[7]利用全同態(tài)加密算法設(shè)計了外包環(huán)境下的安全貝葉斯分類方案. 在提出方案中訓練好的貝葉斯模型參數(shù)被全同態(tài)加密算法加密后上傳到云服務器. 當進行分類時, 用戶在本地先映射樣本的每個屬性使之對應模型中的概率并加密映射后的樣本上傳到服務器中. 云服務器利用全同態(tài)加密的性質(zhì)計算樣本在每個類別下概率的密文返回給用戶. Sun 等人[16]進一步結(jié)合全同態(tài)加密和SIMD 技術(shù)提出了安全外包樸素貝葉斯分類方案, 減少了運算所需的計算和通信開銷. 然而這兩個方案需要云服務器與用戶多次交互進行比較獲得分類結(jié)果, 并且比較過程中會泄漏貝葉斯模型的有效信息給云服務器. 文獻[15] 運用全同態(tài)加密和兩個云服務器模型提出了安全外包樸素貝葉斯分類方案, 在實現(xiàn)分類計算的同時保護了外包貝葉斯模型的隱私. 此外上述方案均假設(shè)貝葉斯分類模型已經(jīng)在本地訓練完成, 僅僅實現(xiàn)了貝葉斯分類階段的外包. Liu 等人[17]利用加同態(tài)加密設(shè)計實現(xiàn)了加密數(shù)據(jù)的安全貝葉斯運算. 然而他們的方案只是部分實現(xiàn)了貝葉斯分類器的構(gòu)建, 僅僅通過聚合協(xié)議實現(xiàn)了從加密數(shù)據(jù)集中統(tǒng)計類標簽的頻數(shù). 待分類樣本的頻數(shù)以及先驗概率仍然需要在明文上進行計算. Zhu 等人[18]結(jié)合Paillier 同態(tài)加密和不合謀的云服務器模型設(shè)計了加密數(shù)據(jù)安全貝葉斯模型訓練和分類方案, 實現(xiàn)了從加密數(shù)據(jù)集中訓練貝葉斯模型參數(shù)并進行分類運算. 但是他們的方案所需的計算和通信開銷太高, 無法應用于大規(guī)模數(shù)據(jù)集中. 與本文研究內(nèi)容相關(guān)的另一些文獻[19,20] 運用差分隱私來實現(xiàn)隱私保護樸素貝葉斯訓練和分類. 文獻[19] 提出的方案中需要一個可信第三方稱為數(shù)據(jù)收集者收集用戶數(shù)據(jù), 向其中添加特定的擾動, 從而在實現(xiàn)差分隱私的同時計算樸素貝葉斯分類. 為了避免使用可信第三方, 文獻[20] 設(shè)計了本地差分隱私下的聯(lián)合分布估計機制并基于此提出了本地差分隱私下的樸素貝葉斯訓練和分類方案. 這一方案雖然保護了數(shù)據(jù)集的隱私, 但是將訓練好的樸素貝葉斯模型泄漏給了第三方.

8 總結(jié)

本文結(jié)合SHE 加密算法、SIMD 技術(shù)和混淆電路提出了加密數(shù)據(jù)安全樸素貝葉斯訓練和分類方案,使得云服務器能夠在外包加密數(shù)據(jù)集上安全批量訓練出樸素貝葉斯模型參數(shù), 并對待分類樣本進行分類運算. 本文提出的方案保護了外包訓練數(shù)據(jù)集、待分類樣本、樸素貝葉斯分類器以及分類結(jié)果的隱私信息,并且能夠高效地在大規(guī)模加密數(shù)據(jù)集上進行運算. 本文在半誠實模型下證明了提出方案的安全性并通過實驗對其性能進行了評估. 實驗結(jié)果表明提出方案相比現(xiàn)有工作具有更好的運行效率.