ABY3 定点数乘法
Published:
定点数乘法计算
定点数乘法在机器学习中出现的情况很普遍。但是由于浮点数相乘会导致小数点爆炸，影响到协议的效率，一般都会对浮点数转定点数之后进行截断。
截断方法1
为了最小化通信成本，将通过两轮交互进行乘法和截断。基本想法是在一方不参与的前提下运行两方协议，根据半诚实模型假设，最多有一方为恶意，诚实方始终是大于恶意方的数目。让双方在环上执行$(2,3)$门限共享协议，令，有，并假设$x^\prime \ll 2^k$。参与方1和2先定义$(2,3)$门限秘密共享协议$(x^\prime_1, x^\prime_2+x^\prime_3)$，两方均在本地截断秘密共享$(x^\prime_1 / 2^d, (x^\prime_2+x^\prime_3)/2^d)$。这个除法带来的误差和两方计算协议计算出来的误差一样，且拥有相同的正确性。定义结果，$r$是一个随机数，并让参与方2，3知道。 显然每方$i$都在本地计算共享分块$x_i$，并通过$(2,3)$门限秘密共享协议把$x_i$发送给$i-1$方，从而得到。这两轮都需要乘法和截断操作，假设第2方知道$x^\prime_2$ 和$x^\prime_3$，$x^\prime_3$由第3方在第一轮中计算得到，每一方都执行3-out-of-3协议得到。然后第3方发送$x^\prime_3$给第2方，第2方计算$x_2:=(x^\prime_2+x^\prime_3) / 2^d -r$，并把这个值转发给第1方。
截断方法2
通过预处理中间参数，可以减少1轮乘法。先预计算随机数，得到 ，再预处理环上的秘密值，并除以$2^d$。然后计算，根据协议广播给每一方。每一方本地计算出。然后每一方收到秘密分块并计算出。这一步是仿照两方安全计算的方案完成，计算和的最大误差是，若选择合适的和，可得到一个很大概率。通过通信一轮完成此操作和的计算。标准的秘密共享乘法需两步，一是在本地用门限方案计算，二是用$(2,3)$门限方案再次秘密共享$x$。在这两步之间，每方能转换为计算$(3,3)$门限秘密共享的。第2步可以通过广播并定义来转换。实际上，一轮通信能完成乘法和截断操作，相比于标准的共享乘法发送3条消息，此操作则需发送4条消息。方法一计算，选择通信量低的二进制秘密共享，也可以抵抗恶意敌手模型。每方无交互预计算一个随机二进制共享。移除的后$d$位在本地进行截断表示为。为了获得最终的共享，第1，2方联合取样并秘密共享值，第2，3方利用同样的方式取样并共享。每方能安全计算二进制减法电路，并发布和。最后的秘密共享被定义为和。
预处理阶段计算并截断同时进行，这不会对协议的复杂度造成影响。因此选择优化通信加法电路，而不是交互通信轮次。一般使用$k-1$个门的行波进位全加法/减法器(ripple carry adder)优化通信电路。同时，可在环下计算，每次减法则需要$k-d-1$个门操作。半诚实模型下，本地计算$r_2, r_3$的一次减法。一般地，要求三方都持有$(3,3)$门限方案的共享计算，重共享时则需把$x^\prime_i$发送给第$i-1$方$(2,3)$门限方案。但是为了证明重共享协议的正确性，需要单独交互一次证明$x^\prime_i$的正确性，把$x^\prime_i$和广播一起发送。第$i$方向第$i-1$方发送一个正确信息$(x_i,\pi_i)$，向第$i+1$方发送一个错误的广播信息$x_i - r_i$。第$i-1, i+1$方保留所有从第$i$方的消息$x_i-r_i$，并在秘密共享值披露之前比较他们是否相等，这用来确保这个协议被执行了。
在线阶段，第3步无需在第4步之前执行，可以在下一轮中进行，并在任何与输出有关的值被披露之前进行。下一步操作不显示$z$的值，这会使定点乘法协议的有效轮次复杂度为1。 加法秘密共享的特性对任意有符号的整数$c$都可以独立计算。若$x$是浮点数，只需$c$也是定点数，加减法可容易操作。对乘法和整数$c$的2的补码而言，明文的乘法自然也可以操作。当$c$为定点数时，则须使用半诚实的截断算法和恶意的截断算法将结果除以$2^d$，从而输出$d$个十进制比特共享，定点数的另外一个特性是支持常数$c$的除法，即。
浮点数乘法矩阵化
机器学习中的大部分计算都是进行矩阵乘法。矩阵乘法可以转变为一系列向量的内积，此内积对应两个相乘矩阵的对应行列。一般内积定义$\vec{x} \cdot \vec{y} := \sum^n_{i=1}x_i y_i, \vec{x}, \vec{y} \in (\mathbb{Z}_{2^k})^n$是$n$维向量。但这样的转化需要$n$次乘法协议，通信复杂度为$O(n)$，文中通过优化通信把通信量降到了$O(1)$，仅需预处理截断分段。半诚实模型下十进制乘法分两步之行，第一步是发布$(3,3)$门限方案共享，最后计算的积就是。这里出现的非线性操作是经过一系列局部变换变成计算。内积的计算变为。每方本地计算出每个 的$(3,3)$门限共享，这些共享通过求和，盲化，截断和重共享之后成为$(2,3)$门限共享的结果。这里只有一个值会被重新共享出去，好处是截断操作在内积计算中产生$2^{-d}$误差。同时误差不是单个乘法操作的误差，对训练结果的影响不大，用这种方法可以计算任何线性组合的乘法，只要算出的共享长度不超过$2^l$，每方在算出$(3,3)$门限秘密共享后进行通信交互实现重共享和截断操作。文中也指出恶意模型下的正确性证明会更复杂，通信复杂度也会到$O(n)$。这种方法是把矩阵乘法的通信发展转到了离线阶段。对于计算矩阵 相乘，两方分别选择与维数相同的随机矩阵。离线阶段，各方用标准定点数乘法协议计算乘法三元组。每方在本地计算$(3,3)$门限共享，第$i$方给第$i-1$发送本地共享$Z_i$，也通过乘法三元组向他证明的正确性。