Kun Liu

Kun Liu

CS & Applied Math & MPC @ GZU | Phd

A High Performance Privacy Preserving Logistic Regression

1 minute read

Published:

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

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

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

逻辑回归

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

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

在环上的加法秘密共享，将共享值分别给Alice和Bob接受到共享$x_A$和$x_B$。两者都是上均匀随机的，且$x_A + x_B = x \mod q$。由于两个共享都是随机数，因此不会泄漏关于$x$的任何信息。秘密共享值的操作在本地计算，并不需要通信。通过组合双方共享向各方公开秘密共享值。令秘密共享，$c$是常数：

  • $z = x+ y$加法，每方本地$x, y$的共享相加，从而得到$z$的共享，
  • $z = x - y$减法，每方本地$x, y$的共享相加，从而得到$z$的共享，
  • $z = cx $常数乘，每方也是在本地计算共享，
  • $z = x + c $常数加，Alice用他的共享$x_A$和$c$相加得到$z_A$，Bob设置共享$z_B = x_B$，

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

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

定点数计算和截断

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

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

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

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

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

共享转换

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

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

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

  • 对二进制数$a, b$求和，第$i$位计算$ c_i = a_i b_i \oplus a_i c_{i-1} \oplus b_i c_{i-1}$
  • 乘法$g_i = a_i b_i$在位置$i$产生一个进位比特，异或$ p_i = a_i \oplus b_i$保留前一个进位比特。可以表示成$ s_i = p_i \oplus c_{i-1} $和$ c_i = g_i + p_i c_{i-1} $，用矩阵形式表示如下
  • 毋需计算第$ \lambda $进位，$s_\lambda$依靠$ c_{\lambda -1} $，第1位进位变成向量$(0,1)$，所有的$ c_i $可以从$M_{1,i}$的右下条目导出。
  • 在安全多方计算中，这个组合计算两次乘法，$p_{i+1}p_i$和$ p_{i+1}g_i $。在第$i$层至少需要$2^{i-1}$个组合$M_{1,j}$，可以在对数网络中时间矩阵组合。添加约束条件，即每个$M_{1,j}$来自前一层的最大矩阵$M_{1, 2^{i-2}}$的组合，余数为$ M_{2^{i-2}+1, j} $，若网络中$ M_{2^{i-2}+1, j} $不存在，则按照相同的约束集添加组合。

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

激活函数的安全计算

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

  • 判断$z^\prime = z + 0.5$是正号或者负号
  • 判断$z^\prime \ge 1$

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

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

PPLR

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

You May Also Enjoy