符芳誠 劉舒 程勇 陶陽宇

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

0 引言

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

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

1 背景知識

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

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

1.1.1 同態(tài)加密

同態(tài)加密(Homomorphic Encryption，HE)[8, 9]指的是一類滿足在密文空間上進行運算的密碼學方法。根據(jù)所支持的運算，同態(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)邦學習算法中[5,6,11-14]。在初始化階段，Paillier加密算法生成密鑰對〈pk,sk〉。其中，公鑰pk被用于進行加密，并且可以被公開至其他參與方，私鑰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 安全模型

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

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

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

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

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

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

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

(1)

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

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

2.1 設(shè)計思路

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

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

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

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

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

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

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

在反向計算中所計算的數(shù)據(jù)可分為反向偏導(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隨機挑選大整數(shù)σA，滿足σA大于INA(即A方特征維度)，發(fā)送σA至參與方B，并接受參與方B發(fā)送過來的σB；對稱地，參與方B隨機挑選大整數(shù)σB，滿足σB大于INB(即B方特征維度)，發(fā)送σB至參與方A，并接受參與方A發(fā)送過來的σA。

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

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

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

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

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

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

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

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

2.3 安全性分析

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

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

表3 前向計算的理想功能

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

證明：分別對參與方A和參與方B進行分析論證。

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

表4 反向計算的理想功能

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

證明：分別對參與方A和參與方B進行分析論證。

參與方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，隨機挑選任意一個可逆矩陣M∈INA×INA，則有(XAM-1)(MWA)=XAWA。由于XAWA和M均是任意的，所以XA,WA存在無窮多種可能的值。

3 結(jié)束語

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