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

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

2. 廣西師范大學(xué)廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室, 桂林 541004

3. 桂林電子科技大學(xué)廣西可信軟件重點(diǎn)實(shí)驗(yàn)室, 桂林 541004

1 引言

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

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

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

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

2 預(yù)備知識(shí)

2.1 符號(hào)描述

論文中的符號(hào)標(biāo)記和描述顯示在表1 中.

表1 符號(hào)描述Table 1 Notations

2.2 樸素貝葉斯分類器

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

由貝葉斯定理可知

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

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

進(jìn)一步將類標(biāo)簽判斷轉(zhuǎn)換為

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

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

2.3 Somewhat 同態(tài)加密

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

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

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

2.4 混淆電路

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

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

3 問題描述和運(yùn)算原語

3.1 系統(tǒng)模型

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

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

3.2 安全模型

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

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

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

3.4 安全運(yùn)算原語

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 選取一個(gè)隨機(jī)數(shù)向量r = (r1,r2,··· ,rl) ∈Zlpo, 計(jì)算Epko(?u) = Epko(?x)?(?Epko(?y))?Pack(r)并將其發(fā)送給云服務(wù)器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 的比特長(zhǎng)度.5CS1 同時(shí)將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 計(jì)算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 是長(zhǎng)度為l 的全1 向量.10 end 11 CS1 和CS2 調(diào)用SBMP 對(duì)σ 個(gè)密文v(0),v(1),··· ,v(σ?1) 安全相乘, 得到Epko(?z) = SBMP(v(0),v(1),··· ,v(σ?1)). 這一過程中的SBMP 只需要在一個(gè)密鑰對(duì)(pko,sko) 上運(yùn)算.

3.4.3 安全比較協(xié)議

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

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

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

4 安全樸素貝葉斯訓(xùn)練和分類方案

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

4.1 初始化

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

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

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

本文方案可以稍微改動(dòng)以支持?jǐn)?shù)據(jù)集D水平分布以及垂直分布在多個(gè)DO 的情況.

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

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

協(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. 對(duì)于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計(jì)算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≤λ 給云服務(wù)器CS1.18 CS1 獲得加密數(shù)據(jù)集Epko(D).

4.3 安全類標(biāo)簽頻數(shù)計(jì)算

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

協(xié)議3 安全類標(biāo)簽頻數(shù)計(jì)算Input: CS1 持有加密數(shù)據(jù)集的類標(biāo)簽{Cit}1≤i≤s,1≤t≤λ, CS2 持有私鑰(ski)1≤i≤h Output: CS1 獲得E( ?md?1)1 for t = 1 to λ do 3 CS1 選擇隨機(jī)比特向量bit ∈Zl2, 計(jì)算發(fā)送Epko(?uit) = Cit ??bit ?(?2?bit ?Cit) 給CS2.2for i = 1 to s do 4 CS2 用私鑰sko 解密Epko(?uit) 得到uit.5 CS2 計(jì)算發(fā)送E(?uit) = {Epk1(?uit),Epk2(?uit),··· ,Epkh(?uit)} 給CS1.CS1 計(jì)算C′it = E(?u)??bit ?(?2?bit ?E(?u)).7end 8CS1 計(jì)算E(?vt) = C′1t ?C′2t ?···?C′st.9CS1 選擇隨機(jī)向量rt ∈Zlp, 計(jì)算E(?vt + ?rt) = E(?vt)??rt 并發(fā)送給CS2.10CS2 解密得到vt +rt, 并計(jì)算τt = ∑lk=1(vtk +rtk).6 11 end 12 CS2 將τ = (τ1,τ2,··· ,τλ) 打包成?τ, 發(fā)送密文E(?τ) 給CS1.13 CS1 計(jì)算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)計(jì)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 運(yùn)行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 計(jì)算Epko(?yijt) = Epko(?xij)?Cit.10CS1 選擇隨機(jī)比特向量bijt ∈Zl2, 計(jì)算發(fā)送Epko(?zijt) = Epko(?yijt)??bijt ?(?2?bijt ?Epko(?yijt)) 給CS2.11CS2 解密得到?zijt, 發(fā)送E(?zijt) = {Epk1(?zijt),Epk2(?zijt),··· ,Epkh(?zijt)} 給CS1.12CS1 計(jì)算E(?yijt) = E(?zijt)??bijt ?(?2?bijt ?E(?zijt)).13end 14CS1 計(jì)算E(?ejt) = E(?y1jt)?E(?y2jt)?···?E(?ysjt).15CS1 選擇隨機(jī)向量rjt ∈Zlp, 計(jì)算E(?ejt + ?rjt) = E(?ejt)??rjt 并發(fā)送給CS2.16CS2 解密得到ejt +rjt, 并計(jì)算fjt = ∑lk=1(ejt[k]+rjt[k]).9 17end 18CS2 將fj = (fj1,fj2,··· ,fjλ) 打包成 ?fj, 發(fā)送密文E( ?fj) 給CS1.19CS1 計(jì)算E(?gj) = E( ?fj)?Pack(?∑l k=1 rj1[k],··· ,?∑l k=1 rjλ[k]).20 end 21 CS1 和CS2 計(jì)算E(?μ) = SBMP(E(?g1),E(?g2),··· ,E(?gd)).

4.5 安全類標(biāo)簽判斷

協(xié)議5 安全類標(biāo)簽判斷Input: CS1 持有加密數(shù)據(jù)E(?μ) 和E( ?md?1), CS2 持有私鑰(skw)1≤w≤h Output: Usr 獲得樣本S 的類標(biāo)簽CS 1 CS1 選取隨機(jī)數(shù)向量r,R ∈Zλp, 計(jì)算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 計(jì)算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 計(jì)算得到α ?E(md?1 t ) 和β ?E(μt), 并和CS2 執(zhí)行SCP 協(xié)議得到θ = SCP(α ?E(md?1 t ),β ?E(μt)).9CS1 計(jì)算E(idx) = t ?(θ ?(E(idx)?(?t))),α = E(μt)?(θ ?(α ?E(?μt))),β = E(md?1t )?(θ ?(β ?E(?md?1t ))).10 end 11 CS1 選取隨機(jī)數(shù)a ∈Zp, 計(jì)算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ù)后計(jì)算得到idx, 設(shè)置樣本的類標(biāo)簽為CS = lidx.

5 方案分析

5.1 安全性分析

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

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

定理2提出的安全批量相等判斷協(xié)議SBEP 在半誠(chéng)實(shí)模型下是安全的, 不會(huì)泄漏任何有效信息給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)加密的密文和選取的隨機(jī)數(shù). 因此能夠構(gòu)造出一個(gè)與View1計(jì)算不可區(qū)分的模擬器S1. CS2的視圖為View2={pko,sko,Epko(?u),u,{Epko(?u(j))}0≤j≤σ?1}. View2中除去u都是SHE 同態(tài)加密的密文.u是被隨機(jī)向量r擾動(dòng)的, 與隨機(jī)數(shù)是計(jì)算不可區(qū)分的. 可以構(gòu)造出一個(gè)與View2計(jì)算不可區(qū)分的模擬器S2. 綜上所述, SBEP 在半誠(chéng)實(shí)模型下是安全的, 不會(huì)泄漏任何有效信息給CS1和CS2.

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

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

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

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

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

5.2 復(fù)雜性分析

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

表2 本文方案計(jì)算和通信復(fù)雜度Table 2 Computational and communication cost of proposed scheme

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

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

5.3 對(duì)比分析

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

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

6 實(shí)驗(yàn)評(píng)估

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

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

6.1 方案性能評(píng)估

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

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

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

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

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

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

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

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

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

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

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

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

7 相關(guān)工作

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

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

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

8 總結(jié)

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