About BLAZE Reading Note(2)

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

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

位提取

位提取协议目的是给定一个算数共享值[[v]]，让服务器计算共享值v∈Z2l 的最高有效位(MSB)的布尔共享。 一种是用文章ABY3中的方案，优化并行前缀加法器(PPA)电路，2l个与门和log(l)深度的乘法。令GC=(u1,u2,u3,u4,u5)表示一个混淆电路，输入u1,u2,u3∈Z2l,u4,u5∈{0,1}，输出时最高有效位y=msb(u1−u2−u3)⊕u4⊕u5。因此，令u1=βv,u2=[αv]1,u3=[αv]2s.t.u1−u2−u3=v。 又令u4=r1,u5=r2，其实r1,r2是(P0,P1)和(P1,P2)随机选取的比特。(P0,P1)生成混淆电路，并把电路GC，输入和解码信息对应的密钥一起发送给P2。P2在评估GC获得v=msb(v)⊕r1⊕r2，把v及其密钥的哈希值一起发送给P1。P1,P2然后联合生成[[v]]B。服务器将[[v]]B与在预处理阶段生成 [[r1]]B 和 [[r2]]B进行异或操作，从而获得最后结果。

比特算术转换

给定共享[[⋅]]，比特算术转换让服务器计算单个比特的b的算术共享。环Z2l的比特b的算术共享

可以计算算术共享(βb)A,(αb)A和它们的积(βb)A(αb)A。

• 计算(αb)A 的算术共享
  (αb)A=([αb]1⊕[αb]2)A=([αb]1)A+([αb]2)A−2([αb]1)A([αb]2)A
• P0,Pj,j∈{1,2}用([αb]j)A联合计算共享[[([αb]j)A]]，服务器用秘密共享乘法协议，在本地计算得到[[([αb]1)A([αb]2)A]]

截断算法

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

点积

点积协议是给定→x 和 →y 的[[⋅]]共享令服务器生成→x⊙→y的共享[[⋅]]。对于一个大小为n的向量→x的[[⋅]]共享，其中每个元素xi∈Z2l,i∈[n]也是一个[[⋅]]共享。若直接用乘法协议计算点积，结果可以在本地计算zi=xi⋅yi相对应的共享，使得通信量大小与n线性相关。若要减小通信量，必须使得在线阶段的通信量与n 无关。若要用 z=→x⊙→y计算βz，就要让P1,P2在本地计算[βz]=[βz1]+⋯+[βzn]并重构βz，而不是分别去重构每一个βzi。P0要结合所有的β⋆zi值并发送单个的值β⋆z给P1,P2去验证，而不是为每个zi=xi⋅yi发送一个 β⋆zi 。这需要P0计算β⋆z=∑ni=1β⋆zi，并发送相同的哈希值给P1,P2，然后P1,P2交叉验证哈希值βz−∑ni=1(βxi⋅βyi−ψi)

截断

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

含截断的点积

含截断的点积协议是给定向量→x 和 →y 的[[⋅]]共享令服务器生成z=→x⊙→y的共享[[⋅]]截断值zd，为了不增加在线阶段的通信成本，需要对ABY3的截断方法进行改进。预处理阶段，和点积协议步骤一样，生成截断对(r,rd)。在线阶段，服务器P1,P2本地计算(z−r)的[⋅]共享，此后，P1,P2进行本地截断操作(z−r)从而获取(z−r)d，并利用联合共享协议产生其[[⋅]]共享。最后，通过增加(z−r)d 和 [[rd]]，服务器可以在本地计算出z的[[⋅]]共享。为了保证计算的正确性，P0将计算(z−r)⋆，而非β⋆z

安全比较

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

实验结果

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