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的向量测试吞吐量，另外还有关于点积计算在隐私保护线性和逻辑回归中提高的性能，主要影响因素有前后向传播网络、随机梯度下降批量大小等。