基于同態(tài)加密和秘密分享的縱向聯(lián)邦LR協(xié)議研究

符芳誠 劉舒 程勇 陶陽宇

(1.北京大學(xué)信息科學(xué)技術(shù)學(xué)院高可信軟件技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100871；2.騰訊TEG數(shù)據(jù)平臺部，深圳 518054；3. 騰訊TEG機(jī)器學(xué)習(xí)平臺部，北京 100083)

0 引言

機(jī)器學(xué)習(xí)和人工智能已經(jīng)在多個領(lǐng)域取得了巨大的成功，如圖像識別、自然語言處理、廣告推薦等。在人工智能技術(shù)突飛猛進(jìn)的同時，潛在的用戶數(shù)據(jù)濫用和隱私泄露風(fēng)險也逐漸成為業(yè)界廣泛關(guān)注的焦點(diǎn)。出于數(shù)據(jù)安全和隱私保護(hù)的考慮，不同機(jī)構(gòu)所擁有的數(shù)據(jù)無法被整合集中在一起用于機(jī)器學(xué)習(xí)建模，導(dǎo)致了數(shù)據(jù)孤島問題的出現(xiàn)，進(jìn)而阻礙了人工智能應(yīng)用的發(fā)展。近年來，如何在保證每個機(jī)構(gòu)的數(shù)據(jù)安全和用戶隱私的前提下，協(xié)同多個機(jī)構(gòu)的數(shù)據(jù)進(jìn)行聯(lián)合機(jī)器學(xué)習(xí)建模，從而提高模型的表達(dá)能力、更深入地釋放數(shù)據(jù)價值，成為了學(xué)術(shù)界與工業(yè)界廣泛研究的熱點(diǎn)課題[1-2]。

聯(lián)邦學(xué)習(xí)(Federated Learning，F(xiàn)L)[3]是由谷歌于2016年提出的概念，旨在解決如何在數(shù)據(jù)不出本地的情況下，聯(lián)合多個參與方(如智能手機(jī)等終端設(shè)備)中的數(shù)據(jù)進(jìn)行模型訓(xùn)練。依據(jù)參與方不同的數(shù)據(jù)劃分形式，聯(lián)邦學(xué)習(xí)被進(jìn)一步細(xì)分為橫向聯(lián)邦學(xué)習(xí)(Horizontal FL)、縱向聯(lián)邦學(xué)習(xí)(Vertical FL)和聯(lián)邦遷移學(xué)習(xí)三種范式[4]。本文關(guān)注的是縱向聯(lián)邦學(xué)習(xí)場景。如圖1所示，在縱向聯(lián)邦學(xué)習(xí)中，不同的參與方擁有不同的特征空間，但在樣本空間上存在交集；該交集部分可以被視作一個虛擬的縱向劃分的數(shù)據(jù)集(即虛擬寬表)，用于聯(lián)合的數(shù)據(jù)建模與分析。此外，在縱向聯(lián)邦學(xué)習(xí)中，只有一個參與方擁有標(biāo)簽信息(Label)，稱該參與方為參與方B，并稱沒有標(biāo)簽信息的參與方為參與方A。針對最常用的機(jī)器學(xué)習(xí)算法協(xié)議之一，本文圍繞兩方縱向聯(lián)邦學(xué)習(xí)場景下的邏輯回歸(Logistic Regression，LR)協(xié)議[5-7]，著重分析如何設(shè)計一個安全的縱向聯(lián)邦LR協(xié)議，并結(jié)合同態(tài)加密和秘密分享兩種技術(shù)，提出了一種安全的聯(lián)邦LR協(xié)議。在半誠實(shí)安全模型下，證明了所設(shè)計的縱向聯(lián)邦LR協(xié)議的安全性。該縱向聯(lián)邦LR協(xié)議已部署于通用隱私計算平臺Angel PowerFL中，并獲得了廣泛的應(yīng)用落地。

1 背景知識

1.1 多方安全計算技術(shù)

以下將對多方安全計算(Secure Multi-Party Computation，MPC)技術(shù)進(jìn)行介紹，包括同態(tài)加密、秘密分享以及安全模型。

1.1.1 同態(tài)加密

同態(tài)加密(Homomorphic Encryption，HE)[8, 9]指的是一類滿足在密文空間上進(jìn)行運(yùn)算的密碼學(xué)方法。根據(jù)所支持的運(yùn)算，同態(tài)加密可以分為全同態(tài)加密(Fully HE，F(xiàn)HE)、層級全同態(tài)加密(Leveled fully，LFHE)、加法半同態(tài)加密(Additive HE，AHE)以及乘法半同態(tài)加密(Multiplicative HE，MHE)等。

本文關(guān)注于加法半同態(tài)加密，例如Paillier加密算法[10]是一種經(jīng)典的加法半同態(tài)加密算法，并且已經(jīng)被應(yīng)用于常用的聯(lián)邦學(xué)習(xí)算法中[5,6,11-14]。在初始化階段，Paillier加密算法生成密鑰對〈pk,sk〉。其中，公鑰pk被用于進(jìn)行加密，并且可以被公開至其他參與方，私鑰sk被用于解密，不可被公開。給定整數(shù)x,y，Paillier加密算法支持下述操作：

1.1.2 秘密分享

秘密分享(Secret Sharing，SS)[15-17]是多方安全計算中最常用的技術(shù)之一。秘密分享的主要思路是將一個數(shù)值拆分為多個秘密，并將每份秘密分發(fā)至不同的參與方，使得所有參與方都無法得知真正的數(shù)值。例如，數(shù)值x可被秘密分享為〈xA,xB〉，滿足xA+xB=x。其中，參與方A持有xA，參與方B持有xB。值得說明的是，秘密分享一般在群空間執(zhí)行計算，例如整數(shù)加法群。

本文關(guān)注于兩方的加法秘密分享。給定兩個秘密分享的變量〈xA,xB〉,〈yA,yB〉，秘密分享的加法操作可以通過本地執(zhí)行，即〈xA+yA,xB+yB〉。秘密分享的乘法通常需要借助乘法三元組(Multiplicative Triplets，或Beaver Triplets)[9, 18, 19]。

1.1.3 安全模型

本文考慮半誠實(shí)安全模型(Semi-Honest Security Model, 也稱為Honest-But-Curios Security Model)。在該安全模型下，所有參與方誠實(shí)地按照算法協(xié)議進(jìn)行計算，但不超過一個參與方可能會被敵手(Adversary)所腐化，并嘗試通過算法協(xié)議中可以得到的信息，對其他參與方的隱私數(shù)據(jù)進(jìn)行分析和推理。本文考慮語義安全(Semantic Security)，即假設(shè)所有敵手均滿足多項(xiàng)式時間復(fù)雜度。當(dāng)分析算法協(xié)議的安全性時，本文采用理想的-真實(shí)的模型(Ideal-real Model)來進(jìn)行分析，其定義如下[20, 21]。

根據(jù)定義1，文獻(xiàn)[7]對圖2所示的算法協(xié)議的安全性進(jìn)行了嚴(yán)格的證明(本文引用該結(jié)論為引理1，不再對證明過程進(jìn)行贅述)。

引理1：在不超過一個參與方被半誠實(shí)敵手腐化的前提下，圖2所示的協(xié)議ΠHE2SS安全地實(shí)現(xiàn)了如表1所示的理想功能FHE2SS。

表1 同態(tài)密文轉(zhuǎn)換為兩個秘密分享變量的理想功能

1.2 縱向聯(lián)邦聯(lián)邦邏輯回歸算法

邏輯回歸(Logistic Regression，LR)是最常用的機(jī)器學(xué)習(xí)算法之一，常用于金融風(fēng)控場景。以下將對縱向聯(lián)邦學(xué)習(xí)中的邏輯回歸算法的計算目標(biāo)進(jìn)行簡要的介紹。

假設(shè)參與方A與參與方B的輸入特征維度分別為INA,INB，記參與雙方的邏輯回歸模型的模型參數(shù)分別為WA∈INA×1,WB∈INB×1。假設(shè)參與雙方的特征分別為XA∈N×INA,XB∈N×INB，參與方B的標(biāo)簽為y∈{0,1}N，其中N為數(shù)據(jù)集中的樣本條數(shù)。邏輯回歸模型的預(yù)測輸出為其中sigmoid(·)為Sigmoid函數(shù)，且Z=XAWA+XBWB。邏輯回歸算法的訓(xùn)練目標(biāo)是尋找最小化損失函數(shù)值的模型參數(shù)，即其中L(·,·)為交差熵?fù)p失函數(shù)(cross-entropy loss)，即

(1)

2 聯(lián)邦LR算法與分析

以下將對縱向聯(lián)邦邏輯回歸算法的設(shè)計思路進(jìn)行討論，然后對所提出的算法協(xié)議流程進(jìn)行介紹，最后對該算法協(xié)議進(jìn)行安全性分析。

2.1 設(shè)計思路

在設(shè)計具體的算法協(xié)議之前，先對縱向聯(lián)邦LR算法中每種數(shù)據(jù)的安全性進(jìn)行逐個分析，這種分析有助于算法協(xié)議的設(shè)計。

2.1.1 模型參數(shù)與梯度保護(hù)

正如接下來將討論的，每個參與方P不可獲得XPWP。因此，在設(shè)計具體的算法協(xié)議時，不允許任何參與方獲得己方的模型參數(shù)，即參與方A不可獲得完整的WA，參與方B不可獲得完整的WB。

2.1.2 縱向聯(lián)邦LR前向計算

由于標(biāo)簽信息y屬于參與方B的隱私數(shù)據(jù)，因此一個安全的聯(lián)邦LR算法協(xié)議里不應(yīng)該允許參與方A有任何可以分析標(biāo)簽信息的可能性。由于聯(lián)邦LR算法是一種有監(jiān)督的機(jī)器學(xué)習(xí)算法，其目標(biāo)是使前向計算的預(yù)測輸出盡可能地擬合標(biāo)簽信息y，因此所有前向計算的中間結(jié)果均可被用于分析標(biāo)簽信息y。為了保護(hù)參與方B的標(biāo)簽信息y，在設(shè)計前向計算的算法協(xié)議時，需要保證參與方A不可獲得任何前向計算中的中間結(jié)果，即參與方A不可以獲得XAWA,XBWB,Z。

在一些現(xiàn)有的縱向聯(lián)邦LR算法協(xié)議中，盡管參與方A不可獲得模型輸出Z，卻仍然可以獲得參與方A的計算結(jié)果，即XAWA，所以存在泄露標(biāo)簽信息y風(fēng)險。本文將進(jìn)一步說明這類方法存在標(biāo)簽泄露的風(fēng)險，即參與方A可以通過分析XAWA來對標(biāo)簽信息y進(jìn)行推測。

2.1.3 縱向聯(lián)邦LR反向計算

在反向計算中所計算的數(shù)據(jù)可分為反向偏導(dǎo)(Backward Derivatives)，即?Z，以及模型參數(shù)對應(yīng)的梯度?WA和?WB。

根據(jù)上述分析，表2匯總了在設(shè)計縱向聯(lián)邦LR的算法協(xié)議時，每個參與方不可獲得的信息。

表2 縱向聯(lián)邦邏輯回歸算法協(xié)議中，為了保證數(shù)據(jù)安全，各參與方不可獲得的信息

2.2 一種安全的兩方聯(lián)邦LR協(xié)議

2.2.1 初始化流程

如圖4所示，本文所提出的聯(lián)邦LR算法的初始化流程分為以下4步。

(1)參與方A隨機(jī)挑選大整數(shù)σA，滿足σA大于INA(即A方特征維度)，發(fā)送σA至參與方B，并接受參與方B發(fā)送過來的σB；對稱地，參與方B隨機(jī)挑選大整數(shù)σB，滿足σB大于INB(即B方特征維度)，發(fā)送σB至參與方A，并接受參與方A發(fā)送過來的σA。

? 對于參與方B，其模型權(quán)重被通過秘密分享技術(shù)進(jìn)行保護(hù)，即模型權(quán)重WB被切分為UB和VB，使得參與方B不能獲得明文形式的完整的模型參數(shù)WB。其中，秘密分享是在密文空間的計算，即大整數(shù)空間里的秘密分享計算，例如模n2計算，n是Paillier同態(tài)加密算法的模長(Modulus)。

值得注意的是，在實(shí)際的初始化過程中，每個參與方還需要初始化己方的密鑰對，并交換雙方的公鑰，但本文假設(shè)此步驟已經(jīng)完成，因此在圖4中省略了相關(guān)公鑰分發(fā)流程。

2.2.2 兩方聯(lián)邦LR協(xié)議前向計算流程

如圖5所示，本文提出的聯(lián)邦LR算法的前向計算流程分為以下4步。

(1)參與雙方各自采樣一個小批量的訓(xùn)練數(shù)據(jù)，記為XA和XB。

在上述前向計算的過程中，使用了同態(tài)加密和秘密分享技術(shù)對敏感數(shù)據(jù)信息進(jìn)行了保護(hù)，每個參與方可獲取的信息滿足表2所列的協(xié)議安全要求。此外，前向計算的預(yù)測輸出是正確無誤的，即計算過程中的隨機(jī)數(shù)(即秘密分片εA,εB)在最后一步被消除，并且不需要對Sigmoid函數(shù)或者交叉熵?fù)p失函數(shù)進(jìn)行多項(xiàng)式近似計算。綜上所述，該算法流程同時保證了安全性和正確性，且無需對非線性函數(shù)進(jìn)行多項(xiàng)式近似計算，從而保證了聯(lián)邦LR模型的無損。

2.2.3 兩方聯(lián)邦LR協(xié)議反向計算流程

如圖6所示，本文提出的聯(lián)邦LR算法的反向計算流程分為三步：

2.3 安全性分析

本文所提出的算法協(xié)議滿足了表2中的所有安全要求，即所有的中間結(jié)果，如XAWA,?Z等，均被使用同態(tài)加密或秘密分享技術(shù)進(jìn)行了保護(hù)。此外，該算法協(xié)議沒有對非線性函數(shù)(包括Sigmoid函數(shù)和交叉熵?fù)p失函數(shù))進(jìn)行多項(xiàng)式近似計算，保證了該算法協(xié)議的結(jié)果是無損的。也就是說，前向計算的預(yù)測輸出和反向計算的模型更新均是正確的。

為了更嚴(yán)格地對該算法協(xié)議的安全性進(jìn)行分析，筆者提出定義兩種理想功能FFw,FBw，分別對應(yīng)算法的前向計算和反向計算過程，并證明該算法協(xié)議的安全保證。

表3 前向計算的理想功能

定理1：在不超過一個參與方被半誠實(shí)敵手腐化的前提下，圖5所示的協(xié)議ΠFw安全地實(shí)現(xiàn)了理想功能FFw。

證明：分別對參與方A和參與方B進(jìn)行分析論證。

如表4所示，在反向計算的理想功能FBw中，每個參與方分別輸入己方的(小批量)特征數(shù)據(jù)，被同態(tài)加密和/或秘密分享的模型，以及密鑰對，參與方B還輸入了標(biāo)簽和前向計算的預(yù)測輸出；每個參與方分別輸出己方的模型梯度。定理2對反向計算流程的安全性進(jìn)行了證明。

表4 反向計算的理想功能

定理2：在不超過一個參與方被半誠實(shí)敵手腐化的前提下，圖6所示的協(xié)議ΠBw安全地實(shí)現(xiàn)了理想功能FBw。

證明：分別對參與方A和參與方B進(jìn)行分析論證。

參與方B在協(xié)議ΠBw中沒有接收到任何消息，即參與方B視圖中的所有數(shù)據(jù)均為通過本地計算得到，顯然參與方B的視圖可以被完美地模擬。

證明：首先，考慮線性方程組Z=ZA+ZB，其中ZA=XAWA,ZB=XBWB。該方程組中僅有Z∈BS×1是參與方B已知的，共有BS個已知變量(Batch Size)；然而，由于ZA和ZB均是參與方B未知的，因此該方程組中共有2×BS個未知變量。所以，該方程組一定存在無窮多種可能解，即ZA=XAWA存在無窮多種可能的值。

其次，考慮任意可能的XAWA，隨機(jī)挑選任意一個可逆矩陣M∈INA×INA，則有(XAM-1)(MWA)=XAWA。由于XAWA和M均是任意的，所以XA,WA存在無窮多種可能的值。

3 結(jié)束語

本文對縱向聯(lián)邦LR算法協(xié)議的安全性進(jìn)行了全面的分析，并詳細(xì)列出了保證特征數(shù)據(jù)和標(biāo)簽信息安全的具體要求?；谠摲治觯岢隽艘环N新穎的兩方縱向聯(lián)邦LR協(xié)議，該協(xié)議通過結(jié)合同態(tài)加密和秘密分享技術(shù)來保證特征數(shù)據(jù)和標(biāo)簽信息的安全，且無需對非線性函數(shù)使用多項(xiàng)式近似計算，從而可以保證聯(lián)邦LR模型無損。筆者在半誠實(shí)安全模型下證明了該協(xié)議的安全性，包括模型訓(xùn)練和模型推理流程的安全性。本文所提出的聯(lián)邦LR協(xié)議的交互流程簡單，易于工程實(shí)現(xiàn)，且計算和通信開銷都較小，已經(jīng)在通用隱私計算平臺Angel PowerFL中獲得了廣泛的應(yīng)用和經(jīng)過了充分的檢驗(yàn)。