Secure multi-party computation (MPC) 介绍
文章来源：https://zhuanlan.zhihu.com/p/100648606
1 百万富翁问题
两个百万富翁都想比较到底谁更富有，但是有都不想让别人知道自己有多少钱。在没有可信的第三方的情况下如何进行？
这个问题就是著名的姚式百万富翁问题。姚式，即大名鼎鼎的姚期智，我国唯一一个图灵奖获得者，此问题开创了安全多方计算领域。
为了说明，这里先简化问题，将两个富翁的财产限定在1千万到1亿之间，而且只想做千万级的比较。也就是说：两个富翁，分别为张三和李四。他们自己都清楚自己有几千万财产，也即，他们心里清楚 1～10中的一个数（代表自己千万级的财富）；他们想知道到底谁的数更大一些。
这里假定：
- 两人都值得信任，不会作假
- 两人都希望诚实地比较出谁更服务（即谁的数更大）
- 两人又都希望知道对方财产到底是多少，如果可能的话，拿到具体数字最好了
一个”解决方案”
有人提出这样一个解决方案：放一个天平，两边放上封闭的盒子，让两个富翁分别在两边放入质量相同的苹果，有几千万财富就放几个，最后看哪边重就可以了。就这么简单。
真的这么简单么？这里方案的提出者忽略了一个条件，也就是不存在可信的第三方，天平谁来提供？提供天平者是可以知道一切的。
这是一个看似简单实则非常复杂的问题。
不经意传输的解决方案
这个问题在数学上，必须借助于密码学。不经意传输是解决这个问题的绝妙方案。 那么什么是不经意传输呢？拿这个例子来说，就是张三给李四提供 n 个选择，这n个选择对李四而言都是无法分辨的（即无法获知原始内容的），李四从中选择一个并告诉张三。但有趣的是，张三不能知道李四选择的是哪一个。这个有点难了吧。
回到百万富翁问题，一个简单的解决方案就是一下步骤：
- 张三找10个一模一样的箱子，按照1～10的顺序摆好，并按照自己的财富值分别往里面放入苹果梨和香蕉，具体放法为：如果序号小于自己的财富之，放入苹果，相等，则放入梨，大于自己的财富值，放入香蕉；
- 把10个盒子都叫上锁；并叫李四过来（或者寄给李四）
- 李四根据自己的财富值对相应的箱子再加一把锁。然后把其他所有箱子销毁。并把这个选择的箱子送给张三。
- 张三看到送回来的箱子，但他不知道李四选择的是第几个箱子，因为每个箱子都是一样的
- 张三李四分别开锁，看里面是什么水果： -- 如果是苹果，张三比李四富有； -- 如果是梨，两人一样有钱 -- 如果是香蕉，李四比张三富有
上面的例子中蕴含了半诚实模型、不经意传输等安全多方计算中用到的一系列思想和方法。下面将系统的介绍一下安全多方计算。
2 介绍
安全多方计算（英文：Secure Multi-Party Computation）的研究主要是针对无可信第三方的情况下，如何安全地计算一个约定函数的问题。
安全多方计算是安全可信计算中的一个分支。安全可信计算主要有两大类：外包计算和多方计算。
2.1 外包计算
为了与多方计算做区分，先简要介绍一下外包计算。外包计算就是一方拥有数据并想获取该数据的计算结果，另一方接收这份数据的一个加密格式，并对加密数据进行计算，得到一份加密的计算结果，并将该结果返回给第一方。过程中，另一方不会获得任何没有加密的信息。
其中 Homomorphic encryption （同态加密）就是外包计算中一种常用的技术，同态加密的思路比较直观：直接将原文加密，然后在密文上进行各种运算，最终得到结果的密文。一个典型的应用场景是：数据持有者想对其持有的大量数据进行计算，奈何其拥有的计算资源不足，想借助云服务器的算力完成该计算。如果按照现在流行的做法，那当然是将数据传输到云服务器，然后运行事先写好的程序进行计算。但如此一来，敏感数据便在云服务器上暴露无遗。同态加密正好解决了此问题，数据持有者传输数据前先将数据加密，云服务器在接收到数据后照例计算，只不过这次是在密文上进行的，云服务器啥都看不到。待得到结果后再将结果的密文返还给数据持有者，数据持有者解开后即得最终结果。
2.2 多方计算
多方计算的目标就是对一组计算的参与者，每个参与者拥有自己的数据，并且不信任其它参与者和任何第三方，在这种前提下，如何对各自私密的数据计算出一个目标结果的过程。
这个问题最早于1982年被姚期智提出，但在提出后的20年间这个问题基本上都属于理论研究的范畴。直到21世纪初，随着算法的进展和计算能力的进步，建设通用的多方计算系统才变得现实起来，Fairplay (Malkhi et al., 2004) 是第一个值得注意的通用多方计算系统，它的出现证明了这类系统的现实可行性。
2.3 应用场景
除了开头提到的姚式百万富翁问题，安全多方计算还有一些其他的应用场景。
- Secure auctions（安全拍卖）
- Secure electronic voting （安全电子选举）
- Secure machine learning （安全机器学习）
虽然安全多方计算还是偏学术研究的领域，在工业上不是非常成熟，但是也有一些成功的案例，比如丹麦甜菜拍卖（Bogetoft et al. 2009)、波士顿工资平等研究（Bestavros et al. 2017) 等。
3 安全模型
在安全多方计算中，根据参与方的可信程度可以建立几种安全模型。
- Real-Ideal Paradigm（理想模型） ：在理想模型中，每一个参与方都是可信的，一方将其信息发送给另一方，另一方不会去查看这份信息，只会根据规定计算出结果，并发送给下一方或者所有参与方。
- Semi-Honest Security（半诚实模型） ：半诚实模型就是参与方会诚实的运行协议，但是他会根据其它方的输入或者计算的中间结果来推导额外的信息。
- Malicious Security（恶意模型） ：恶意模型则可能不会诚实的运行协议，甚至会搞破坏。
在现实世界中，理性模型是不存在的，但相比于恶意模型，参与方如果真的想获取到同时对自己有用的信息，多数情况下符合半诚实模型。因此下面也主要讨论半诚实模型下的多方安全计算方法。
4 基本概念和方法
这里介绍一些MPC中的基本概念。
4.1 Secret Sharing （**分享）
**分享是 MPC 中的一个基本原语，很多 MPC 中的方法使用到了它。**分享的基本思路是将每个数字
拆散成多个数，并将这些数分发到多个参与方
那里。然后每个参与方拿到的都是原始数据的一部分，一个或少数几个参与方无法还原出原始数据，只有大家把各自的数据凑在一起时才能还原真实数据。计算时，各参与方直接用它自己本地的数据进行计算，并且在适当的时候交换一些数据（交换的数据本身看起来也是随机的，不包含关于原始数据的信息），计算结束后的结果仍以secret sharing的方式分散在各参与方那里，并在最终需要得到结果的时候将某些数据合起来。这样的话，**分享便保证了计算过程中各个参与方看到的都是一些随机数，但最后仍然算出了想要的结果。
4.2 Random Oracle (随机预言机)
Random Oracle就是一个理想化的Hash。
通常可以视为一张表，两列，一列是用来写输入值x,一列用来记录x对应的Hash,也就是H(x)初始为空，就是空空的两列。
RO的行为可以这么描述：
当输入为x的时候：
- 如果x和H(x)已经在表里记录过，就输出H(x)
- 如果没有关于x的记录，则RO完全随机地在值域中选取一个0,1字符串（或者从其他希望映射到的元素集合中完全随机的选取）当作H(x)，把这个和x一起记录在表里，然后输出这个H(x)。
这里，最重要的安全性特征是：
- 对于Random Oracle，把一个未曾记录在表里的新元素x映射到目标集合里特定元素E的概率始终为
比如，要用RO来模拟把任意长度的01字符串映射到一个256位的01字符串上的Hash，那么把x映射到特定的一个01字符串H(x)的概率是
更一般地，比如映射到k位的01字符串上，这个概率就是
- 如果x未曾记录在表里，则RO相当于一个完全随机的函数。直观上来说，就是RO自己都不知道x会被映射到哪个值。
- 由2可知，任何询问RO的人，即使拿到了除了x之外所有的RO的输出，也无法确定x会被映射到哪个值
4.3 Oblivious Transfer (不经意传输)
密码学中，不经意传输（OT）协议是指，发送方可以向接收方传输一系列信息中的某一部分，接收方可以正确收到信息，但不知道信息属于整体的哪个部分。
4.4 Yao’s Garbled Circuits Protocol（姚氏混淆电路）
姚氏混淆电路是MPC中最基础的技术，很多技术都是基于此的，因此我们先来看下姚氏混淆电路。那么混淆电路具体是如何工作的了。注意关键词“电路（circuit）”，我们知道可计算问题都可以转换为一个个电路，于是就有了加法电路、比较电路和乘法电路等等。当然，更复杂的计算过程，如深度学习等等，也是可以转换成电路的。一个电路是由一个个门（gate）组成的，比如与门、非门、或门、与非门等等。
混淆电路就是通过加密和扰乱这些电路的值来掩盖信息的。在最经典的混淆电路中，加密和扰乱是以门为单位的。每个门都有一张真值表。比如下图就是与门的真值表和或门的真值表。下面就以与门为例来说明混淆电路的工作原理。
Alice和Bob想计算一个与门。该门两个输入线x 和 y 和一个输出线 z ，每条线有0和1两个可能的值。Alice首先给每条线指定两个随机的key，分别对应0和1。
然后，Alice用这些**加密真值表，并将该表打乱后发送给Bob。加密过程就是将真值表中每一行对应的x 和 y 的**加密 z 的**。这一加密+打乱的过程，就是混淆电路（garbled circuit）的核心思想。
那Bob收到加密表后，如何计算呢？首先Alice把自己的输入对应的key发给Bob，比如Alice的输入是0，那就发
，输入是1就发
。同时把和Bob有关的key都发给Bob，也就是
和
。然后Bob根据自己的输入挑选相关的key。由于Bob收到的这些key都是随机数，所以其实并没有任何有效信息泄露。Bob根据收到的
和自己的
，对上述加密表的每一行尝试解密，最终只有一行能解密成功，并提取出相应的
。
Bob将kz发给Alice，Alice通过对比是
还是
得知计算结果是0还是1。由于整个过程大家收发的都是密文或随机数，所以没有有效信息泄露。
以上就是混淆电路中单个门的计算方法。当然每个电路肯定是由多个门组成的，这时候需要将这些门都串起来。当然，这样的混淆电路方法有点复杂，现在大家已经研究出了很多优化方法，具体方法可以去看论文。
4.5 Zero-Knowledge Proof (零知识证明)
零知识证明指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。
Jean-Jacques Quisquater 和 Louis Guillou 用一个关于洞穴的故事来解释零知识证明。在上图中，洞穴里有一个秘密，知道咒语的人能打开 C 和 D 之间的密门。但对任何人来说，两条通路都是死胡同。 假设 P 知道这个洞穴的秘密，她想对 V 证明这一点，但她不想泄露咒语。下面是她如何使 V 相信的过程:
- V 站在 A 点。
- P 一直走进洞穴，到达 C 或者 D 点。
- 在 P 消失在洞穴中之后，V 走到 B 点。
- V 向 P 喊叫，要她: 从左通道出来，或者从右通道出来。
- P 答应，若有必要则用咒语打开密门。
- P 和 V 重复步骤(1)-(5)多次。
若多次重复中，若每次 P 都从 V 要求的通道中出来，则能说明 P 确实知道咒语，并且 V 不知道咒语的具体内容。
4.6 differential privacy （差分隐私）
上述的同态加密、混淆电路、和**分享方法都属于非噪音方法。这些方法一般是在源头上就把数据加密或编码了，计算操作方看到的都是密文，因此只要特定的假设条件满足，这类方法在计算过程中是不会泄露信息的。
还有一类是基于噪音的方法，这类方法的思想是，对计算过程用噪音干扰，让原始数据淹没在噪音中，使别有用心者无法从得到的结果反推原始数据。虽然严格来说，这类方法不算在安全计算当中，但这里也做下介绍。
基于噪音的方法中最火的就是差分隐私。为了更形式化地描述差分隐私，我们需要先定义相邻数据集。现给定两个数据集D和D’, 若它们有且仅有一条数据不一样，那我们就称此二者为相邻数据集。以上面数据集为例：假定有
个人，他们是否是单身狗，形成一个集合
（其中
或
），那么另一个集合当中只有一个人改变了单身状态，形成另一个集合
，也就是只存在一个
使得
，那么这两个集合便是相邻集合。
那么对于一个随机化算法
（所谓随机化算法，是指对于特定输入，该算法的输出不是固定值，而是服从某一分布），其分别作用于两个相邻数据集得到的两个输出分布难以区分。差分隐私形式化的定义为：
也就是说，如果该算法作用于任何相邻数据集，得到一个特定输出
的概率应差不多，那么我们就说这个算法能达到差分隐私的效果。也就是说，观察者通过观察输出结果很难察觉出数据集一点微小的变化，从而达到保护隐私的目的。
那如何才能得到差分隐私呢？最简单的方法是加噪音，也就是在输入或输出上加入随机化的噪音，以期将真实数据掩盖掉。比较常用的是加拉普拉斯噪音（Laplace noise）。由于拉普拉斯分布的数学性质正好与差分隐私的定义相契合，因此很多研究和应用都采用了此种噪音。还是以前面那个数据集为例，假设我们想要知道到底有多少人是单身狗，我们只需要计算
，那么为了掩盖具体数值，实际输出值应为
，相应地，另一个数据集输出的是
。这使得观察者分不清最终的输出是由哪个数据集产生的。
前面描述的是差分隐私的严格定义。还有一种稍微放宽一点的定义为：
其中
是一个比较小的常数。要获取这种差分隐私，我们可以使用高斯噪音（Gaussian noise）。
当然，对输入或输出加噪音会使得最终的输出结果不准确。而且由于噪音是为了掩盖一条数据，所以很多情况下数据的多少并不影响加的噪音的量。那么在数据量很大的情况下，噪音的影响很小，这时候就可以放心大胆地加噪音了，但数据量很小的情况下，噪音的影响就显得比较大，会使得最终结果偏离准确值较远而变得不可用。
5 总结
目前，可信多方计算是一个研究比较火热的领域，但在工程上，单纯的可信多方计算方案并不够成熟。目前工程多采用和硬件可信执行环境（TEE，Intel SGX为代表）技术结合的方案来实现可信计算，比如百度的可信数据计算（http://di.baidu.com/product/calc?castk=LTE%3D）、蚂蚁金服的共享学习平台（https://www.jiqizhixin.com/articles/2019-08-17）等。
参考文献