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

1.信息物理社會可信服務計算教育部重點實驗室(重慶大學),重慶400044

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

1 引言

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

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

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

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

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

2 相關技術

2.1 HEAAN方案

同態(tài)加密是一種加密技術,允許我們在不解密的情況下對加密數(shù)據(jù)進行操作,并得到與明文計算相匹配的計算的結果.該技術在實際應用中具有很大潛力,因為它允許我們在公共卻不信任的服務器上安全地進行外包計算.

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

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

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

?參數(shù)設置(λ):輸入安全參數(shù)λ,輸出多項式維度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).設Q=q2,取樣s′←s2,a′←RQ,e′←χ,輸出計算密鑰 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),設 (d0,d1,d2)= (b0b1,a0b1+a1b0,a0b1)(modq′),輸出cmult←(d0,d1)+?1/q·d2·evk?(modq′).

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

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

有關HEAAN方案的技術細節(jié)和噪音分析可以參考文獻[11].有關HEAAN方案的bootstrapping方法可以參考文獻[12].

2.2 Logistic回歸和梯度下降

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

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

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

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

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

其中,α表示學習率.

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

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

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

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

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

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

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

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

3.1 多分類 Logistic回歸

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

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

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

OvR策略只需要訓練k個分類器,相對其它拆解方法,存儲和測試時間開銷通常較小.使用OvR策略得到的多分類Logistic回歸的詳細過程如算法1.

算法1多分類Logistic回歸算法Input:X ∈RN×F,y∈RN,α>0 Output:ω ∈ RK×F 1初始化權重矩陣ω;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)計算

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

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

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

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

算法2內積計算Input:數(shù)據(jù)集矩陣X 加密后的密文CX,權重向量ωk加密后的密文Cωk,常量矩陣M 加密后的密文CM Output:內積矩陣密文CI 1將Cωk復制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

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

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

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

算法3密文的多分類Logistic回歸算法Input:數(shù)據(jù)集矩陣X 加密后的密文CX,權重矩陣ω加密后的密文Cω,標簽矩陣Y 加密后的密文CY,α>0 Output:權重矩陣密文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 實現(xiàn)

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

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

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

表1 使用5倍交叉驗證的模型的實驗結果Table 1 Implementation results for model with 5-fold CV

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

5 總結

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

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