About BLAZE Reading Note(2)

三方安全计算的机器学习方案位提取协议。

和许多隐私保护机器学习方案一样，BLAZE也需要进行位提取，比特到二进制转换和截断操作。

位提取

位提取协议目的是给定一个算数共享值$[\![ v ]\!]$，让服务器计算共享值$v \in \mathbb{Z}_{2^l}$ 的最高有效位(MSB)的布尔共享。 一种是用文章ABY3中的方案，优化并行前缀加法器(PPA)电路，$2l$个与门和$\log(l)$深度的乘法。令$\text{GC} = (\mathsf{u}_1, \mathsf{u}_2, \mathsf{u}_3, \mathsf{u}_4, \mathsf{u}_5)$表示一个混淆电路，输入$\mathsf{u}_1, \mathsf{u}_2, \mathsf{u}_3 \in \mathbb{Z}_{2^l}, \; \mathsf{u}_4, \mathsf{u}_5 \in \{0, 1 \}$，输出时最高有效位$\mathsf{y} = \mathsf{msb}(\mathsf{u}_1 - \mathsf{u}_2 - \mathsf{u}_3) \oplus \mathsf{u}_4 \oplus \mathsf{u}_5$。因此，令$\mathsf{u}_1 = \beta_{\mathsf{v}}, \mathsf{u}_2 = [ \alpha_{\mathsf{v}} ]_1, \mathsf{u}_3 = [ \alpha_{\mathsf{v}} ]_2 \; \text{s.t.} \; \mathsf{u}_1 - \mathsf{u}_2 - \mathsf{u}_3 = \mathsf{v}$。 又令$\mathsf{u}_4 = \mathsf{r}_1, \mathsf{u}_5 = \mathsf{r}_2$，其实$\mathsf{r}_1, \mathsf{r}_2$是$(P_0, P_1)$和$(P_1, P_2)$随机选取的比特。$(P_0, P_1)$生成混淆电路，并把电路$GC$，输入和解码信息对应的密钥一起发送给$P_2$。$P_2$在评估$GC$获得$\mathsf{v} = \mathsf{msb}(\mathsf{v}) \oplus \mathsf{r}_1 \oplus \mathsf{r}_2$，把$\mathsf{v}$及其密钥的哈希值一起发送给$P_1$。$P_1,P_2$然后联合生成$[\![ \mathsf{v} ]\!]^{\text{B}}$。服务器将$[\![ \mathsf{v} ]\!]^{\text{B}}$与在预处理阶段生成 $[\![ \mathsf{r}_1 ]\!]^{\text{B}}$ 和 $[\![ \mathsf{r}_2 ]\!]^{\text{B}}$进行异或操作，从而获得最后结果。

比特算术转换

给定共享$[\![ \cdot ]\!]$，比特算术转换让服务器计算单个比特的$\mathsf{b}$的算术共享。环$\mathbb{Z}_{2^l}$的比特$\mathsf{b}$的算术共享

可以计算算术共享$(\beta_{\mathsf{b}})^{\text{A}}, (\alpha_{\mathsf{b}})^{\text{A}}$和它们的积$(\beta_{\mathsf{b}})^{\text{A}}(\alpha_{\mathsf{b}})^{\text{A}}$。

• 计算$(\alpha_{\mathsf{b}})^{\text{A}}$ 的算术共享
  $\begin{align*} (\alpha_{\mathsf{b}})^{\text{A}} &= ([\alpha_{\mathsf{b}}]_1 \oplus [\alpha_{\mathsf{b}}]_2)^{\text{A}} \\ &= ([\alpha_{\mathsf{b}}]_1)^{\text{A}} + ([\alpha_{\mathsf{b}}]_2)^{\text{A}} - 2 ([\alpha_{\mathsf{b}}]_1)^{\text{A}}([\alpha_{\mathsf{b}}]_2)^{\text{A}} \end{align*}$
• $P_0, P_j, j \in \{1,2\}$用$([\alpha_{\mathsf{b}}]_j)^{\text{A}}$联合计算共享$[\![ ([\alpha_{\mathsf{b}}]_j)^{\text{A}} ]\!]$，服务器用秘密共享乘法协议，在本地计算得到$[\![ ([\alpha_{\mathsf{b}}]_1)^{\text{A}}([\alpha_{\mathsf{b}}]_2)^{\text{A}} ]\!]$

截断算法

ML里面涉及小数点的运算，一般都会采用2的补码的形式表示十进制，用最高有效位(MSB)表示正负号，小数点后保留$\text{d}$位。通常情况下选择$l=64, \text{d} = 13$，为整数部分保留50个比特位。$l$位的比特串值是$\mathbb{Z}_{2^l}$上的元素。由于$\text{d}$的取值，$\mathbb{Z}_{2^l}$上两个元素相乘会使得小数点后增加到26位。这对于许多ML算法中的乘法会出现溢出的情况。截断算法就是将上述积的形式转换成为可以计算的形式，方便ML实现任务中出现的小数点乘法情况。

点积

点积协议是给定$\vec{\mathbf{x}}$ 和 $\vec{\mathbf{y}}$ 的$[\![\cdot ]\!]$共享令服务器生成$\vec{\mathbf{x}} \odot \vec{\mathbf{y}}$的共享$[\![\cdot ]\!]$。对于一个大小为$\text{n}$的向量$\vec{\mathbf{x}}$的$[\![\cdot ]\!]$共享，其中每个元素$x_i \in \mathbb{Z}_{2^l}, \; i \in [ \mathsf{n}]$也是一个$[\![\cdot ]\!]$共享。若直接用乘法协议计算点积，结果可以在本地计算$\mathsf{z}_i = \mathsf{x}_i \cdot \mathsf{y}_i$相对应的共享，使得通信量大小与$\text{n}$线性相关。若要减小通信量，必须使得在线阶段的通信量与$\text{n}$ 无关。若要用 $\mathsf{z} =\vec{\mathbf{x}} \odot \vec{\mathbf{y}}$计算$\beta_{\mathsf{z}}$，就要让$P_1, P_2$在本地计算$[ \beta_{\mathsf{z}} ] = [ \beta_{ \mathsf{z}_1 } ] + \cdots + [ \beta_{\mathsf{z}_{\text{n}}} ]$并重构$\beta_{\mathsf{z}}$，而不是分别去重构每一个$\beta_{\mathsf{z}_{\text{i}}}$。$P_0$要结合所有的$\beta^\star_{\mathsf{z}_i}$值并发送单个的值$\beta^\star_{\mathsf{z}}$给$P_1, P_2$去验证，而不是为每个$\mathsf{z}_i = \mathsf{x}_i \cdot \mathsf{y}_i$发送一个 $\beta^\star_{\mathsf{z}_i}$ 。这需要$P_0$计算$\beta^\star_{\mathsf{z}} = \sum^{\mathsf{n}}_{i=1}\beta^\star_{\mathsf{z}_i}$，并发送相同的哈希值给$P_1, P_2$，然后$P_1, P_2$交叉验证哈希值$\beta_{\mathsf{z}} - \sum^{\mathsf{n}}_{i=1}(\beta_{\mathsf{x}_i} \cdot \beta_{\mathsf{y}_i} - \psi_i)$

截断

截断操作是服务器计算$[\![\mathsf{v} ]\!]$的截断$[\![\mathsf{v}^d ]\!]$，这使得$\mathsf{v}$的值向右移动到$\text{d}$的位置，$\text{d}$是分配给小数部分的位数。SecureML提出了两方的截断协议，两方服务器在本地截断共享。ABY3证明了上述方法不能扩展到三方中，并提出了对随机数$\mathsf{r}$的共享截断对$(\mathsf{r}, \mathsf{r}^d)$。这种方法在评估乘法门之后截断乘积，这样保留潜在截断值的概率比较高。利用ABY3的截断生成方式。对于共享$\mathsf{v}$通过公开发布$( \mathsf{v} - \mathsf{r} )$，然后截断和增加共享到$[\![\mathsf{r}^d ]\!]$，形成$\mathsf{v}$的$[\![\cdot ]\!]$共享形式。截断协议产生一对共享$([\![\mathsf{r} ]\!], [\![\mathsf{r}^d ]\!])$，ABY3中有两种阶段方法，一是高效的半诚实方案，对恶意模型却会增加通信成本，二是对恶意模型是通信高效的，对$l$比特的环需要$O(l)$通信复杂度。服务器$P_0, P_j, j \in \{1, 2\}$选取随机数$R_j \in \mathbb{Z}_{2^l}$通过截断操作获得 $R^d_j$。令$\mathsf{r} = R_1 + R_2$，服务器$P_0, P_j, j \in \{1, 2\}$在$R^d_j$上执行联合共享协议生成$\mathsf{r}^d$的$[\![\cdot ]\!]$共享。各方服务器在本地计算$[\![\mathsf{r}^d ]\!] = [\![(R_1 + R_2)^d ]\!] = [\![ R_1^d ]\!] [\![ R_2^d ]\!]$

含截断的点积

含截断的点积协议是给定向量$\vec{\mathbf{x}}$ 和 $\vec{\mathbf{y}}$ 的$[\![\cdot ]\!]$共享令服务器生成$\mathsf{z} = \vec{\mathbf{x}} \odot \vec{\mathbf{y}}$的共享$[\![\cdot ]\!]$截断值$\mathsf{z}^d$，为了不增加在线阶段的通信成本，需要对ABY3的截断方法进行改进。预处理阶段，和点积协议步骤一样，生成截断对$(\mathsf{r}, \mathsf{r}^d)$。在线阶段，服务器$P_1, P_2$本地计算$(\mathsf{z} - \mathsf{r})$的$[\cdot]$共享，此后，$P_1, P_2$进行本地截断操作$(\mathsf{z} - \mathsf{r})$从而获取$(\mathsf{z} - \mathsf{r})^d$，并利用联合共享协议产生其$[\![\cdot ]\!]$共享。最后，通过增加$(\mathsf{z} - \mathsf{r})^d$ 和 $[\![\mathsf{r}^d ]\!]$，服务器可以在本地计算出$\mathsf{z}$的$[\![\cdot ]\!]$共享。为了保证计算的正确性，$P_0$将计算$(\mathsf{z} - \mathsf{r})^\star$，而非$\beta_{\mathsf{z}}^\star$

安全比较

给定$x, y \in \mathbb{Z}_{2^l}$的$[\![\cdot ]\!]$共享，安全比较计算旨在检查$x < y$。在定点数算术计算中，可以通过检测存储$v = x - y$的最高有效位(MSB)确定。根据这个思想，服务器本地计算$[\![v ]\!] = [\![x ]\!] - [\![y ]\!]$，然后用位提取协议得到$[\![v ]\!]$ 的MSB，然后通过上述的比特算术转换协议得到算术共享结果。

实验结果

文章定义吞吐量是分预处理和在线阶段计算每分钟执行的点积数，文章主要和ABY3一文进行比较，在长度从100到1000的向量测试吞吐量，另外还有关于点积计算在隐私保护线性和逻辑回归中提高的性能，主要影响因素有前后向传播网络、随机梯度下降批量大小等。