隐私计算-多方安全计算

一、多方安全计算简介

多方安全计算（MPC：Secure Muti-Party Computation）理论是姚期智先生为解决一组互不信任的参与方之间在保护隐私信息以及没有可信第三方的前提下协同计算问题而提出的理论框架。

多方计算的目标就是对一组计算的参与者，每个参与者拥有自己的数据，并且不信任其它参与者和任何第三方，在这种前提下，如何对各自私密的数据计算出一个目标结果的过程。MPC是一种计算协议，数据持有方可以各自使用自己的数据进行训练，最终通过协议汇总结果。

MPC比较常见的落地场景就是姚期智提出的百万富翁问题。两个人各自都不希望告诉对方自己的资产，但是希望不通过第三方实现资产比较。

二、 多方安全计算

秘密共享

秘密共享(Secret-Sharing) 是现代密码学领域的一个重要分支，是信息安全和数据保密中的重要手段，也是多方安全计算和联邦学习等领域的一个基础应用技术。实际应用中，在密钥管理，数字签名，身份认证，多方安全计算，纠错码，银行网络管理以及数据安全等方面都有重要作用。

秘密共享是在一组参与者中共享秘密的技术，它主要用于保护重要信息，防止信息被丢失、被破坏、被篡改。它源于经典密码理论，最早由Sharmir和Blakley在1979年提出。简单来说，秘密共享就是指共享的秘密在一个用户群体里进行合理分配，以达到由所有成员共同掌管秘密的目的。

基于Shamir秘密共享理论的方法中，秘密共享的机制主要由秘密的分发者D、团体参与者P{P1，P2，…，Pn}、接入结构、秘密空间、分配算法、恢复算法等要素构成。

秘密共享通过把秘密进行分割，并把秘密在n个参与者中分享，使得只有多于特定t个参与者合作才可以计算出或是恢复秘密，而少于t个参与者则不可以得到有关秘密。如下图所示，特征A的值x，分割成x1，x2，……，xn，分发给S1，S2，……Sn。

三、密文乘法示例

Beaver将密文计算过程分为离线阶段与在线阶段；离线阶段即获得实际秘密之前的阶段。通过在离线阶段生成一个三元组，保证；然后让参与方与分别获得与。

然后在某个时间点，参与方分别获得了实际秘密与的分享值与。容易注意到，存在如下公式：

此时，两参与方只需分别计算如下步骤（注：步骤中为赋值运算符）：①在本地计算 ②通过一轮交互恢复出与；③在本地计算，然后进一步计算。其过程如下图所示。

容易注意到，上述步骤实质上构造出了公式中除外每一项的加法分享；通过离线阶段的乘法替代了在线阶段的乘法

c= a b

e = x-a

f = y-b

x*y = c + af + be + ef

= c + a(y-b) + b(x-a) + (x-a)(y-b)

= c + ay - ab + bx -ab + xy -bx -ay + ab

= ab + ay - ab + bx -ab + xy -bx -ay + ab

= xy

四、现有开源框架比较

MP-SPDZ - 是SPDZ-2(Keller等人，CCS’13)的分支，SPDZ是多方计算(MPC)协议SPDZ(Damgård等人，Crypto’12)的实现。MP-SPDZ将SPDZ-2扩展到了二十多种MPC协议，所有这些协议都可以用同一个基于Python的高级编程接口来使用。这大大简化了不同协议和安全模型的成本比较。这些协议涵盖了所有常用的安全模型(诚实/不诚实的多数人和半诚实/恶意模型)，以及二进制和算术电路的计算(后者的模数为素数和二次幂)。所采用的基本基元包括秘密共享、不经意传输、同态加密和混淆电路。

1. ABY - 该框架仅实现具有半诚实安全性的两方计算[DSZ15]。但是，与MP-SPDZ不同，它提供了秘密共享计算和混淆电路之间的转换。内积示例需要大约60行代码，没有注释或空行。
2. ABY3 - 该框架仅以半诚实安全性来实现三方计算[MR18]。 内积示例需要大约需要40行代码，没有注释或空行。
3. CBMC-GC - 这是将C代码编译为二进制电路描述[BHWK16]，并由ABY执行编译器。Hastings 无法执行示例代码。
4. EMP-toolkit - 框架仅在各种安全模型中实现混淆电路[WMK16]。内积示例需要大约60行代码，而没有注释或空行。
5. FRESCO - 这个框架[Ale20]只实现了不诚实多数计算，对算术电路(SPDZ和SPDZ2k )具有恶意安全，对二进制电路具有半诚实安全[DNNR17]。内积示例需要大约30行左右的代码，没有注释和空行。
6. Frigate - 这是一个编译器，它将类似C语言的代码编译成二进制的电路描述[MGC+16]。内积示例需要大约20行代码，没有注释或空行。
7. JIFF - 这个JavaScript库只实现了半诚实安全的诚实多数计算[Tea20]。与MP-SPDZ不同，它允许在离线和在线阶段之间改变安全模型。内积示例需要大约50行代码，没有注释和空行。
8. MPyC - 这个Python框架[Sch20]只实现了基于Shamir的秘密共享[Sha79]的半诚实安全的计算。内积示例需要大约20行代码，没有注释或空行。
9. Obliv-C - 这个框架通过标准C编译扩展到机器码[ZE15]。它只支持姚的乱码电路，具有半诚实的安全性。内积示例需要20行左右的代码，没有注释或空行。
10. OblivVM - 这个框架将Java的扩展编译成Java字节码[LWN+15]。它只支持Yao的乱码电路，具有半诚实的安全性。内积示例需要20行左右的代码，没有注释或空行。
11. PICCO - 这个框架通过标准C将C语言的扩展编译成本地二进制文件[ZSB13]。它只实现了基于Shamir的秘密共享的诚实多数半诚实计算。内积示例需要10行左右的代码，没有注释和空行。
12. SCALE-MAMBA - 这个框架[COS19]是SPDZ-2[KSS13，KRSS18]的另一个分叉。尽管有共同的根源，但自2018年以来，这两个分叉已经有了很大的分歧。SCALE-MAMBA只实现了素数模数（不是二的幂数）的算术计算，根据Hazay等人[HSS17]的混淆电路，以及基于秘密共享的二进制计算[FKOS15，WRK17]。所有的计算都只在恶意安全的情况下实现，不诚实多数计算模数化只使用同态加密实现。另一方面，SCALE-MAMBA对理论上可能的任何访问结构都实现了诚实多数计算。前端与MP-SPDZ中的类似，但没有后期增加的动态循环优化（6.3节）、重复代码优化（6.4节）和机器学习功能（7.3节）。此外，作者已经开始脱离Python编译器，转而使用基于Rust的新编译器。内积示例只需要不到10行代码，没有注释或空行。
13. Sharemind MPC - 这个框架实现了各种后端的前台，但它自己的后端只使用三方诚信多数半诚信计算[BLW08]。它还允许使用ABY和FRESCO作为后端，而专有的后端不能自由使用。内积示例只需要不到10行代码，没有注释和空行。
14. TinyGarble - 这个框架只实现了Yao的半诚实安全的混淆乱码电路[SHS+15]。Hastings等人无法在这个框架中运行他们所有的例子。
15. Wysteria - 这个框架实现了一个特定领域的语言，在半诚实环境下，只有二进制计算，且是不诚实大多数[RHH14]。Hastings等人无法在这个框架中运行他们所有的例子。

效率比较：