姓名：王镭璋
学号：19011110177
转载自：https://www.zhihu.com/question/329237347/answer/715419386
https://zhuanlan.zhihu.com/p/68116569
https://zhuanlan.zhihu.com/p/25770963
https://zhuanlan.zhihu.com/p/59108808
多方安全计算（MPC：Secure Muti-Party Computation）理论是姚期智先生为解决一组互不信任的参与方之间在保护隐私信息以及没有可信第三方的前提下协同计算问题而提出的理论框架。多方安全计算能够同时确保输入的隐私性和计算的正确性，在无可信第三方的前提下通过数学理论保证参与计算的各方成员输入信息不暴露，且同时能够获得准确的运算结果。
早在1982年，姚期智先生在其发表的文章《安全计算协议》（Protocols for Secure Computation）里提出了著名的姚氏百万富翁问题，同时也首次引入了双方安全计算的概念来解决问题，并对其可行性进行了验证。两个百万富翁Alice和Bob在无任何可信第三方，同时不暴露自己的财产的情况下，希望得出谁更富有的结论。
我们下面来介绍姚老师的精妙解法 ---
假设富翁王有i亿资产，李有j亿资产。王选取一个公钥，使得李可以传递加密的信息。
首先，李选取一个随机的大整数x，把用王的公钥加密，得到密文K。 李 发送k-j给王。
王收到密文c=k-j之后， 对c+1，c+2，...，c+10进行解密，得到十个数字。再选取一个适当大小的素数p, 把这十个数字除以p的余数记作d1，d2，...，d10。
.注意: 这十个数字看起来应该是完全随机的，关键是等式dj=x mod p 成立。
最后，王对这一串数字作如下操作：前面 i 个数不动，后面的数字每个加一，然后发回给李。
这样一通复杂的操作之后，李检查第j个数字。如果等于x mod p 的话，说明这个数字没有被加一，所以 i >= j. 反之，则 i < j。
这个过程的绝妙之处在于：在协议完成之后，王不知道j的具体值，而李也不知道 i 的值， 但是双方都知道谁的财富更多，这就是多方安全计算。一般来说，在甲只知道x，乙只知道y的情况下，双方可以合作计算一个函数 f(x,y)。协议完成时，只有函数值是公开的，而彼此都不知道对方的输入值。
从前面的举例发现，多方安全计算的特点：
1、两方或者多方参与基于他们各自隐私或秘密数据输入的计算。
2、参与一方都不愿意让其他任何第三方知道自己的输入信息。
在多方安全计算出现以前，解决上述问题的策略是假设有可信任的服务提供者或是假设存在可信任的第三方。但是在目前多变和充满恶意的环境中，这是极具风险的。因此，作为能够解决一组互不信任的参与方之间保护隐私的协同计算问题的技术，安全多方计算变的日益重要。
目前互联网已经完成了从IT时代向DT时代的转变，数据已经成为DT时代企业的核心竞争力。数据作为一种新能源，只有流动起来才能产生价值。不过，大多数企业考虑到数据安全和个人隐私等问题，对数据共享都非常谨慎。而MPC对打破数据孤岛，实现数据的可控共享，具有重要的理论和现实意义。
MPC方案主要可分为基于混淆电路(Garbled Circuit，GC)和基于秘密共享两种。
不经意传输(Oblivious Transfer)
首先介绍一种基础的安全多方计算协议：不经意传输(Oblivious Transfer, OT)。
来看一个例子：假设某旅行社拥有N个景点的旅游资料，小淘想去其中的A景点游玩，希望向旅行社购买相关资料做好出游功课。但是小淘非常在意自己的隐私，不希望向旅行社泄露自己的目的地是哪里。因此双方希望这笔交易能够满足以下隐私条件：
小淘不希望向旅行社泄露“我准备去A景点”这一信息；
旅行社只希望出售小淘出钱购买的那份资料，而不泄露小淘未购买的N-1份资料；
粗看起来这种隐私条件似乎是无法满足的：旅行社只要把景点A的资料给到小淘，就必然了解了“小淘正在关注A景点”这一信息；除非旅行社把所有N份资料都给出，但是这又违背了旅行社的利益；
但是神奇的OT可以让交易在这种“不可能的条件”下达成。简而言之，在OT协议中，旅行社把他拥有的N份资料使用某种双方协商同意的加密算法和参数进行加密，然后发送给小淘；小淘可以从密文中解密出A的资料，而无法解密出其他N-1份资料。
OT除了可以直接用于构造MPC方案之外，也是GC等许多MPC方案的基石。
混淆电路
我们知道，任意函数最后在计算机语言内部都是由加法器、乘法器、移位器、选择器等电路表示，而这些电路最后都可以仅由AND和XOR两种逻辑门组成。一个门电路其实就是一个真值表，例如AND门的真值表就是：
例如其中右下格表示两根输入线(wire)都取1时，输出wire=1：即 1 AND 1 = 1。
假设我们把每个wire都使用不同的密钥加密，把真值表变成这样：
例如其中右下格表示如果门的输入是b和d，那么输出加密的f(密钥是b和d)。这个门从控制流的角度来看还是一样的，只不过输入和输出被加密了，且输出必须使用对应的输入才能解密，解密出的f又可以作为后续门的输入。这种加密方式就称为“混淆电路(Garbled Circuit，GC)”。
将电路中所有的门都按顺序进行这样的加密，我们就得到了一个GC表示的函数。这个函数接收加密的输入，输出加密的结果。
假设有两个参与方A和B各自提供数据a、b，希望安全的计算约定的函数F(a,b)，那么一种基于GC的安全两方计算协议过程可以非正式的描述如下：
细心的同学一定会指出：第4步中A怎么可以接触B的输入b呢？这不是违背了安全多方计算的假设吗？这里就需要使用OT，A扮演Sender，B扮演Receiver，让B从A处得到Encrypt( b)，却不向A透露b的内容。如图所示：
需要注意的是，上述流程只是最原始的GC方法的不严谨描述，GC后续还有Point & Permute、Free XOR、Half Gates等多种细节优化，随着最近几年的研究进展，GC的性能已经差不多可以实用了。以求两个百万维向量的汉明距离(Hamming Distance)为例（应用场景是两份数据求相似度，却互相不泄露数据内容），这样的安全两方计算已经可以在1.5秒左右完成。
安全多方计算的安全模型
半诚实行为模型与恶意行为模型
更细心的同学还会进一步提出问题：“怎么确保A给B的
就是一个正确的GC呢？例如A和B商定要比a和b的大小，商定了F(a,b)=a>b?1:0，但是A可以制作一个别的函数的GC，例如F(a,b)=b的第1个比特，这样显然是会侵害B的隐私的，但是由于函数是以GC形式发给B的，B是没有办法发现这个问题?”
这确实是一个安全问题，事实上，GC还存在如selective failure等其他更多的安全问题。在介绍解决方案之前，我们需要先定义安全多方计算的安全模型。
安全多方计算的安全模型包含多个角度的内容，在上述上下文中，我们关注的是其中的“行为模型”，即参与方可能进行何种行为以获取其他方的隐私。常见的行为模型包括“半诚实(Semi Honest)”和“恶意(Malicious)”两种。前者假设所有参与方都是忠实的按照协议步骤进行执行，只是想通过协议内容推测其他方的隐私，而后者假设恶意参与方为了获取其他方的隐私可以不遵循协议内容。
用扑克牌打个不严谨的比方，半诚实的牌友会试图从自己的手牌和已经打出的牌来推测他人的手牌，但是还是遵循扑克牌规则的；而一个恶意的牌友则换牌、偷牌等手段无所不用。
可见，本节开始提出的问题属于恶意行为的范畴，而原始的GC只能说在半诚实行为模型下是安全的，无法抵御恶意行为攻击。有许多对GC方案的改进方案可以达到恶意行为模型下的安全性，但是它们都需要付出很大的性能代价：仍然以求两个百万维向量的汉明距离为例，其中最快的方法也需要10秒+，比同等的半诚实方案慢7倍以上。事实上，经过我们的调研，若想真正的实现支持大规模数据的MPC产品，基本上只能考虑半诚实方案。这严重影响了安全多方计算的实用性。
多方安全计算的一些应用
在电子选举、电子投票、电子拍卖、秘密共享、门限签名等场景中有着重要的作用。
结束语
百万富翁问题的提出和解答形象地说明了多方安全计算面临的挑战和解决问题的思路，引发了学术界极大的关注。时隔4年，姚期智先生再次取得重大突破，于1986年提出了基于混淆电路的通用解决方案，进一步验证了多方安全计算的通用可行性，同时也奠定了现代计算机密码学的理论基础。此后，经Oded Goldreich、Shafi Goldwasser等学者进一步的研究和创新，多方安全计算逐渐发展成为现代密码学的一个重要分支。
