ABY3 定点数乘法

定点数乘法计算

定点数乘法在机器学习中出现的情况很普遍。但是由于浮点数相乘会导致小数点爆炸，影响到协议的效率，一般都会对浮点数转定点数之后进行截断。

截断方法1

为了最小化通信成本，将通过两轮交互进行乘法和截断。基本想法是在一方不参与的前提下运行两方协议，根据半诚实模型假设，最多有一方为恶意，诚实方始终是大于恶意方的数目。让双方在环\(\mathbb{Z}_{2^k}\)上执行$(2,3)$门限共享协议，令\([\![x^\prime ]\! ] := [\![ y ]\!][\![z]\!]\)，有\([\![x ]\! ] = [\![x^\prime ]\! ] / 2^d\)，并假设$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)$。这个除法带来的误差和两方计算协议计算出来的误差一样，且拥有相同的正确性。定义结果\([\![ x ]\!] := (x_1, x_2, x_3) = ((x^\prime_1 / 2^d, (x^\prime_2+x^\prime_3)/2^d)-r, r)\)，$r$是一个随机数，并让参与方2，3知道。 显然每方$i$都在本地计算共享分块$x_i$，并通过$(2,3)$门限秘密共享协议把$x_i$发送给$i-1$方，从而得到\([\![ x ]\!]\)。这两轮都需要乘法和截断操作，假设第2方知道$x^\prime_2$ 和$x^\prime_3$，$x^\prime_3$由第3方在第一轮中计算得到，每一方都执行3-out-of-3协议得到\([\![x^\prime ]\! ] := [\![ y ]\!][\![z]\!]\)。然后第3方发送$x^\prime_3$给第2方，第2方计算$x_2:=(x^\prime_2+x^\prime_3) / 2^d -r$​，并把这个值转发给第1方。

截断方法2

通过预处理中间参数，可以减少1轮乘法。先预计算随机数\(r^\prime \in \mathbb{Z}_{2^k}\)，得到 \([\![ r ]\!] = [\![r^\prime / 2^d]\!]\)，再预处理环\(\mathbb{Z}_{2^k}\)上的秘密值\([\![ x^\prime ]\!]\)，并除以$2^d$。然后计算\((x^\prime - r^\prime) / 2^d\)，根据协议广播\([\![x^\prime -r^\prime ]\!] = [\![x^\prime ]\!] - [\![r^\prime ]\!]\)给每一方。每一方本地计算出\((x^\prime - r^\prime) / 2^d\)。然后每一方收到秘密分块并计算出\([\![ \tilde{x} ]\!]:=(x^\prime - r^\prime)/2^d+[\![ r ]\!]\)。这一步是仿照两方安全计算的方案完成，计算\(\tilde{x}\)和\(x = yz / x^d, x \in \mathbb{Z}_{2^l}\)的最大误差是\(2^{-d}\)，若选择合适的\(k\)和\(l\)，可得到一个很大概率\(1-2^{-k+l}\)。通过通信一轮完成此操作和\([\![x^\prime ]\!]:= [\![ y ]\!][\![z]\!]\)的计算。标准的秘密共享乘法需两步，一是在本地用\((3,3)\)门限方案计算\([\![x^\prime ]\!]\)，二是用$(2,3)$门限方案再次秘密共享$x$。在这两步之间，每方能转换为计算$(3,3)$门限秘密共享的\([\![x^\prime -r^\prime ]\!]\)。第2步可以通过广播\([\![x^\prime -r^\prime ]\!]\)并定义\([\![ x ]\!]:=(x^\prime - r^\prime) / 2^d + [\![ r ]\!]\)来转换。实际上，一轮通信能完成乘法和截断操作，相比于标准的共享乘法发送3条消息，此操作则需发送4条消息。方法一计算\([\![ r^\prime ]\!], [\![ r ]\!] = [\![ r^\prime / 2^d ]\!]\)，选择通信量低的二进制秘密共享，也可以抵抗恶意敌手模型。每方无交互预计算一个随机二进制共享\([\![ r^\prime ]\!]^\mathsf{B}\)。移除\([\![ r^\prime ]\!]^\mathsf{B}\)的后$d$位在本地进行截断表示为\([\![ r ]\!]^\mathsf{B}\)。为了获得最终的共享\([\![ r^\prime ]\!]^\mathsf{A}, [\![ r ]\!]^\mathsf{A}\)，第1，2方联合取样并秘密共享值\(r^\prime_2,r_2 \in \mathbb{Z}_{2^k}\)，第2，3方利用同样的方式取样并共享\(r^\prime_3, r_3 \in \mathbb{Z}_{2^k}\)。每方能安全计算二进制减法电路，并发布\([\![ r^\prime_1 ]\!]^\mathsf{B} = [\![ r^\prime ]\!]^\mathsf{B} - [\![ r^\prime_2 ]\!]^\mathsf{B} - [\![ r^\prime_3 ]\!]^\mathsf{B}\)和\([\![ r_1 ]\!]^\mathsf{B} = [\![ r ]\!]^\mathsf{B} - [\![ r_2 ]\!]^\mathsf{B} - [\![ r_3 ]\!]^\mathsf{B}\)。最后的秘密共享被定义为\([\![ r^\prime ]\!]:=(r^\prime_1, r^\prime_2, r^\prime_3)\)和\([\![ r ]\!]:=(r_1, r_2, r_3)\)。

预处理阶段计算并截断同时进行，这不会对协议的复杂度造成影响。因此选择优化通信加法电路，而不是交互通信轮次。一般使用$k-1$个\(\mathtt{AND}\)门的行波进位全加法/减法器(ripple carry adder)优化通信电路。同时，\([\![ r^\prime_1 ]\!]\)可在环\(\mathbb{Z}_{2^{k-d}}\)下计算，每次减法则需要$k-d-1$个\(\mathtt{AND}\)门操作。半诚实模型下，本地计算$r_2, r_3$的一次减法。一般地，要求三方都持有$(3,3)$门限方案的共享\([\![ x^\prime ]\!]\)计算\([\![x^\prime ]\! ] = [\![ y ]\!][\![z]\!]\)，重共享时则需把$x^\prime_i$发送给第$i-1$方$(2,3)$门限方案。但是为了证明重共享协议的正确性，需要单独交互一次证明$x^\prime_i$的正确性，把$x^\prime_i$和广播\([\![x^\prime - r^\prime ]\!]\)一起发送。第$i$方向第$i-1$方发送一个正确信息$(x_i,\pi_i)$，向第$i+1$方发送一个错误的广播信息$x_i - r_i$。第$i-1, i+1$方保留所有从第$i$方的消息$x_i-r_i$，并在秘密共享值披露之前比较他们是否相等，这用来确保这个协议被执行了。

在线阶段，第3步无需在第4步之前执行，可以在下一轮中进行，并在任何与输出\(\mathbb{Z}_{2^k}\)有关的值被披露之前进行。下一步操作不显示$z$的值，这会使定点乘法协议的有效轮次复杂度为1。 加法秘密共享\([\![ x ]\!]^\mathsf{A}\)的特性对任意有符号的整数$c$都可以独立计算\([\![ x ]\!]^\mathsf{A} + c, [\![ x ]\!]^\mathsf{A} - c, c[\![ x ]\!]^\mathsf{A}\)。若$x$是浮点数，只需$c$也是定点数，加减法可容易操作。对乘法和整数$c$的2的补码而言，明文的乘法自然也可以操作。当$c$为定点数时，则须使用半诚实的截断算法和恶意的截断算法将结果除以$2^d$，从而输出$d$个十进制比特共享\([\![ cx ]\!]^\mathsf{A}\)，定点数的另外一个特性是支持常数$c$的除法，即\([\![ cx ]\!]^\mathsf{A} / c = c ^{-1} [\![ cx ]\!]^\mathsf{A}\)。

浮点数乘法矩阵化

机器学习中的大部分计算都是进行矩阵乘法。矩阵乘法可以转变为一系列向量的内积，此内积对应两个相乘矩阵的对应行列。一般内积定义$\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)$，仅需预处理截断分段\([\![r^\prime ]\! ], [\![r ]\! ]\)。半诚实模型下十进制乘法分两步之行，第一步是发布$(3,3)$门限方案共享\([\![z^\prime + r^\prime ]\! ] = [\![x ]\! ][\![y ]\! ] + [\![r^\prime ]\! ]\)，最后计算的积就是\([\![z^\prime + r^\prime ]\! ] :=(z^\prime + r^\prime)/2^d - [\![z^\prime + r ]\! ]\)。这里出现的非线性操作是经过一系列局部变换变成计算\([\![x ]\! ][\![y ]\! ]\)。内积的计算变为\([\![\vec{x} ]\! ][\![\vec{y} ]\! ] := \mathsf{reveal}((\sum^n_{i=1}[\![x_i ]\! ][\![y_i ]\! ]) + [\![r^\prime ]\! ])/2^d - [\![r ]\! ]\)。每方本地计算出每个\([\![x_i ]\! ][\![y_i ]\! ]\) 的$(3,3)$门限共享，这些共享通过求和，盲化，截断和重共享之后成为$(2,3)$门限共享的结果。这里只有一个值会被重新共享出去，好处是截断操作在内积计算中产生$2^{-d}$误差。同时误差不是单个乘法操作的误差，对训练结果的影响不大，用这种方法可以计算任何线性组合的乘法，只要算出的共享长度不超过$2^l$，每方在算出$(3,3)$门限秘密共享后进行通信交互实现重共享和截断操作。文中也指出恶意模型下\([\![x_i ]\! ][\![y_i ]\! ]\)的正确性证明会更复杂，通信复杂度也会到$O(n)$。这种方法是把矩阵乘法的通信发展转到了离线阶段。对于计算矩阵 \([\![X ]\!][\![Y ]\! ]\)相乘，两方分别选择与\([\![X ]\!], [\![Y ]\! ]\)维数相同的随机矩阵\([\![A ]\! ], [\![B ]\! ]\)。离线阶段，各方用标准定点数乘法协议计算乘法三元组\([\![C ]\! ]:=[\![A ]\! ][\![B ]\! ]\)。每方在本地计算$(3,3)$门限共享\([\![Z ]\! ]:=[\![X ]\! ][\![Y ]\! ]\)，第$i$方给第$i-1$发送本地共享$Z_i$，也通过乘法三元组\(([\![A ]\! ], [\![B ]\! ], [\![C ]\! ])\)向他证明\([\![Z ]\! ]\)的正确性。