MOTION-混合协议的多方计算框架
本次介绍的是Braun等人发表在TOPS'22上的MOTION。论文链接如下：[https://eprint.iacr.org/2020/1137]。之前的 ABY 和 ABY2.0 实现了在两方下的三种秘密分享（Arithmetic-Sharing，Boolean-Sharing 和 Yao's-Sharing）的转化，在MOTION中，Braun等人实现了面向多方下dishonest majority场景的三种秘密分享的转化，并提出了一些协议和实现优化来提升性能，和之前的方案的对比见表1。
大致上，MOTION做了如下主要工作：
MOTION使用面向多方的GMW协议的Arithmetic和Boolean变体实现A-Sharing和B-Sharing，而对于多方的Y-Sharing，则使用BMR协议； 进一步，MOTION实现了A/B/Y三种秘密分享的转化； 而对于底层的Beaver Triples (MTs) 生成等基础协议，则使用基于OT的方式来实现。
本次，我们将介绍的重点放在三种技术的介绍和协议层面的优化。对于实现层面的优化，则不会过多的涉及。
1. MPC Building Blocks
本文用到的notations都是MPC方案中常见的表达形式，在这里不做过多的展开。我们从原文的Section 5 MPC Building Blocks部分直接开始。
1.1 Oblivious Transfer (OT)
本文利用OT构造底层的基本模块，使用OT Extension来提升性能。并且，本文还使用了Random-OT和C-OT来加速MTs的生成和乘法的计算。关于OT的上述相关知识详见知乎不经意传输(OT)-总结。这里，我们介绍一下本文提出的对C-OT的优化：Braun等人发现，在C-OT中，虽然根据的修正比特，的传输消息的计算方式不一样，但是两种计算的结果却是一样的。为了方便描述C-OT的预计算过程，此处作者用R-OT进行描述。具体来说：
双方首先计算R-OT，其中的选择比特是 ； 对于的实际输入 ，如果 ， 令 ，否则 。并将 发送给 ; 获得 之后，如果 则调换自己两条信息的位置，否则位置不变。进而发送消息给对方。
但是在C-OT中，在 两种情况下发送的消息是完全一样的：
因此，双方可以独立并行传输自己的消息给对方，从而减少一半的延迟。
1.2 Beaver Triples
Beaver MTs 能够用在A-Sharing和B-Sharing中用来计算乘法/AND门。下面我们以A-Sharing下的A-MTs为例进行介绍。多方场景下，每一个参与方本地生成两个随机的分享 和 ，进而多方计算生成 。因为
在本地计算 ，然后和两方计算 ()。两方基于C-OT实现，其中, 。在第次COT：
作为发送方输入 ，得到； 作为接收方，输入比特，得到，其中表示对进行分解之后得到的比特向量； 最终，令 ，令 ，从而使得 。
由于模约减，可以在COT中通过舍弃高k比特的方式减少一半的通信量。一共需要两轮通信，总通信量为 比特。
对于B-MTs，处理方法和A-MTs类似。总通信量为 比特，一共需要两轮通信。
1.3. Square Pairs (SPs)
SPs是指秘密分享下的 ，满足 。其生成方法和MTs类似，除了我们只需要任意两方做一次乘法，因此通信量是生成MTs的一半，通信轮数也是2轮。
1.4. Shared Bits (SBs)
SBs指，其中。给定，可以通过 来计算。我们基于DET+17中的协议 生成SBs。我们利用实现 的转化。生成SBs需要3轮通信，通信量为。
1.5. Extended Shared Bits (ESBs)
进一步，ESBs指，其中 , 。生成ESBs的方法有两种：
基于SBs：首先生成个SBs： 其中。这样一来可以令，。如果要得到 ，则需要对 进行 转化。 基于加法电路：在该方法下，首先令本地生成随机，从而构成。然后每一方将自己的 进行B-或者Y-Sharing，进而计算个布尔电路下的加法得到 或者 。进行布尔加法时，不同的电路通信量和通信开销不同，一般常用的有RCA、PPA。
各个子模块的具体开销见表4。
1.6. Other Ooptimizations
本文还使用如下方法进行优化：
Fixed-Key AES做哈希函数和伪随机函数； 在N方下，多个参与方如果要互相公开share，并在本地进行share的累加，在半诚实敌手下则可以通过指定一方做累加，然后将累加结果公布给所有参与方，从而将通信从降低到比特，但是增加了一轮交互。
2. MPC Protocols
在本章节，我们介绍A-, B-, Y-Sharing三种秘密分享各自的计算协议。
2.1 A-Sharing
给定，将分享为 。具体来说，拥有的可以1）在本地生成份额然后发给其他方，2）也可以使用伪随机函数实现0通信。秘密恢复则是需要得到所有份额然后恢复。对于线性操作（包括加法和明文密文乘法），可以类似两方计算不需要交互就、本地计算得到结果。而乘法则需要消耗一个MTs，通过交互得到。具体来说：
令 表示 MTs，满足; 为了计算 ，各方本地计算 和 ，并恢复 ； 最后，各方在本地计算 。
在恢复的时候，可以采用Sec 1.6 中提到的第二种优化减少通信量（但是增加了轮数）。
平方计算可以利用SPs通过类似的方法得到：，其中 ，是SPs()。
2.2 B-Sharing
对于B-Sharing， A-Sharing下的加法和乘法替换为和操作，计算方法在比特级别。算法原理类似。
More Efficient AND Gates without MTs: 本文利用优化的COT提出了一种不需要MTs的更加高效的乘法，简单来说是利用COT直接计算AND门下的交叉比特操作。该方法和基于MTs的方法相比，通信量：预计算节省了4比特，在线计算相同；通信轮数，在线计算相同，预计算提升了。
2.3 Y-Sharing
多方下的混乱电路协议是BMR协议，该方法的基本思想是多方在预计算交互，构造混乱电路。然后在线计算阶段只需要本地计算即可。和两方计算不同，BMR中任意一方都不能拥有构造混乱表的全部的keys明文。
Setup:在混乱电路构造阶段，每一个参与方本地生成global key offset ，随机置换比特的分享（），针对输入线两种可能值的两个keys ：
如果提供实际输入，那么当时，有；否则，； 如果对应公开值， ($i=1,...,N)； 如果不是XOR门的输出，那么且；如果是XOR的输出且输是，那么且。两种情况下，都有 。
的garbling过程如下：对于每一个AND门，对于输入线，混乱表项计算如下：
对于所有的和，其输出。MOTION使用OT实现底层的计算：
多方使用1比特的COT计算得到，从而获得share； 进而，每一方本地计算，该计算可以令本地计算。对于和计算类似； 第三步，多方调用-比特的COT计算得到对于和。记该步的结果为； 如此一来，最后的混乱表中，持有的表项可以构造如下： 广播 ； 广播 。 上述广播的消息做XOR即可得到。另外一种优化方法则是通过计算
得到 , 可以不用计算。
Online: 在线计算阶段，任意参与方持有（其中是实际输入），keys () 和 分享 。表示为
在线阶段，秘密拥有者首先广播；然后每一方广播。给定 和 ，可以利用free-XOR技术本地计算XOR：
;
AND门则需要解密得到，通过对比 推断的值。其余的优化可以参考原文。
上述各部分的开销如下：
3. MPC Conversions
本章节介绍A/B/Y三种协议多方下的转化：
3.1 B2Y
最直观的方法是利用Y-Sharing的分享方法直接分享然后在Y-Sharing下做XOR。本文提出了对于通信量的优化方案：
广播； 计算，并广播； 令
不难验证，。如此，通行量提升了。
3.2 Y2B
和2PC下一样Y2B也是free的：因为。由于是公开的，是B-Sharing的，令计算， ()设置即可得到。
3.3 B2A
Straightforward: Additive Masking: 该方法直接利用ESBs：，计算：
； ;
但是该方法需要在B-Sharing做减法电路，需要通信轮数。
Optimized: Using Shared Bits: 该方法对于每一比特利一个SBs，将每一比特转化为A-Sharing之后，再本地加权求和即可。通信轮数降低为1。
3.4 A2Y
比较直观的方法是每一方将自己的share重新分享为Y-Sharing，然后在Y-Sharing下做次加法。本文的优化方法是利用ESBs ，计算如下：
； ； 。上述方法只需要一次加法电路。
3.5 A2B
两种方法实现A2B：1）使用加法电路直接将在布尔电路下做加法，通信轮数为；2）先做A2Y，然后做Y2B（free）。
3.6 Y2A
简单是方法是先做Y2B，然后做B2A。但是该方法需要一轮在线通信。本文的优化方法可以利用ESBs ：
; ; 。根据BMR的特性，上述Step 1 & 2 不需要在线通信，而A-Sharing下的加法也不要通信。因此，该方法不需要在线通信。
各协议的复杂度如下：
4. Experiments
本文做了一系列实验，和ABY，MP-SPDZ等协议对比，验证了子协议和整个系统的性能提升。列举几项如下：
译者简介
董业， 本科毕业于山东大学计算机科学与技术专业，目前在中国科学院信息工程研究所攻读博士学位。主要研究兴趣包括隐私保护、安全多方计算、同态加密和机器学习。知乎：酸菜鱼。
往期推荐：
一个好用的多方隐私求交算法库MultipartyPSI-Pro
Secret-shared Shuffle—秘密共享下的洗牌协议
欢迎投稿
邮箱：pet@openmpc.com
参与更多讨论，请添加小编微信加入交流群