A High Performance Privacy Preserving Logistic Regression

一个存在可信第三方的两方联合训练逻辑回归隐私保护模型

在机器学习隐私保护中，根据参与方的数目和模型角色的不同具体区分方案的差别。根据服务的扮演的角色不用，含可信第三方的两方安全计算以及计算地位相等的两方机器联合学习，两者的区别在是否需要可信第三方提供机器学习中乘法所需的三元组，若由可信中心提供三元组，联合计算方的通信量则会降低，至于降低多少根据方案设计而各不相同。另外在没有可信第三方辅助下，两方需要共同协商密钥和产生共用的乘法三元组，则需要产生通信。还有一种三方安全计算，三方的计算地位相对均等，其主要的计算难点是安全性假设、秘密共享方案和乘法，若是半诚实模型，用(3,3)秘密共享；若为最多一方为腐败的恶意模型，则均需采用(2,3)和(3,3)秘密共享。

此次文章高性能的逻辑回归隐私保护方案。文章设计了两方安全计算协议，用梯度下降算法训练逻辑回归模型。新的激活函数不需要使用GC电路和密码学优化技术，实验模拟超过了七十亿次的安全乘法，可以在27秒内完成。方案假设数据由数据有单一方持有，并由拥有者分发给服务器，服务器不能处理相关的明文信息，但是这样会存在泄漏数据拥有者其他信息的风险。在这种挑战下利用安全多方计算技术保障数据的安全。一般而言，存在多个数据拥有者，他们都有训练数据不相交的部分，这样通用假设使得数据包括所有的分割数据。存在两个服务器处理训练数据并推导出模型，还假设存在一个可信第三方，分发相关随机性参数给服务器。在执行过程中假设可信中心不参与任何数据处理操作和中间参数设置。

逻辑回归

逻辑回归是很常见的二分类机器学习模型。简单描述一下，样本数据d=(xd,td)组成训练集D，其中xd=⟨xd,1,…,xd,m⟩是一个m维的向量。，每一条输入样本数据包含了m个值和d个特征值，td∈0,1是类标签分类的标准(Groud Truth)。每一个xd,i都是实数值。训练一个神经元要将xd映射到td进行正确的样本分类。神经元计算计算输入的加权总和，并让其作为激活函数的输入从而获得一个输出od=f(w0⋅xd,0+⋯+wn⋅xd,n)，这表示为标签是1的概率。在神经网络中，用一个虚拟特征xd,0扩展到输入的属性向量中，它的所有xd值都是1。原本的罗辑回归的激活函数是σ(z)=11+e−z。由于sigmoid函数需要用到指数函数进行除法和评估，安全多方计算处理这些操作十分困难，需要采用近似来拟合激活函数。使用全梯度下降计算逻辑回归模型输入样本集合，输入权重。多个数据拥有者持有用于训练的不相干的部分，合作使用安全MPC协议训练LR模型

基于安全多方计算的秘密共享

在环Zq={0,…,q−1}上的加法秘密共享，将共享值分别给Alice和Bob接受到共享xA和xB。两者都是Zq上均匀随机的，且xA+xB=xmodq。由于两个共享都是随机数，因此不会泄漏关于x的任何信息。秘密共享值的操作在本地计算，并不需要通信。通过组合双方共享向各方公开秘密共享值。令[[x]]q,[[y]]q秘密共享，c是常数：

• z=x+y加法，每方本地x,y的共享相加，从而得到z的共享，[[z]]q←[[x]]q+[[y]]q
• z=x−y减法，每方本地x,y的共享相加，从而得到z的共享，[[z]]q←[[x]]q−[[y]]q
• z=cx常数乘，每方也是在本地计算共享，[[z]]q←c[[y]]q
• z=x+c常数加，Alice用他的共享xA和c相加得到zA，Bob设置共享zB=xB，[[z]]q←[[y]]q+c

秘密共享值的安全乘法需要在两方之间通信才能完成。通常使用乘法三元组辅助安全乘法的完成，用可信第三方预分发乘法三元组给Alice和Bob。秘密共享值的安全矩阵乘法，可以具体化为标量乘法。

• 协议由Alice和Bob两方一起运行，参数，参数q，矩阵大小分别是(i,j)和(j,k)
• Alice和Bob接受到共享并确认共享是否是[[X]]q∈Zi×jq,[[Y]]q∈Zj×kq。
• 若收到双方的共享，则重构秘密X和Y，并计算Z=XY并创建秘密共享Zq分发给Alice和Bob。若两方中存在腐败方，诚实方则会验证三元组的正确性，通过均匀选择随机值创建共享。

定点数计算和截断

两方数据拥有者初始化训练数据，模q之后成为秘密共享，每个特征值x∈R用2的补码转变成一个定点数

把Q(x)转换成二进制表示，定义从右边开始a个比特位表示小数部分，接下来b个比特位表示为x的非负整数位部分，用最高有效位表示值的正负符号。λ表示总的比特数，定义q=2λ，选择一个足够大的λ能够使得LR协议中产生足够多的数x。λ至少应该有2(a+b)长，选择足够大的b能够使得x的整数部分。

将浮点数转换为定点数时，两数乘积会生成更多位的小数点。假设x,y>0，它们的定点数表示为x⋅2a和y⋅2a。两个数的成乘积是xy⋅22a。2a表示小数点的位数。需要使用截断协议把小数点直接截取到a位，这并不需两方通信，双方只在本地共享上进行操作。但是这个操作会在最低有限位出现翻转错误，这个结果完全是随机的，概率为2a+1−λ。阶段在LR模型中需要调用两次，

• 在训练数据时计算当前向量的点积，若发生误差，激活函数将错误带入到神经元输出中，每轮产生较小的误差
• 更新调整权重差Δwi。权重向量中的元素被新的环中的随机值替代

这使得需要选择一个合适截断精确度，使用10-12位小数点精确度，和环取64位，这样出现误差的概率为1253<p<1251。为了避免阶段带来的误差，截断只对乘积进行操作，也可以减少定点书本来带来的误差。通过交叉验证，12位的小数点精度可使得训练明文和密文之间无法区分。

共享转换

安全计算激活函数过程中，有一些步骤在Z2上计算，其它的则在Z2λ上进行。则需要在两者之间进行转换。两方计算协议执行[[x]]2λ共享[[xi]]2，这里xλ⋯x1是x的二进制表示。这种工作原理类似于行波进位加法器运算电路，原理如下，两方持有两个秘密共享之和，以及和的”XOR-sharing”之间的差作为载波矢量。

• 比特分解协议使得Alice和Bob输入x的λ比特长的共享值，加法共享[[x]]2λ∈Z2λ转换成加法二进制共享 [[xi]]2∈Z2 使得 x=xλ⋯x1。
• 一旦接受到Alice和Bob的共享[[x]]2λ记录共享，然后忽略任何来自该方的任何消息，并告知对方收到的消息
• 协议在收到双方输入之后，重构秘密共享x=xλ⋯x1，把x∈1,⋯,λ分发比特xi新共享[[xi]]2。若出现腐败方，将输出的共享固定为任意值，根据加法共享的正确性限制下，选择均匀随机值为诚实方的共享。

为了提高比特分解的协议的通信效率，可以通过一些优化措施。将比特分解协议实现加法器，输入大模数的环Z2λ的秘密共享[[xi]]2λ，输出异或形式的共享[[x1]]2,…,[[xλ]]2。各方将 Z2λ的共享，表示为xi，异或共享表示为[[xi,1]]2,…,[[xi,λ]]2，并作为加法器的输入。然后，加法器计算出进位向量(carry vector)，表示二进制加法的翻转。把此向量添加到按位共享中 [[x1,j]]2,…,[[x2,j]]2 解决 [[x1,1]]2…[[x1,λ]]2⊕[[x2,1]]2…[[x2,λ]]2 和分解秘密x。行波进位加法操作进位向量的通信复杂度是线性的。实现加法器每一层的下一进位计算两次，对于前一进位0和1的情况各计算一次。该协议通信⌈log(λ)⌉+2次，总共需要传输4λ⌈log(λ)⌉+6λ比特。

• 对二进制数a,b求和，第i位计算ci=aibi⊕aici−1⊕bici−1
• 乘法gi=aibi在位置i产生一个进位比特，异或pi=ai⊕bi保留前一个进位比特。可以表示成si=pi⊕ci−1和ci=gi+pici−1，用矩阵形式表示如下 [ci1]=[pigi01][ci−11]=[pigi01][pi−1gi−101]=MiMi−1[ci−21]
• 毋需计算第λ进位，sλ依靠cλ−1，第1位进位变成向量(0,1)，所有的ci可以从M1,i的右下条目导出。
• 在安全多方计算中，这个组合计算两次乘法，pi+1pi和pi+1gi。在第i层至少需要2i−1个组合M1,j，可以在对数网络中时间矩阵组合。添加约束条件，即每个M1,j来自前一层的最大矩阵M1,2i−2的组合，余数为M2i−2+1,j，若网络中M2i−2+1,j不存在，则按照相同的约束集添加组合。

[pi+1gi+101][pigi01]=[pi+1pipi+1gi+gi+101]

另外也需要将二进制共享和算术共享，将λ长的比特串安全的转变成算术共享。

激活函数的安全计算

逻辑回归的激活函数需要进行简化之后成为了分段函数，需要对LR的激活函数的输入在z,0.5,−0.5之间执行安全比较协议。为了避免比较协议的高通信消耗，可以通过检查共享的符号来确定：

• 判断z′=z+0.5是正号或者负号
• 判断z′≥1

通过以上就把比较协议变成了判断z′的最高有效位MSB，若MSB为1，z′为负，若MSB为0，z′为正。在λ位的共享中，最低a位表示小数部分，剩余的λ−a−b位表示整数和MSB表示符号。因此只需要执行(a+b+1)部分比特分解判断z′是否时正数或负数。

• 若z′是负数，则协议输出为0
• 若z′是正数，则需要确定z′≥1，这确实协议输出是1，还是z′。要判断z′≥1，当且仅当z′表示整数部分对应的b个比特位中至少有一个是1，故需要分析b个比特位。
• 下面协议的AND运算对应了Z2的乘法，利用德摩根律OR操作等于AND门和非门。
• 协议正确性，若z>1/2，则pos=1,gep1=1；若−1/2≤z<1/2，则pos=1,gep1=0；若z<−1/2，则pos=0，输出零的秘密共享。

PPLR

• Step1，TI将乘法三元组发给服务器，这部分随机数是离线部分操作，和数据处理无关
• Step2，数据拥有者预处理训练数据，并转换成定点数，然后将其随机分为两个秘密共享发给两个服务器
• Step3，服务器接受数据用手的数据共享，拥有训练集的([[xd]],[[td]])，预先商量并公开学习率η以及迭代次数n
• Step4，服务器训练LR模型，遵循协议执行
• Step5，两个服务器各自拥有训练模型参数的共享份额[[wi]]，并将各自的份额用秘密共享协议发给对方，双方通过重构两个共享得到最后的模型