基于同态加密和秘密分享的纵向联邦LR协议研究

符芳诚 刘舒 程勇 陶阳宇

(1.北京大学信息科学技术学院高可信软件技术重点实验室，北京 100871；2.腾讯TEG数据平台部，深圳 518054；3. 腾讯TEG机器学习平台部，北京 100083)

0 引言

机器学习和人工智能已经在多个领域取得了巨大的成功，如图像识别、自然语言处理、广告推荐等。在人工智能技术突飞猛进的同时，潜在的用户数据滥用和隐私泄露风险也逐渐成为业界广泛关注的焦点。出于数据安全和隐私保护的考虑，不同机构所拥有的数据无法被整合集中在一起用于机器学习建模，导致了数据孤岛问题的出现，进而阻碍了人工智能应用的发展。近年来，如何在保证每个机构的数据安全和用户隐私的前提下，协同多个机构的数据进行联合机器学习建模，从而提高模型的表达能力、更深入地释放数据价值，成为了学术界与工业界广泛研究的热点课题[1-2]。

联邦学习(Federated Learning，FL)[3]是由谷歌于2016年提出的概念，旨在解决如何在数据不出本地的情况下，联合多个参与方(如智能手机等终端设备)中的数据进行模型训练。依据参与方不同的数据划分形式，联邦学习被进一步细分为横向联邦学习(Horizontal FL)、纵向联邦学习(Vertical FL)和联邦迁移学习三种范式[4]。本文关注的是纵向联邦学习场景。如图1所示，在纵向联邦学习中，不同的参与方拥有不同的特征空间，但在样本空间上存在交集；该交集部分可以被视作一个虚拟的纵向划分的数据集(即虚拟宽表)，用于联合的数据建模与分析。此外，在纵向联邦学习中，只有一个参与方拥有标签信息(Label)，称该参与方为参与方B，并称没有标签信息的参与方为参与方A。针对最常用的机器学习算法协议之一，本文围绕两方纵向联邦学习场景下的逻辑回归(Logistic Regression，LR)协议[5-7]，着重分析如何设计一个安全的纵向联邦LR协议，并结合同态加密和秘密分享两种技术，提出了一种安全的联邦LR协议。在半诚实安全模型下，证明了所设计的纵向联邦LR协议的安全性。该纵向联邦LR协议已部署于通用隐私计算平台Angel PowerFL中，并获得了广泛的应用落地。

1 背景知识

1.1 多方安全计算技术

以下将对多方安全计算(Secure Multi-Party Computation，MPC)技术进行介绍，包括同态加密、秘密分享以及安全模型。

1.1.1 同态加密

同态加密(Homomorphic Encryption，HE)[8, 9]指的是一类满足在密文空间上进行运算的密码学方法。根据所支持的运算，同态加密可以分为全同态加密(Fully HE，FHE)、层级全同态加密(Leveled fully，LFHE)、加法半同态加密(Additive HE，AHE)以及乘法半同态加密(Multiplicative HE，MHE)等。

本文关注于加法半同态加密，例如Paillier加密算法[10]是一种经典的加法半同态加密算法，并且已经被应用于常用的联邦学习算法中[5,6,11-14]。在初始化阶段，Paillier加密算法生成密钥对〈pk,sk〉。其中，公钥pk被用于进行加密，并且可以被公开至其他参与方，私钥sk被用于解密，不可被公开。给定整数x,y，Paillier加密算法支持下述操作：

1.1.2 秘密分享

秘密分享(Secret Sharing，SS)[15-17]是多方安全计算中最常用的技术之一。秘密分享的主要思路是将一个数值拆分为多个秘密，并将每份秘密分发至不同的参与方，使得所有参与方都无法得知真正的数值。例如，数值x可被秘密分享为〈xA,xB〉，满足xA+xB=x。其中，参与方A持有xA，参与方B持有xB。值得说明的是，秘密分享一般在群空间执行计算，例如整数加法群。

本文关注于两方的加法秘密分享。给定两个秘密分享的变量〈xA,xB〉,〈yA,yB〉，秘密分享的加法操作可以通过本地执行，即〈xA+yA,xB+yB〉。秘密分享的乘法通常需要借助乘法三元组(Multiplicative Triplets，或Beaver Triplets)[9, 18, 19]。

1.1.3 安全模型

本文考虑半诚实安全模型(Semi-Honest Security Model, 也称为Honest-But-Curios Security Model)。在该安全模型下，所有参与方诚实地按照算法协议进行计算，但不超过一个参与方可能会被敌手(Adversary)所腐化，并尝试通过算法协议中可以得到的信息，对其他参与方的隐私数据进行分析和推理。本文考虑语义安全(Semantic Security)，即假设所有敌手均满足多项式时间复杂度。当分析算法协议的安全性时，本文采用理想的-真实的模型(Ideal-real Model)来进行分析，其定义如下[20, 21]。

根据定义1，文献[7]对图2所示的算法协议的安全性进行了严格的证明(本文引用该结论为引理1，不再对证明过程进行赘述)。

引理1：在不超过一个参与方被半诚实敌手腐化的前提下，图2所示的协议ΠHE2SS安全地实现了如表1所示的理想功能FHE2SS。

表1 同态密文转换为两个秘密分享变量的理想功能

1.2 纵向联邦联邦逻辑回归算法

逻辑回归(Logistic Regression，LR)是最常用的机器学习算法之一，常用于金融风控场景。以下将对纵向联邦学习中的逻辑回归算法的计算目标进行简要的介绍。

假设参与方A与参与方B的输入特征维度分别为INA,INB，记参与双方的逻辑回归模型的模型参数分别为WA∈INA×1,WB∈INB×1。假设参与双方的特征分别为XA∈N×INA,XB∈N×INB，参与方B的标签为y∈{0,1}N，其中N为数据集中的样本条数。逻辑回归模型的预测输出为其中sigmoid(·)为Sigmoid函数，且Z=XAWA+XBWB。逻辑回归算法的训练目标是寻找最小化损失函数值的模型参数，即其中L(·,·)为交差熵损失函数(cross-entropy loss)，即

(1)

2 联邦LR算法与分析

以下将对纵向联邦逻辑回归算法的设计思路进行讨论，然后对所提出的算法协议流程进行介绍，最后对该算法协议进行安全性分析。

2.1 设计思路

在设计具体的算法协议之前，先对纵向联邦LR算法中每种数据的安全性进行逐个分析，这种分析有助于算法协议的设计。

2.1.1 模型参数与梯度保护

正如接下来将讨论的，每个参与方P不可获得XPWP。因此，在设计具体的算法协议时，不允许任何参与方获得己方的模型参数，即参与方A不可获得完整的WA，参与方B不可获得完整的WB。

2.1.2 纵向联邦LR前向计算

由于标签信息y属于参与方B的隐私数据，因此一个安全的联邦LR算法协议里不应该允许参与方A有任何可以分析标签信息的可能性。由于联邦LR算法是一种有监督的机器学习算法，其目标是使前向计算的预测输出尽可能地拟合标签信息y，因此所有前向计算的中间结果均可被用于分析标签信息y。为了保护参与方B的标签信息y，在设计前向计算的算法协议时，需要保证参与方A不可获得任何前向计算中的中间结果，即参与方A不可以获得XAWA,XBWB,Z。

在一些现有的纵向联邦LR算法协议中，尽管参与方A不可获得模型输出Z，却仍然可以获得参与方A的计算结果，即XAWA，所以存在泄露标签信息y风险。本文将进一步说明这类方法存在标签泄露的风险，即参与方A可以通过分析XAWA来对标签信息y进行推测。

2.1.3 纵向联邦LR反向计算

在反向计算中所计算的数据可分为反向偏导(Backward Derivatives)，即∇Z，以及模型参数对应的梯度∇WA和∇WB。

根据上述分析，表2汇总了在设计纵向联邦LR的算法协议时，每个参与方不可获得的信息。

表2 纵向联邦逻辑回归算法协议中，为了保证数据安全，各参与方不可获得的信息

2.2 一种安全的两方联邦LR协议

2.2.1 初始化流程

如图4所示，本文所提出的联邦LR算法的初始化流程分为以下4步。

(1)参与方A随机挑选大整数σA，满足σA大于INA(即A方特征维度)，发送σA至参与方B，并接受参与方B发送过来的σB；对称地，参与方B随机挑选大整数σB，满足σB大于INB(即B方特征维度)，发送σB至参与方A，并接受参与方A发送过来的σA。

• 对于参与方B，其模型权重被通过秘密分享技术进行保护，即模型权重WB被切分为UB和VB，使得参与方B不能获得明文形式的完整的模型参数WB。其中，秘密分享是在密文空间的计算，即大整数空间里的秘密分享计算，例如模n2计算，n是Paillier同态加密算法的模长(Modulus)。

值得注意的是，在实际的初始化过程中，每个参与方还需要初始化己方的密钥对，并交换双方的公钥，但本文假设此步骤已经完成，因此在图4中省略了相关公钥分发流程。

2.2.2 两方联邦LR协议前向计算流程

如图5所示，本文提出的联邦LR算法的前向计算流程分为以下4步。

(1)参与双方各自采样一个小批量的训练数据，记为XA和XB。

在上述前向计算的过程中，使用了同态加密和秘密分享技术对敏感数据信息进行了保护，每个参与方可获取的信息满足表2所列的协议安全要求。此外，前向计算的预测输出是正确无误的，即计算过程中的随机数(即秘密分片εA,εB)在最后一步被消除，并且不需要对Sigmoid函数或者交叉熵损失函数进行多项式近似计算。综上所述，该算法流程同时保证了安全性和正确性，且无需对非线性函数进行多项式近似计算，从而保证了联邦LR模型的无损。

2.2.3 两方联邦LR协议反向计算流程

如图6所示，本文提出的联邦LR算法的反向计算流程分为三步：

2.3 安全性分析

本文所提出的算法协议满足了表2中的所有安全要求，即所有的中间结果，如XAWA,∇Z等，均被使用同态加密或秘密分享技术进行了保护。此外，该算法协议没有对非线性函数(包括Sigmoid函数和交叉熵损失函数)进行多项式近似计算，保证了该算法协议的结果是无损的。也就是说，前向计算的预测输出和反向计算的模型更新均是正确的。

为了更严格地对该算法协议的安全性进行分析，笔者提出定义两种理想功能FFw,FBw，分别对应算法的前向计算和反向计算过程，并证明该算法协议的安全保证。

表3 前向计算的理想功能

定理1：在不超过一个参与方被半诚实敌手腐化的前提下，图5所示的协议ΠFw安全地实现了理想功能FFw。

证明：分别对参与方A和参与方B进行分析论证。

如表4所示，在反向计算的理想功能FBw中，每个参与方分别输入己方的(小批量)特征数据，被同态加密和/或秘密分享的模型，以及密钥对，参与方B还输入了标签和前向计算的预测输出；每个参与方分别输出己方的模型梯度。定理2对反向计算流程的安全性进行了证明。

表4 反向计算的理想功能

定理2：在不超过一个参与方被半诚实敌手腐化的前提下，图6所示的协议ΠBw安全地实现了理想功能FBw。

证明：分别对参与方A和参与方B进行分析论证。

参与方B在协议ΠBw中没有接收到任何消息，即参与方B视图中的所有数据均为通过本地计算得到，显然参与方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 结束语

本文对纵向联邦LR算法协议的安全性进行了全面的分析，并详细列出了保证特征数据和标签信息安全的具体要求。基于该分析，提出了一种新颖的两方纵向联邦LR协议，该协议通过结合同态加密和秘密分享技术来保证特征数据和标签信息的安全，且无需对非线性函数使用多项式近似计算，从而可以保证联邦LR模型无损。笔者在半诚实安全模型下证明了该协议的安全性，包括模型训练和模型推理流程的安全性。本文所提出的联邦LR协议的交互流程简单，易于工程实现，且计算和通信开销都较小，已经在通用隐私计算平台Angel PowerFL中获得了广泛的应用和经过了充分的检验。