如何更安全地进行三方计算？

安全多方计算（MPC:Secure Muti-Party Computation）研究起源于图灵奖获得者、中国科学院院士姚期智教授的百万富翁问题：两个百万富翁如何在不想向对方泄露自己的财富值的前提下，知道谁更富有？随后姚期智教授提出著名的Garbled Circuit 协议，开创了MPC的先河。

通俗来讲，MPC可以使多个数据持有方合作完成某个计算，同时不泄露关于计算结果之外的任何信息，因而可以达成“数据可用不可见”的效果。我们可以基于MPC搭建多方联合训练、推理、数据分析等应用。

在姚院士开创MPC的先河之后，经过数十年的研究，MPC已发展出多条技术路线，大体可分为基于Garbled Circucit（GC）和基于Secret Sharing（SS）的两种技术流派。一般而言，基于GC的方案通信量相对较高，而基于SS的方法通信量相对较低。业务中使用的也是基于SS的方案居多。

其中，在honest-majority模型下的SS方案又具有最高的效率（honest-majority指的是攻击者能控制的参与方数量小于一半。换句话说，如果有三个参与方，我们假设任意两个参与方不会合谋来危害第三方），因此有着相当广泛的应用场景。如Facebook的Crypten、我们之前与隐语联合发布的密态大模型PUMA等应用均属于honest-majority模型下的三方SS方案。

Tip：什么是MPC中的“电路”

当将MPC/ZKP等密码学技术运用到具体的场景中时，需要先将待计算的任务转化为密码学角度的输入形式，称为“电路”，一般包括算术电路和布尔电路。算术电路由加法和乘法组成，适用于处理计算中的线性部分（如矩阵乘法），而布尔电路由AND、XOR等二进制门组成，适用于处理计算中的非线性部分（如Relu、Max Pooling、batchnorm、截断等）。在机器学习等应用中，非线性部分的代价往往较高，因而本文先集中讨论布尔电路。

MPC方案的安全性

MPC方案的安全性也有高低之分。流行的安全模型主要可分为半诚实模型和恶意模型两种：半诚实模型是指各个参与方都会诚实地执行该做的事，因此只需要保证默认情况下大家互相传输的信息内容不会泄露隐私即可；而恶意模型是指参与方可能会任意篡改正常执行的内容，因此方案必须包含“异常检测”能力，确保参与方如果发现这种篡改，能够自动报错中止（abort），无论遇到何种意外情形均不会泄露隐私。

容易看出，恶意模型的安全性更高，但是设计满足恶意模型要求的MPC方案是非常困难的，其原因可以理解为：因为这是一个MPC方案，即对方传过来的所有的信息都是“加密”的，无法直接查看内容，因此检测这个“加密”信息是否被篡改过是非常困难的。并且“检测”这个动作本身也要求不能泄露隐私，这使得方案的设计难上加难，通常都会带来相当大的通信量和计算量开销。鉴于这一难题，目前工业界实用的方案基本上都做不到恶意模型，只能实现半诚实模型。

学术界已有的解决方案

学术界已有的恶意模型+布尔电路+三方计算+honest-majority+SS的方案，主要可以分为以下两类：
（1）基于Beaver Triple的技术（如FLNW17等）。这种方案的主要思想是假设已经有一些正确的计算结果（Beaver Triple），可以使用这些已知的结果作为标杆去检测后续的计算结果，如果检测通过就说明被检测的计算没有被篡改。这里就有一个鸡生蛋还是蛋生鸡的问题：最开始的正确结果哪里来？这可以通过cut and choose技术来实现，也就是先实现一些随机数的计算，然后“抽查”一部分，如果抽查的是正确的，那么由于概率学原理，我们相信剩下的也大概率是正确的。这种“抽查”并不会影响安全性，因为检测的是随机数而已，和实际的数据无关。

这类技术的主要优势是计算简单：只是相当于多运行几次乘法而已。缺陷是抽查后的计算结果丧失了随机性，后续只能使用没被抽查的结果，因此会浪费很多通信量。例如在FLNW17中每方计算1个AND门需要通信10个bits；对比之下，半诚实模型如ABY3，算一个AND门只需要1个bit。

（2）基于分布式零知识证明（Distributed Zero-knowledge Proof，Dzkp）的技术（如BGIN19等）。这类技术需要发送方运行一个零知识证明zkp，证明自己正确运行了乘法协议。这里的zkp比较特殊：数据是分散在三个参与方手中，因此某个参与方给出的证明是需要另外两个参与方合作才能验证，单方是无法验证的，因此称为Dzkp。

使用Dzkp验证乘法的正确性的优势是通信量低：因为多个乘法的证明可以被压缩为一个简短的证明，摊下来的通信量实际上和半诚实方案几乎保持不变；劣势是计算量较大；zkp中需要大量的多项式插值等操作。尤其对于布尔电路而言，我们不能直接在{0,1}数据进行插值，必须将其扩展到较大的扩域才能保障zkp较低的soundness error，这进一步提高了计算代价。

一图概括，当前已有的两类方案各有优劣，难于两全其美。有没有可能设计一个在通信开销和计算开销上都比较优的解决方案呢？

通信量

计算量

triple类技术(FLNW17)

高（需要cut and choose)

低

dzkp类技术(BGIN19)

低

高（需要扩域多项式计算）

我们的思路与结果

蚂蚁技术研究院与清华大学合作发表于USENIX Security 2023的论文《Efficient3PC for Binary Circuits with Application to Maliciously-Secure DNN Inference》就是针对这一问题提出了创新的解决方案，在通信量和计算量两方面都取得了较优的结果。

本文的核心思想是基于dzkp技术路线的改进：我们尝试沿着Dzkp的路线进行思考并注意到相比于二进制扩展域，同等大小的素数域尤其是梅森素域往往具有更优性能（梅森素域是一种特殊有限域，其模数形如p＝2n-1这种特殊的性质使其在进行算术运算时可以利用CPU天然支持2幂次计算的特性，具有高效的效率）。因此，我们自然而然地想到，能否把二进制上的等式关系转化到梅森素数域上进行证明？

最后我们成功设计出了比较高效的转化方案，利用素数域的代数结构特点对算法进行了充分的优化，并基于MP-SPDZ框架实现了本方案，与BGIN19和FLNW17协议进行了对比。实验结果表明，与BGIN19协议相比，我们协议的计算开销可以降低3.5倍，通信量基本相同；与FLNW17协议相比，我们协议的通信开销可以降低9倍，计算开销基本相同。因此可以说，我们的协议将这两个维度的最优结合到了一起。此后，我们把协议用在神经网络中的布尔电路部分，对ResNet50、DenseNet和SqueezNet都进行了测试，结果显示，我们的协议可以将这些网络中非线性函数的耗时降低60%~90%之多。感兴趣的小伙伴们可以查看下方链接。

论文链接：https://www.usenix.org/system/files/usenixsecurity23-li-yun.pdf

开源代码：https://github.com/AntCPLab/malicious_3pc_binary

参考文献：

[BGIN19]: Elette Boyle, Niv Gilboa, Yuval Ishai, and Ariel Nof. Practical fully secure three-party computation via sublinear distributed zero-knowledge proofs. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 869–886, 2019.

[FLNW17]: Jun Furukawa, Yehuda Lindell, Ariel Nof, and Or Weinstein. High-throughput secure three-party computation for malicious adversaries and an honest majority. In Annual international conference on the theory and applications of cryptographic techniques, pages 225–255. Springer, 2017.