基于同態(tài)加密的多分類Logistic回歸模型*

許心煒,蔡 斌,向 宏,桑 軍

1.信息物理社會(huì)可信服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室(重慶大學(xué)),重慶400044

2.重慶大學(xué)大數(shù)據(jù)與軟件學(xué)院,重慶400044

1 引言

機(jī)器學(xué)習(xí)是人工智能的核心技術(shù),研究計(jì)算機(jī)如何模擬或?qū)崿F(xiàn)人類的學(xué)習(xí)行為,以獲取新的知識(shí)或技能.機(jī)器學(xué)習(xí)可以自動(dòng)地產(chǎn)生模型,分析更大的數(shù)據(jù),解決更復(fù)雜的問題.隨著計(jì)算能力的發(fā)展,機(jī)器學(xué)習(xí)應(yīng)用范圍也在不斷擴(kuò)大.然而,如何保護(hù)數(shù)據(jù)的隱私已經(jīng)成為一個(gè)重要問題,尤其對(duì)于醫(yī)療、基因、財(cái)務(wù)等特別注重個(gè)人隱私的數(shù)據(jù).

傳統(tǒng)加密系統(tǒng)依賴于交換加密信息的雙方之間共享密鑰.但是,這種方法存在隱私問題.用戶會(huì)失去對(duì)敏感數(shù)據(jù)隱私的控制,尤其在現(xiàn)今流行的云服務(wù)中.Nikolaenko等[1]基于 Yao的Garbled Circuit[2]提出了一種隱私保護(hù)線性回歸協(xié)議.Mohassel等[3]將安全多方計(jì)算應(yīng)用于隱私保護(hù)機(jī)器學(xué)習(xí)中.但是這些方法需要所有的參與方都遵照協(xié)議才能保證方案的安全性和正確性.因此,這些方法雖然實(shí)現(xiàn)了安全多方計(jì)算,但是并不是完全安全的外包計(jì)算方案.

同態(tài)加密是一種特殊的加密方案,它允許第三方對(duì)加密數(shù)據(jù)進(jìn)行操作,而不需要事先對(duì)其進(jìn)行解密,并且得到的運(yùn)算結(jié)果解密后與在明文上運(yùn)算結(jié)果一致.因此同態(tài)加密是有效保護(hù)用戶隱私的一項(xiàng)技術(shù).Graepel等[4]討論了使用同態(tài)加密進(jìn)行機(jī)器學(xué)習(xí)的適當(dāng)和不適當(dāng)?shù)膱?chǎng)景,提供了線性均值分類器和線性判別分析兩個(gè)例子,這兩個(gè)例子均可以在同態(tài)加密中使用低次多項(xiàng)式來實(shí)現(xiàn).然而,這些簡(jiǎn)單的參數(shù)模型不能很好地處理復(fù)雜的數(shù)據(jù)集,同時(shí)也不是生物醫(yī)學(xué)研究中使用的主流機(jī)器學(xué)習(xí)技術(shù)[5].Xie等[6]使用加法同態(tài)加密方案來匯總一些中間統(tǒng)計(jì)數(shù)據(jù),然而計(jì)算中間信息需要昂貴的計(jì)算成本.Crawford等[7]在訓(xùn)練小型Logistic回歸模型方面取得了良好的表現(xiàn),但是他們的解決方案只允許計(jì)算特征非常少的數(shù)據(jù).

與本文最相似的是Kim等[8]和 Chen等[9]的工作.2017年iDASH安全基因組分析競(jìng)賽中,Kim等[8]提出了一個(gè)基于有效近似算術(shù)同態(tài)加密的安全Logistic回歸模型.Chen等[9]在完全同態(tài)加密中應(yīng)用了多位明文空間以及定點(diǎn)數(shù)編碼,提出了基于SEAL庫(kù)的加密Logistic回歸模型.

但是,這兩種解決方案只能分析二分類問題,而現(xiàn)實(shí)生活中存在許多多分類問題.本文基于 Kim等的研究以及Sánchez-Maro?o等[10]的針對(duì)多分類情況的OVR方法,提出了一種基于同態(tài)加密的多分類Logistic回歸模型.該模型可以在解決多分類問題的同時(shí)保證數(shù)據(jù)的隱私安全.該模型具有良好的性能,輸出的結(jié)果可以與未加密運(yùn)算輸出的結(jié)果一致,不影響模型的準(zhǔn)確率.

2 相關(guān)技術(shù)

2.1 HEAAN方案

同態(tài)加密是一種加密技術(shù),允許我們?cè)诓唤饷艿那闆r下對(duì)加密數(shù)據(jù)進(jìn)行操作,并得到與明文計(jì)算相匹配的計(jì)算的結(jié)果.該技術(shù)在實(shí)際應(yīng)用中具有很大潛力,因?yàn)樗试S我們?cè)诠矃s不信任的服務(wù)器上安全地進(jìn)行外包計(jì)算.

Cheon等提出了一種方法,構(gòu)造近似數(shù)算術(shù)同態(tài)加密方案,簡(jiǎn)稱為HEAAN方案.HEAAN方案支持加密消息的近似算術(shù),使得參數(shù)的大小不會(huì)增加過多,減小了一定的精度而大幅提高效率.HEAAN方案支持密鑰生成、加密、解密、加法和乘法等操作.同時(shí),該方案支持消息打包,這有利于實(shí)現(xiàn)并行化.

HEAAN方案的主要思想是將加密噪聲視為近似計(jì)算過程中出現(xiàn)誤差的一部分.即,給定私鑰 sk和密文模數(shù)q,對(duì)于小的誤差e,一個(gè)明文m的密文c滿足=m+e(modq).

HEAAN方案是以LWE(Learning With Errors)問題為理論基礎(chǔ).對(duì)于2的整數(shù)冪N,模數(shù)為N的分圓多項(xiàng)式定義為R=Z[X]/(XN+1).對(duì)于一個(gè)正整數(shù)q,R模q的剩余環(huán)定義為Rq=R/qR.下面是對(duì)HEAAN方案操作的簡(jiǎn)要描述:

?參數(shù)設(shè)置(λ):輸入安全參數(shù)λ,輸出多項(xiàng)式維度N,最大密文模數(shù)q和離散高斯分布χ.

? 密鑰生成 (N,q,χ):輸入?yún)?shù)N,q,χ,取樣s←R,a←Rq,e←χ,輸出私鑰 sk←(1,s)和公鑰pk←(b,a)∈Rq×Rq,其中b←?as+e(modq).設(shè)Q=q2,取樣s′←s2,a′←RQ,e′←χ,輸出計(jì)算密鑰 evk←(b′,a′)∈RQ×RQ,其中b′←?a′s+e′+qs′(modQ).

? 加密 (m,pk):輸入明文m∈R,取樣v←χ,e0←χ,e1←χ,輸出密文m←v·pk+(m+e0,e1)(modq).

? 解密 (c,sk):輸入密文c=(c0,c1),輸出m←c0+c1·s(modq′).

? 加法 (c,c′): 輸入密文c,c′,輸出cadd←c+c′(modq′).

? 乘法 (c,c′,evk): 輸入密文c= (a0,b0),c′= (a1,b1),設(shè) (d0,d1,d2)= (b0b1,a0b1+a1b0,a0b1)(modq′),輸出cmult←(d0,d1)+?1/q·d2·evk?(modq′).

? 重縮放 (c,p):輸入密文c和一個(gè) 2的整數(shù)冪p,輸出c′←?1/p·c?(mod(q′/p)).

?旋轉(zhuǎn)(c,rk,r):輸入密文c和旋轉(zhuǎn)密鑰rk,輸出c的明文向量旋轉(zhuǎn)r個(gè)位置后的密文c′.

有關(guān)HEAAN方案的技術(shù)細(xì)節(jié)和噪音分析可以參考文獻(xiàn)[11].有關(guān)HEAAN方案的bootstrapping方法可以參考文獻(xiàn)[12].

2.2 Logistic回歸和梯度下降

Logistic回歸是機(jī)器學(xué)習(xí)中常用的一種方法,用于建立一個(gè)可區(qū)分 2個(gè)或更多類別樣本的模型.Logistic回歸的一種常見形式是表示為類別0的后驗(yàn)概率:

其中,Y表示類別,x∈Rf表示特征,ω∈Rf表示在模型訓(xùn)練中需要學(xué)習(xí)的權(quán)重向量,σ(t)=1/(1+e?t)是sigmoid函數(shù),將xωT轉(zhuǎn)為后驗(yàn)概率.

機(jī)器學(xué)習(xí)中,損失函數(shù)是用來了衡量模型的預(yù)測(cè)值和真實(shí)值的一致程度,損失函數(shù)越小,模型越優(yōu).對(duì)于Logistic回歸,使用極大似然估計(jì)法,可以得到損失函數(shù):

其中,n表示樣本數(shù)量.

訓(xùn)練Logistic回歸的常用方法是梯度下降法.梯度下降的計(jì)算過程是沿著梯度下降的方向求解損失函數(shù)的最小值.梯度在每次迭代中下降,第t次迭代中權(quán)重向量ω更新為:

其中,α表示學(xué)習(xí)率.

動(dòng)量法改進(jìn)了梯度下降法.動(dòng)量法使得每一次的參數(shù)更新方向不僅僅取決于當(dāng)前位置的梯度,還受到上一次參數(shù)更新方向的影響.而Nestervo梯度下降法[13]相比動(dòng)量法,添加了誤差微分量,使其具有更快的收斂速度.設(shè)初始量v0=ω0,Nestervo梯度下降法更新方程如下:

其中,0<γ<1表示衰減率.

2.3 Sigmoid函數(shù)的近似多項(xiàng)式函數(shù)

雖然梯度下降法比其他的訓(xùn)練方法更適合同態(tài)計(jì)算,但現(xiàn)有的同態(tài)加密只能支持多項(xiàng)式算術(shù)運(yùn)算,所以計(jì)算sigmoid函數(shù)成為了一個(gè)計(jì)算的阻礙.

Chen等[9]使用了極小極大方法[14]得到了sigmoid函數(shù)在區(qū)間[?5,5]上的3次多項(xiàng)式近似函數(shù):

Kim等[15]使用了最小二乘法找到了sigmoid函數(shù)在區(qū)間[?8,8]上的3,5,7次多項(xiàng)式近似函數(shù).

區(qū)間范圍內(nèi),低階多項(xiàng)式只需要較小的計(jì)算深度,具有較高的效率,而高階多項(xiàng)式則具有較高的精度.本文采用了Kim等的近似方法,并在效率和精度中做了權(quán)衡,使用5次多項(xiàng)式進(jìn)行同態(tài)計(jì)算.

3 同態(tài)加密多分類Logistic回歸模型

3.1 多分類 Logistic回歸

Logistic回歸也可以完成多分類學(xué)習(xí)任務(wù).本文基于拆解方法中的“一對(duì)其余”(One vs Rest,OvR)策略,擴(kuò)展二分類Logistic回歸模型來解決多分類問題.

給定數(shù)據(jù)集D={(x1,y1),(x2,y2),···,(xn,yn)},yi∈C1,C2,···,Ck.OvR 策略每次將一個(gè)類的樣例作為正例,剩余其他類型的樣例作為反例訓(xùn)練出k個(gè)分類器,得到{P1,P2,···,Pk}.比較各個(gè)分類器的預(yù)測(cè)置信度,選擇最大置信度對(duì)應(yīng)的標(biāo)記類別作為預(yù)測(cè)的分類結(jié)果.OvR策略的詳細(xì)過程如圖1.

圖1 OvR策略示意圖Figure 1 Diagram of OvR strategy

OvR策略只需要訓(xùn)練k個(gè)分類器,相對(duì)其它拆解方法,存儲(chǔ)和測(cè)試時(shí)間開銷通常較小.使用OvR策略得到的多分類Logistic回歸的詳細(xì)過程如算法1.

算法1多分類Logistic回歸算法Input:X ∈RN×F,y∈RN,α>0 Output:ω ∈ RK×F 1初始化權(quán)重矩陣ω;for iter=0 to T do 2 for k=0 to K do 3 for i=0 to N do 4 Pi←;5 Si← σ(Pi);6 end 7 for j=0 to F do 8 gj←Σi(Si?yi)Xij;9 ωkj← ωkj?αgj;10 end 11 end 12end 13return ω

3.2 多分類 Logistic回歸的同態(tài)計(jì)算

本節(jié)將描述如何基于HEAAN方案,對(duì)加密數(shù)據(jù)進(jìn)行安全的多分類Logistic回歸運(yùn)算.

在同態(tài)加密的外包計(jì)算模型中,客戶端加密數(shù)據(jù),服務(wù)器對(duì)加密后的數(shù)據(jù)進(jìn)行同態(tài)計(jì)算,并返回計(jì)算結(jié)果給客戶端,最終由客戶端對(duì)結(jié)果進(jìn)行解密.

在本文的模型中,首先,客戶端將大小為n×(f+1)的數(shù)據(jù)集X和初始化后的權(quán)重矩陣ω加密后并發(fā)送給服務(wù)器.根據(jù)公式(3),要先進(jìn)行內(nèi)積計(jì)算.

HEAAN方案中沒有直接的內(nèi)積計(jì)算方法,需要通過乘法、加法、旋轉(zhuǎn)運(yùn)算構(gòu)造內(nèi)積計(jì)算.對(duì)每個(gè)類別的權(quán)重向量,首先對(duì)其進(jìn)行N次復(fù)制填充槽,然后與數(shù)據(jù)集的密文做對(duì)位乘法運(yùn)算.接著通過旋轉(zhuǎn)相加得到內(nèi)積.但此時(shí)內(nèi)積中含有無價(jià)值的數(shù)據(jù),將其與常量矩陣相乘,可得到完整的內(nèi)積.常量矩陣是第一列向量為1,剩余列向量為0的矩陣.詳細(xì)的內(nèi)積計(jì)算方法如算法2.

算法2內(nèi)積計(jì)算Input:數(shù)據(jù)集矩陣X 加密后的密文CX,權(quán)重向量ωk加密后的密文Cωk,常量矩陣M 加密后的密文CM Output:內(nèi)積矩陣密文CI 1將Cωk復(fù)制N 次填充槽,得到矩陣密文Cω;2C1←Rescale(CMult(CX,Cω),p);3for i=0 tolog(f+1)?1 do 4 C2←Add(C1,Rotate(C1,2i));5end 6C3←Rescale(Mult(C2,CM),pc);7for i=0 tolog(f+1)?1 do 8 CI← Add(C3,Rotate(C3,?2i));9end 10return CI

得到內(nèi)積后,使用Sigmoid近似函數(shù)進(jìn)行計(jì)算.根據(jù)公式(3),得到的結(jié)果與標(biāo)簽矩陣密文進(jìn)行同態(tài)減法,再與數(shù)據(jù)集矩陣密文做同態(tài)乘法.將結(jié)果進(jìn)行旋轉(zhuǎn)相加,再乘以學(xué)習(xí)率,可以得到梯度值.將權(quán)重與梯度值做同態(tài)減法,可以得到更新后權(quán)重值的密文.完整的密文的多分類Logistic回歸算法如算法3.

做多次迭代后,服務(wù)器得到最終的權(quán)重矩陣的密文并將其發(fā)送給客戶端.客戶端進(jìn)行解密操作,可以得到更新后的ω′并對(duì)其他數(shù)據(jù)進(jìn)行預(yù)測(cè).

在整個(gè)過程中,服務(wù)器只對(duì)密文進(jìn)行操作而不能看到任何明文.客戶端可以使用服務(wù)器的計(jì)算能力而不泄露隱私,并且能得到更新后的權(quán)重矩陣,解決多分類問題.可見,基于同態(tài)加密的多分類 Logistic回歸模型是安全且有效的.

算法3密文的多分類Logistic回歸算法Input:數(shù)據(jù)集矩陣X 加密后的密文CX,權(quán)重矩陣ω加密后的密文Cω,標(biāo)簽矩陣Y 加密后的密文CY,α>0 Output:權(quán)重矩陣密文Cω′1for iter=0 to T do 2 for k=0 to K do 3 C1←InnerProduct(CX,Cωk);4 C2←PolySigmoid(C1);5 C3←Sub(C2,CY);6 C4←Rescale(Mult(C3,CX),p);7 for i=log(f+1)?1 to log(f+1)+logn?1 do 8 C5←Add(C4,Rotate(C4,2i));end 10 C6← Rescale(α ·C5,pc);11Cω′k←Sub(Cωk,C6);12 end 13end 14return Cω′9

4 實(shí)現(xiàn)

本文的實(shí)現(xiàn)基于Cheon等實(shí)現(xiàn)HEAAN方案的開源庫(kù)[16].所有的實(shí)驗(yàn)都在Intel core i5 4200 M 2.5 GHz機(jī)器上實(shí)現(xiàn).

本文使用了來自UCI的Dermatology數(shù)據(jù)集[17]和Iris數(shù)據(jù)集[18]來測(cè)試本文的模型的性能.Dermatology數(shù)據(jù)集研究的是紅斑鱗狀疾病的鑒別診斷,是皮膚病學(xué)的一個(gè)現(xiàn)實(shí)問題.紅斑鱗狀疾病的臨床特征差別小,具有許多組織病理學(xué)特征,因此難以鑒別診斷.該數(shù)據(jù)集包含358個(gè)樣本,每個(gè)樣本包含34個(gè)特征,共分為6類.Iris數(shù)據(jù)集是常用的分類實(shí)驗(yàn)數(shù)據(jù)集,包含150個(gè)樣本,每個(gè)樣本包含4個(gè)特征,共分為3類.

為了證明方法的有效性,使用了5倍交叉驗(yàn)證方法,將數(shù)據(jù)集隨機(jī)分為5個(gè)大小相等的子集,并將其中4個(gè)子集用于訓(xùn)練,剩余 1個(gè)子集用于測(cè)試模型.由于迭代次數(shù)越高,需要的計(jì)算開銷越大,所以將同態(tài)加密下的模型的迭代次數(shù)設(shè)為7次.表1列出了分別對(duì)明文和加密數(shù)據(jù)進(jìn)行計(jì)算的模型的性能,包括平均運(yùn)行時(shí)間(加密和計(jì)算)和準(zhǔn)確率.

表1 使用5倍交叉驗(yàn)證的模型的實(shí)驗(yàn)結(jié)果Table 1 Implementation results for model with 5-fold CV

根據(jù)實(shí)驗(yàn)結(jié)果,可以看出,模型使用Sigmoid原函數(shù)進(jìn)行計(jì)算時(shí),由于不考慮開銷問題,通過增大迭代次數(shù),可以達(dá)到較高的準(zhǔn)確率.同樣使用Sigmoid近似函數(shù)進(jìn)行計(jì)算時(shí),模型對(duì)加密數(shù)據(jù)訓(xùn)練得到的準(zhǔn)確率與對(duì)未加密數(shù)據(jù)訓(xùn)練得到的準(zhǔn)確率相同,由此可以驗(yàn)證本文模型同態(tài)計(jì)算的可行性.雖然,對(duì)加密數(shù)據(jù)的訓(xùn)練速度比對(duì)未加密數(shù)據(jù)的訓(xùn)練速度相比慢得多,但是訓(xùn)練一次得到的結(jié)果可以用于多次預(yù)測(cè),所以針對(duì)注重隱私性的醫(yī)療、基因、財(cái)務(wù)等數(shù)據(jù)而言,對(duì)加密數(shù)據(jù)的訓(xùn)練速度是可以接受的.

5 總結(jié)

本文提出了一個(gè)解決方法,基于近似同態(tài)加密方案,實(shí)現(xiàn)了安全的多分類 Logistic回歸計(jì)算模型,并針對(duì)Dermatology數(shù)據(jù)集和Iris數(shù)據(jù)集對(duì)模型進(jìn)行了評(píng)估.本文的模型表現(xiàn)出較好的性能,Dermatology數(shù)據(jù)集36.70分鐘的訓(xùn)練時(shí)間驗(yàn)證了模型在現(xiàn)實(shí)應(yīng)用中的可行性,同時(shí)模型準(zhǔn)確度與未加密情況下計(jì)算的準(zhǔn)確度一致.

在未來的工作中,可以使用本文的思路和技術(shù),將同態(tài)加密應(yīng)用于其它機(jī)器學(xué)習(xí)算法.同時(shí)應(yīng)用HEAAN方案的bootstrapping方法解決較大迭代次數(shù)導(dǎo)致的計(jì)算開銷問題.