多方安全计算MPC

1.多方安全计算的价值

MPC是密码学的一个重要分支，旨在解决一组互不信任的参与方之间保护隐私的协同计算问题，为数据需求方提供不泄露原始数据前提下的多方协同计算能力。

在目前个人数据毫无隐私的环境下，对数据进行确权并实现数据价值显得尤为重要。MPC就是实现此目的的计算协议，在整个计算协议执行过程中，用户对个人数据始终拥有控制权，只有计算逻辑是公开的。计算参与方只需参与计算协议，无需依赖第三方就能完成数据计算，并且参与各方拿到计算结果后也无法推断出原始数据。

2.多方安全计算的来源

多方安全计算（MPC：Secure Muti-Party Computation）研究由图灵奖获得者、中国科学院院士姚期智教授在1982年提出，姚教授以著名的百万富翁问题来说明多方安全计算。百万富翁问题指的是，在没有可信第三方的前提下，两个百万富翁如何不泄露自己的真实财产状况来比较谁更有钱。通过研究此问题，形象地说明了多方安全计算面临的挑战和问题解决思路，经Oded Goldreich、Shaft Goldwasser等学者的众多原始创新工作，多方安全计算逐渐发展成为密码学的一个重要分支。

3.问题抽象

多方安全计算可以抽象的理解为：两方分别拥有各自的私有数据，在不泄漏各自私有数据的情况下，能够计算出关于公共函数 的结果。整个计算完成时，只有计算结果对双方可知，且双方均不知对方的数据以及计算过程的中间数据。

4.什么是多方安全计算？

多个持有各自私有数据的参与方，共同执行一个计算逻辑计算逻辑（如，求最大值计算），并获得计算结果。但过程中，参与的每一方均不会泄漏各自数据的计算，被称之为MPC计算。

举个例子，Bob和Alice想弄清谁的薪资更高，但因为签署了保密协议而不能透露具体薪资。如果Bob和Alice分别将各自的薪资告诉离职员工Anne，这时Anne就能知道谁的薪资更高，并告诉Bob和Alice。这种方式就是需保证中间人Anne完全可信。

而通过MPC则可以设计一个协议，在这个协议中，算法取代中间人的角色，Alice和Bob的薪资以及比较的逻辑均交由算法处理，参与方只需执行计算协议，而不用依赖于一个完全可信的第三方。

多方安全计算所要确保的基本性质就是：在协议执行期间发送的消息中不能推断出各方持有的私有数据信息，关于私有数据唯一可以推断的信息是仅仅能从输出结果得到的信息。

4.1.什么是算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

算法具有以下五个重要特征：

• 有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止；
• 确切性：算法的每一步骤必须有确切的定义；
• 输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
• 输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
• 可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

注意：文档中提到的“算法”，特指MPC底层算法；“计算逻辑”特指为执行具体运算而编写的算法，运行在MPC底层算法之上。

4.2.MPC问题分类

由算法适用性来看，MPC既适用于特定的算法，如加法、乘法、AES，集合交集等；也适用于所有可表示成计算过程的通用算法。

根据计算参与方个数不同，可分为只有两个参与方的2PC和多个参与方（≥3）的通用MPC。

安全两方计算所使用的协议为Garbled Circuit(GC)+Oblivious Transfer(OT)；而多方安全计算所使用的协议为同态加密+秘密分享+OT。

在多方安全计算中，安全挑战模型包括半诚实敌手模型和恶意敌手模型。市场大部分场景满足半诚实敌手模型，也是JUGO技术产品所考虑的敌手模型。

• 半诚实敌手模型：计算方存在获取其他计算方原始数据的需求，但仍按照计算协议执行。半诚实关系即参与方之间有一定的信任关系，适合机构之间的数据计算；
• 恶意敌手模型：参与方根本就不按照计算协议执行计算过程。参与方可采用任何（恶意）方式与对方通信，且没有任何信任关系。结果可能是协议执行不成功，双方得不到任何数据；或者协议执行成功，双方仅知道计算结果。更多适用于个人之间、或者个人与机构之间的数据计算。

4.3.多方安全计算主要通过以下四大技术来进行保障:

（1）同态加密（Homomorphic Encryption，简称HE）

同态加密是一类具有特殊自然属性的加密方法，可在密文域下进行数据运算的加密算法。与一般加密算法相比，同态加密除了能实现基本的加密操作之外，还能实现密文间的多种计算功能，即先计算后解密等价于先解密后计算。

根据不同加密方案对所支持功能的不同限制，同态加密方案可分为有限同态和完全同态(FHE)方案。有限同态的加密算法只支持某些特定的功能（如有限的加法和乘法运算）。有限同态算法容易实现，其计算开销也小；因此，这种算法已经在实践中使用。相比之下，完全同态算法可以支持任意函数，但其计算开销巨大；因此，它们离实际应用还有一定距离。

通过FHE算法，数据用户可以将加密数据外包给服务器，直接对这些数据执行各种操作，而不暴露这些数据包含的任何机密信息。支持的操作包括查询和修改加密数据。一旦对加密数据操作的操作已经完成，结果就返回给数据用户，数据用户使用相应的解密密钥对接收到的加密数据进行解密。在整个过程中，服务器帮助数据用户执行复杂的操作，而无需从用户的数据中获取任何信息。

多用户同态加密主要有两种类型：门限FHE和多密钥FHE。在前者中，密钥生成过程是一个交互式SMPC协议，其中多个用户共同协商一个公钥并获取相应私钥的秘密份额。然后，所有用户都使用公共公钥对其私有数据进行加密并将其发送到服务器，其中，该服务器具有强大的计算能力。此服务器对收到的密文执行任意函数计算。最后，用户交互地应用解密协议来获得计算结果的明文。

（2）混淆电路（Garbled Circuit，简称GC）

混淆电路思想是利用计算机模拟集成电路的方式来实现多方安全计算的，它将运算任务转化为门电路的形式，并且对每一条线路进行加密，在很大程度上保障了用户的隐私安全。

（3）不经意传输（Oblivious Transfer，简称OT）

不经意传输协议是一种可保护隐私的秘密协议，它使得服务发送方和服务接收方以不经意的方式交互信息，从而可达到保护隐私的目的。不经意传输协议是一个两方安全计算协议，接收方从发送方的数据中选取部分数据，协议使得接收方除选取的内容外，对剩余数据一无所知，并且发送方也无从知道被选取的内容。

（4） 秘密分享（Secret Sharing，简称SS）

秘密分享也被称为秘密分割，是一种对秘密信息的管理方式，它将秘密进行拆分，拆分后的每一个分片由不同的参与者管理，单个参与者无法恢复秘密信息，需要超过一定门限数量的人一同协作进行合并才能恢复秘密文件。

5.MPC算法基本原理（2PC半诚实模型）

下面介绍安全两方计算的半诚实模型下的MPC算法原理：

5.1.MPC算法执行过程

先对输入数据做预处理。

遵循原则：1、尽量少的数据输入；2、尽量多的数据预处理

——数据量太大时会大幅降低算法执行效率。

计算逻辑转化为布尔电路。

遵循原则：尽量简单的计算逻辑

——由于MPC是计算密集型和通信密集型算法，若计算逻辑很复杂，会对执行效率产生很大影响。

转化方式：手动/电路编译器Frutta

将输入的布尔电路做GC和OT算法（详细在下面叙述），得到输出结果。

5.2.GC+OT的两方计算基本框架

GC+ OT是在两方semi-honest模型下的通用型算法，即可以支持任意计算逻辑的安全两方计算。

总体框架如下图：

6.小结

多方安全计算是一种在不泄漏原始数据的情况下，对数据进行的计算。上述内容首先介绍了MPC的价值及来源，然后详述了两方安全计算的技术实现原理，主要包括GC和OT算法，并对一些技术基础知识做了简要概述。