基于安全两方计算的隐私保护线性回归算法

魏立斐，李梦思，张 蕾，陈聪聪，陈玉娇，王 勤

上海海洋大学 信息学院，上海201306

线性回归（Linear Regression）作为一种广泛使用的基础型机器学习算法，是通过对多个影响因素和结果进行拟合，从而以线性模型来建模一个或多个自变量与因变量之间相关关系的一种方法。为了提高和优化回归模型性能，通常需要训练大量的原始数据，但本地计算资源及存储资源有限，使得一些企业或机构无法满足独自训练模型的需求。而云计算[1]的迅速发展，使得这一问题得到很好地解决，目前有许多云计算服务商业平台（如亚马逊和谷歌等）允许客户端上传数据到云服务器进行各种机器学习任务。但因为云计算的不可信性[2]，它可以查看并记录用户的数据信息，甚至可能遭受到敌手的攻击而泄露用户数据，所以研究能够保护隐私的线性回归方案尤为重要。目前已经有许多学者提出了具有隐私保护的线性回归方案。基于差分隐私的方法[3-5]是通过对回归模型添加适当噪声的方式来实现隐私保护，但引入噪声的同时会导致模型性能有所下降。基于同态加密（Homomorphic Encryption，HE）的方案[6-8]则通常需要客户端使用同态加密算法对训练数据加密之后，由云服务器利用同态性质在密文上进行训练，但使用同态加密算法对大量的数据实现加密对于客户端来说计算开销太大，并且由于同态加密计算本身的限制，无法实现任意次的加法和乘法，在现实环境中并不实用。

安全多方计算（Secure Multi-party Computation，SMC）起源于1982年Yao[9]提出的百万富翁问题，核心思想是在不泄露任何参与方的私有输入情况下正确地计算目标函数。作为安全计算领域里的核心内容之一，SMC 是构造多方计算协议的基础，可用于解决现实世界中的实际问题，但它需要借助现代密码学中的其他技术来实现[10-12]，比如基于秘密共享（Secret Sharing）、混淆电路（Garbled Circuits，GC）、同态加密等技术的安全多方计算线性回归方案[13-15]。2011 年，Hall 等人[16]基于同态加密首次提出了一种可以达到安全性定义的安全两方计算线性回归协议，但该方案过于依赖计算开销巨大的同态加密，无法应用到数据条目庞大的数据集中。Martine 等人[17]基于文献[16]在数据集分布于多个参与方的情境下，提出了一种能够保护数据隐私的线性回归方案，各计算方可以在不共享自己私有数据集的情况下协同训练线性回归模型。Dankar[18]通过引入一个半可信第三方，在理论上提出了一种支持多个数据提供者参与的隐私保护线性回归方案。Adrià等人[19]提出一种用于任意分布于多个参与方的训练集的隐私保护线性回归方案，该方案结合了Yao的混淆电路和全同态加密方案。之后，Mohassel 等人[20]提出的SecureML 方案基于混淆电路和不经意传输（Oblivious Transfer，OT）[21]协议，设计了支持安全两方计算的随机梯度下降算法，实现了线性回归、逻辑回归以及神经网络的模型训练任务。该方案由数据拥有者将私有数据通过秘密共享的方式分发给两个服务器，由两个服务器用安全多方计算的方式训练模型，实现了加法和乘法的分布式计算。在SecureML的基础上，唐春明等人[22]借助基于OT协议生成的乘法三元组[23]，提出了具有隐私性的回归模型训练算法，同时实现了对训练数据及模型参数的隐私保护。Akavia 等人[24]提出一种能够从多个数据所有者提供的数据集中学习线性回归模型的数据隐私保护方案，该方案使用两个非共谋服务器和线性同态加密（Linearly Homomorphic Encryption）来学习正则化线性回归模型。Dong等人[25]提出了一个可以适应半诚实和恶意环境下的分布式机器学习框架，每个参与者将自己的梯度分成共享份额，并分配给多个参数服务器，由参数服务器聚合梯度后发还给参与者，参与者在本地更新参数。

受安全多方计算核心思想的启发，本文拟采用安全两方计算技术来解决线性回归方案中的隐私保护问题。在此之前，Mohassel[20]和唐春明[22]提出的基于安全两方计算的隐私保护方案，由两个非共谋云服务器协作完成线性回归任务，但他们均使用通信复杂度较高的OT 协议，因此在规模比较大的数据集上使用会有一定的局限性。另外，文献[20]中的线性回归协议虽然解决了数据隐私保护问题，但需要两个云服务器直接重构模型参数，因此该方案无法保证模型参数的隐私性。不同于文献[20]和文献[22]，本文避免使用通信复杂度较高的OT 协议，而是通过使用加法同态加密和加法掩码相结合的方法实现秘密共享值的乘法计算，避免两方服务器私有信息的泄露。相比之下，本文方案在保证数据和模型参数隐私不被泄露的同时，所需要的通信开销更低。本文主要贡献包括以下两方面：

（1）使用安全两方计算的方式执行小批量梯度下降算法更新模型参数，通过将加法同态加密与加法掩码相结合的方法，实现了秘密共享值之间的乘法计算。

（2）提出并实现了隐私保护的预测方案，确保云服务器在预测过程中无法获得预测数据的具体信息，同时在预测结束后无法获得真正的预测结果，实现了隐私保护线性回归预测。

1 预备知识

1.1 线性回归

给定一个包含n条数据的训练集(X,y)，其中X∈Rn×d表示具有d个特征的样本集特征矩阵，y∈Rn表示n条数据样本对应的标签向量，线性回归任务的目标是从训练集(X,y) 学习模型M的一组回归系数θ∈Rd，使得目标值y≈Xθ。

为了衡量模型的好坏，需要对训练出的模型进行性能评价，一个常用的评价标准是平方误差和，即目标值和预测结果之间差距的平方和，因此可以定量化损失函数：

线性回归的任务就是寻求使得L最小化时的θ值。

梯度下降是一个用来求目标函数最小值的优化算法，本文使用小批量梯度下降算法（Mini-Batch Gradient Descent，MBGD）来求出损失函数L(θ)的最小值。它在更新每一参数时都使用一部分样本进行更新，相比较随机梯度下降算法（Stochastic Gradient Descent，SGD）和批量梯度下降算法（Batch Gradient Descent，BGD），该算法可以缩减模型收敛所需要的迭代次数，同时使收敛的结果更接近梯度下降的效果。对于小批量数据集(XB,yB)的梯度下降算法的参数更新方式为：

其中，XB和yB分别表示小批量样本集的特征值和目标值，e表示当前迭代次数，α表示学习率，| |B表示小批量样本数量。

1.2 加法同态加密

同态加密最早是由Rivest 等人[26]提出，这种加密方法允许直接在密文上进行某些特殊类型的计算而获得密文结果，并且将密文结果解密后，其值与在明文上执行的函数结果一致。本文使用支持加法同态加密的Paillier 加密系统[27]，它是由Paillier 于1999 年基于复合剩余类困难问题建立的概率公钥加密系统。该加密系统工作原理如下：

（l）密钥生成KeyGen(·)→(pk,sk)：随机生成两个大素数p、q满足gcd(pq,(p－1)(q－1))=1，计算N=pq,λ=lcm(p－1,q－1)，随机选择整数，则公钥pk=(g,N)，私钥sk=λ。

（2）加密过程Enc(pk,m)→c：选择一个随机数r∈，则明文m对应的密文c=gmrNmodN2。

（3）解密过程Dec(sk,c)→m：对于密文c解密后的明文m=(L(cλmodN2)/L(gλmodN2))modN，其中L(u)=(u－1)/N。

对于明文m有：

本文Paillier同态加密利用python-paillier库（https：//python-paillier.readthedocs.io/）实现，该加密库支持浮点数的计算，因此对于实数k和明文m有(Enc(m))k=Enc(km)。

1.3 秘密共享

秘密共享就是指共享的秘密在多个计算方之间进行合理分配，以达到由所有参与方共同掌管秘密的目的。Sharmir在1979年最早提出t-out-of-n秘密共享方案[28]，允许将秘密s进行分割并在n个参与者中共享，使得至少任意t个参与者合作才能够还原秘密，而任何少于t个参与者均不可以得到秘密的任何信息。具体地，该方案由两种算法组成：共享算法Share(·)和重构算法Recon(·)，算法描述如下：

（1）Share(s,t,n)→(s1,s2,…,sn)：给定秘密s、阈值t以及共享份额数n,可以产生一组秘密共享值{s1,s2,…,sn}。

（2）Recon(Θ,t)→s：给定秘密共享值的子集Θ，其中Θ∈{s1,s2,…,sn}且 |Θ|≥t，则可以重构出原始秘密s。

本文方案涉及两方计算任务，由两个云服务器进行交互式协作计算，因此本文采用2-out-of-2 秘密共享方案。即对于秘密a，通过共享算法Share(a,2,2)→(a0,a1)得到其对应的两个共享值ai(i=0,1)；反之，由秘密共享值ai(i=0,1)恢复出原始秘密a的过程就叫作Recon({a0,a1},2)→a。其中a=a0＋a1。

2 系统模型

本文采用诚实且好奇的非共谋双云服务器模型，即云服务器诚实地执行预置的计算任务，同时出于好奇会查看并记录数据信息，但不会向另一方透露任何自己的输入、中间计算参数以及输出信息。如图1 所示，本文系统模型包含一个数据提供者（Data Provider）、一个用户（User）和两个云服务器（Cloud Server，CS）。数据拥有者发布线性回归模型的训练任务并提供必要的训练数据，在与云服务器CSi(i=0,1)建立基于TSL/SSL协议的安全信道并进行模型训练任务协商之后，利用秘密共享原理将训练数据分发给它们，由两个云服务器协作完成训练任务；在预测阶段，具有预测请求的用户在与服务器建立安全信道之后，将待预测数据通过秘密共享的方式分发给它们，两个云服务器进行协作预测，并将各自的预测值返还给用户，由用户重构出最终的预测结果。

图1 系统模型Fig.1 System model

3 本文方案

本章主要描述基于安全两方计算的隐私保护线性回归方案，包括秘密共享值的乘法计算以及基于两方计算的线性回归安全训练和预测阶段。其中秘密共享值的乘法计算（Multiplication of Secret Shared Values，MoSSV）协议作为训练及预测阶段的基础协议，主要用于双云服务器的安全两方计算。如图2所示，训练阶段和预测阶段分别由三个主要模块构成。在训练阶段，鉴于数据需要脱离数据提供者本地，但又不能向云服务器泄露任何数据信息，因此首先通过Share(·)算法将数据以秘密共享的方式进行划分；收到秘密共享数据之后，两个云服务器共同协商并预置相同的训练参数，即学习率、小批量样本数目、最大迭代次数及损失阈值；最后由两个云服务器执行安全的小批量梯度下降算法进行模型参数更新，直至模型收敛。在预测阶段，同样出于保护预测数据的隐私，首先将预测数据通过秘密共享Share(·)算法分发给双云服务器；之后由双云服务器执行CalPred(·)模块，得到预测结果的秘密共享值；最后由用户执行Recon(·)算法重构最终的预测结果。

图2 隐私保护线性回归方案框架图Fig.2 Framework of privacy protection linear regression

3.1 秘密共享值的乘法计算协议

假设两个计算方分别持有给定矩阵和向量的秘密共享值，那么如何在保证计算方各自的秘密共享值不被泄露的情况下，安全地完成秘密共享值之间的乘法运算呢?Du等人[29]在仅有两个计算方参与的情形下，基于OT协议提出了一系列解决分布式线性代数问题的方案。由于OT 协议通信复杂度较高，陈莉等人[30]基于同态加密的性质设计了用于求解分布式线性方程组问题的安全两方计算协议。基于文献[30]，本文利用加法同态加密和加法掩码实现了适用于线性回归任务中秘密共享值的乘法计算协议（MoSSV），其核心思想是在仅有两个计算方参与的情况下，利用加法同态加密保护其中一个计算方的私有信息，利用加法掩码掩盖另一计算方的私有信息，最终计算双方获得矩阵-向量乘积的秘密共享值。下面给出了协议执行过程的详细描述，协议执行过程如图3所示。

图3 秘密共享值的乘法计算协议流程图Fig.3 Flowchart of multiplication calculation protocol for secret shared values

3.1.1 问题描述

秘密共享值的乘法计算问题可以描述为：对于给定的矩阵M和向量v（其中M的第二维度与v的第一维度一致），Mi和vi(i=0,1)是它们的秘密共享份额且分别为计算方Pi(i=0,1)所拥有，其中M=M0＋M1，v=v0＋v1，即计算方P0拥有私有矩阵M0和私有向量v0，另一计算方P1拥有私有矩阵M1和私有向量v1。执行该协议之后，Pi(i=0,1)可以获得乘积Mv的秘密共享份额pi=Multi(M0,M1,v0,v1)。

3.1.2 秘密共享值的乘法计算协议

输入：P0的私有矩阵M0和私有向量v0，P1的私有矩阵M1和私有向量v1。

输出：Pi(i=0,1)可得到pi=Multi(M0,M1,v0,v1)。

协议过程描述：

步骤1Pi各自生成同态加密密钥对(pki,ski)，其中pki和ski分别表示Pi的公钥和私钥，并将公钥pki发给对方。

步骤2Pi使用自己的公钥pki加密私有向量vi并将Encpki(vi)发给对方。

步骤3P1－i收到对方公钥pki和加密向量Encpki(vi)后，随机生成向量r1－i，并使用对方的公钥pki加密得到Encpki(r1－i)。

步骤4P1－i计算Encpki(M1－ivi－r1－i)并将结果发给对方。

步骤5Pi收到Encpki(M1－ivi－r1－i)后，使用自己的私钥ski解密得到M1－ivi－r1－i。

步骤6Pi计算得到pi=Mivi ＋(M1－ivi－r1－i)＋ri,协议结束。

3.1.3 正确性

对于任意两个秘密a、b，要求在避免使用可信第三方且不泄露a、b值的情况下求c=a ＋b。通过随机数r，可以进行以下构造：a′=a－r，b′=b ＋r。因为随机数可以相抵消，所以有c=a′＋b′=(a－r)＋(b ＋r)=a ＋b。

根据以上原理，对于MoSSV协议，有：

因此该协议是正确的。

3.1.4 安全性

在MoSSV协议执行之前，计算方Pi(i=0,1)之间通过协商建立基于TSL/SSL协议的安全通道，以确保他们之间发送的任何敏感数据的安全性及完整性。该协议利用加法同态加密和加法掩码的性质保护计算双方的私有信息，其安全性主要体现在协议计算过程步骤2～步骤4 中。在步骤2 中计算方Pi利用加法同态加密技术，使用己方公钥加密私有向量并发送给对方，因为对方不知道密文对应的私钥，所以无法解密，从而起到保护私有向量隐私性的作用；在步骤4 中，对方不能直接将加密的矩阵向量乘积发送回来，而是在步骤3利用加法掩码的原理使用随机向量将乘积进行盲化，从而起到保护对方私有矩阵信息的作用。

综上，在协议执行过程中，Pi(i=0,1)可以获得的信息如表1所示。

表1 在MoSSV协议步骤中参与方所获得的信息Table 1 Information obtained by each participant in MoSSV protocol

3.2 训练阶段

（1）Share((X,y),2,2)→((X0,y0),(X1,y1))

数据提供者将私有训练数据(X,y)，利用2-out-of-2秘密共享的原理随机拆分为与原始数据维度大小相同的两部分子数据(X0,y0)和(X1,y1)，并通过基于TSL/SSL协议建立的安全信道分发给云服务器CS0和CS1。

（2）InitPara(CS0,CS1)→(θ0,θ1,α,|B|,E)

由于在线性回归模型训练之前，参与训练模型的计算方需要共同预置一些必要的参数，以高效准确地完成回归任务。因此CSi(i=0,1)首先共同协商学习率α、小批量样本数目 |B|、最大迭代次数E，并分别初始化模型参数θi∈Rd（全0/1向量或者任意随机数）。

（3）ParaUpdate(·)→(θ0,θ1)

为了优化模型收敛速度，云服务器CSi(i=0,1)之间使用安全的小批量梯度下降（MBGD）算法，根据式（2）更新模型参数。具体子步骤如下所示：

之后，CSi根据当前更新的模型参数θi，利用MoSSV协议计算损失函数值Li并发给对方，两个云服务器根据Recon(·)重构出整个训练集的损失值，并判断模型是否收敛，若收敛，训练结束，当前CSi(i=0,1)所拥有的参数θi为线性回归模型参数的秘密共享值；否则，以上子步骤会循环执行。当模型或者训练达到最大迭代次数E时，强行停止训练。

3.3 预测阶段

（1）Share(XU,2,2)→

已知云服务器CS0和CS1分别拥有模型参数的秘密共享值θ0和θ1，具有预测任务的用户User可以利用云服务器强大的计算力进行线性预测。首先将预测数据集XU进行拆分预处理，得到两个子数据集和并分别发送给云服务器CS0和CS1。

CSi(i=0,1)利用MoSSV 协议得出预测结果的秘密共享值

CSi(i=0,1)分别将秘密共享结果发送给用户，由用户根据秘密共享值重构出真实的预测结果

4 性能评估

4.1 安全分析

本文方案实现了数据及模型参数的隐私保护，如表2 所示。本文的线性回归任务涉及两个计算方安全地执行小批量梯度下降算法，即由两个云服务器进行交互式协作计算，但因为云服务器是诚实且好奇的，对训练数据的安全存在一定的威胁，所以方案首先利用加法秘密共享将训练用的数据以适当形式拆分后分发给不同计算方。本方案中两个云服务器CS0和CS1非共谋，因此有效地避免了云服务器恢复原始数据信息的问题，实现了对训练数据的隐私保护。

表2 基于两方计算的线性回归方案对比Table 2 Comparison of linear regression schemes based on two-party computation

在参数更新过程中，涉及到两方秘密共享值需要同时使用的计算操作，比如需要在保护各自秘密共享数据以及模型参数的情况下进行安全计算。本文利用安全的MoSSV 协议，使用同态加密对各自模型参数θi进行加密处理，根据加法掩码的原理使用随机向量掩盖秘密共享数据的信息，防止对方使用私钥解密获得私有数据信息，根据表1 可知，云服务器无法获取到任何关于对方的隐私信息。判断模型收敛时，云服务器无法根据损失函数值Li恢复出对方的预测结果以及真实标签yi。预测阶段仅涉及到秘密共享数据和模型参数，其安全性分析同理。

值得注意的是，在训练阶段结束之后，若数据提供者有模型使用需求，则可以直接向云服务器请求发还模型参数的秘密共享值，并在本地使用Recon(·)重构出模型参数。因为数据提供者本身是具有模型训练任务的，所以该操作并不会涉及到模型参数私有信息的泄露问题。

4.2 性能分析

与本文最接近的方案是文献[20]和文献[22]，均属于基于安全多方计算的隐私保护方案，但它们均使用通信复杂度较高的OT协议，方案通信成本过高，因此本文避免采用OT 协议，而是使用加法同态加密和加法掩码技术，对比如表2所示。传统使用同态加密的隐私保护方案的一般做法是使用同态加密技术将原始训练数据加密处理后以密文的形式进行训练，最后将模型同态解密。这种方法虽然可以实现数据及模型的隐私保护，但是在密文数据上的训练会使得通信和计算开销呈指数级增长，因此为了平衡计算通信开销与隐私保护之间的矛盾，本文不论是在隐私保护线性回归算法的训练阶段还是预测阶段，均首先引入加法秘密共享技术，使用Share(·)算法将原始数据转换为非敏感型数据，并将拆分后的秘密共享数据直接以明文的形式分发给云服务器CS0和CS1，即通过明文传输的方法保护原始数据，而不是直接将数据进行加密处理，有效避免了用户与服务器之间的密文传输，从而既保护了原始数据的隐私，又极大降低了数据提供者（或用户）与服务器之间的通信开销。之后在模型训练ParaUpdate(·)和预测结果计算CalPred(·)模块中，借助同态加密可以对密文直接进行处理的特性，结合加法掩码技术，利用加法秘密共享值之间的加法和乘法计算特性，将模型参数更新公式进行分解，使用MoSSV协议保护计算双方的私有信息。相较于传统的同态加密方案，这种方法不需要在双云服务器之间进行多维度密文数据的传送，只需要在每一轮迭代过程发送单一维度的密文向量即可，从而不仅保护了数据和模型参数的隐私，而且大幅度降低了双云服务器之间的通信开销。

由于在不同的数据集上模型收敛的速度不同，本文仅针对一轮迭代训练过程中的时间及通信开销进行方案性能分析。在小批量梯度下降算法中，小批量样本数目 |B|以及学习率α的选择是很重要的，|B|太大或者太小都会导致训练时间过长。经过大量的实验验证，最终本文将小批量样本数目 |B|、最大迭代次数E及学习率α分别设置为10、100和0.1，并设置模型收敛条件（即损失阈值）为10－5。在本文的方案中，通信开销主要来自于ParaUpdate(·)阶段中的MoSSV 协议。ct表示一条密文大小，pt表示一条明文大小。那么在计算时，CSi(i=0,1)需要分别将向量θi和盲化的乘积向量的密文形式发给对方，因此通信开销为对于的发送，通信开销为 |B|×pt。当判断模型是否收敛时，需要计算训练集上的损失函数，计算的过程需要的通信成本，另外CSi(i=0,1) 将损失函数值Li发送给对方需要n×pt。综合以上，一轮迭代训练过程的总通信开销为文献[20]和文献[22]的通信成本主要出现在小批量梯度下降算法的执行以及OT协议中。其中文献[20]执行SGD_Linear 协议时，CSi(i=0,1)在每轮迭代过程中发送盲化之后的权重及误差向量所需要的通信成本为而使用OT协议计算乘法三元组时通信量为则每轮迭代过程所需要的总通信成本为pt。在文献[22]的线性回归算法迭代训练过程中，CSi(i=0,1)计算预测值和梯度变化量时的通信成本均为而双云服务器使用OT 协议计算乘法三元组需要通信成本为 |B|dl×pt，故每次迭代总通信成本为，其中表示比a大的最小整数，l表示数据长度。

4.3 实验结果

为了证明本文方案的有效性，对基于安全两方计算的数据隐私保护线性回归算法进行了实验验证。实验平台配置为Intel®CoreTMi5-4200M、2.50 GHz、8 GB 内存的计算机，使用Python 语言进行编程，通过两个类分别模拟数据提供者和云服务器的行为。实验数据选用Python的Scikit-learn库提供的Boston数据集和Diabetes数据集。其中Boston 数据集涉及美国人口普查局收集的美国马萨诸塞州波士顿住房价格的有关信息，包含506条样本数据，每条数据包含有13个输入变量和1个输出变量。Diabetes 数据集包含404 条医疗记录，每条记录有10 个输入变量和1 个输出变量。本文随机选取数据集的80%用于训练模型，剩余的20%用于测试模型性能，并对其进行归一化处理。

图4 展示了预测数据集真实标签值与明文域及密文域的预测值的对比曲线图。其中明文状态实验结果是指由客户端本地独自训练模型的情形，曲线图证明密文下的预测结果几乎与明文下的预测结果一致。同时，本文以均方误差（Mean-Square Error，MSE）、均方根误差（Root-Mean-Square Error，RMSE）、平均绝对误差（Mean Absolute Error，MAE）和R平方（R-Squared）作为线性回归模型的评估指标。与明文下的结果相比，本文方案几乎实现了相同的预测性能，这表明本文基于两方计算的保护数据隐私线性回归方案是可行的。如表3 所示，Boston数据集完成一轮训练平均需要157.912 s，Diabetes数据集完成一轮训练需要128.340 s。虽然密文域的训练速度与明文相比慢，但是训练一次得到的模型可以用于多次预测，因此针对注重隐私性的医疗、基因、财务等数据而言，密文域的训练是可以接受的。

表3 明文和密文下的实验结果对比Table 3 Comparison of implementation results between plaintext and ciphertext

图4 明文域及密文域预测结果与真实标签值的对比图Fig.4 Comparison of real and predicted label values in plaintext and ciphertext

5 结束语

本文提出了一种基于安全两方计算的数据隐私保护线性回归方案。为了在两方计算过程中不泄露数据、模型参数及中间参数的信息，本文利用加法同态加密和加法掩码保护两个云服务器的秘密共享值，实现了秘密共享值的乘法计算协议MoSSV。实验结果表明，本文方案在保证模型准确度的情况下，实现了数据及模型参数的隐私保护。本文提出的方案保证了训练和预测过程的高效性，并达到了较高的准确度。对于下一步的工作，计划针对逻辑回归、岭回归等回归算法的数据隐私保护问题展开研究，并在隐私回归问题的时间及通信成本方面进一步优化。