EN
安全多方计算：理论、实践与应用
写在前面
OpenMPC翻译计划小组正式亮相，本次带来的是“前菜”《Secure Multi-Party Computation: Theory, practice and applications》，由翻译小组成员：书想（摘要、第一章、第六章）、宋小宋（第二章）、松山（第三章）、林立可（第四章）、starry（第五章）共同著作，云中雨雾、六三审稿。
后续会有更多的文章和书籍的翻译推出，尽请期待！
零、摘要
安全多方计算（以下简称SMPC）是一种通用的密码原语，它在不泄露参与方的隐私输入和输出的前提下让分布式参与方合作计算任意函数。自从1982年Yao的开创性工作以来，经过30年的研究，SMPC从当初的纯理论研究走到如今的现实应用。最近，越来越多新兴技术，如云计算、移动计算和物联网使得SMPC更加受到关注。这主要是因为，作为隐私数据计算的通用工具，在这些领域中，SMPC在解决安全性和隐私性方面有天然的优势。也因此出现了很多面向应用的SMPC协议。本文从理论到实践方面对SMPC协议进行全面介绍。首先，我们描述SMPC的基本概念，包括它的安全性要求和基础构造技术。接着，我们介绍关于通用SMPC协议构造技术的前沿研究，还介绍类似云辅助SMPC协议。然后，我们总结当前流行的面向应用的协议。最后，讨论目前关于SMPC的文献并给出总结。
一、引言
随着物联网、移动计算、大数据和云计算的快速发展，人们的生活方式也发生很大的改变。这些技术在收集、存储、传播和信息处理上提出了新模式，这对做为一个整体的整个社会提供了极大便利。为了共享这些不同技术提供的资源，不同组织或者个人之间合作计算变得越来越普遍了。不同数据类型的所有人通过协作计算，在不泄露他们自己秘密数据的前提下合并资源，并由此得到更多有价值的信息。例如，在物联网系统中从不同探测设备收集到的数据可以聚集起来产生目标值。云和客户可以协作得到恰当的服务。但与此同时，隐私信息和秘密数据泄露经常出现。这种安全性威胁严重限制了这些数据处理技术的应用和推广。因此，在多方场景中数据处理方法的隐私保护发展变成急切的任务。
作为信息安全领域中一个核心技术，密码学在确保安全的方方面面中扮演了中心角色，并为数据隐私、完整和认证提供理论基础和技术支撑。在密码学研究中，安全多方计算是一种为合作计算提供隐私保护的通用密码学原语。在密码学领域中，做为一个重要基础研究方向，SMPC以安全的方式处理分布式计算场景中几个拥有隐私数据的参与方执行协作计算的问题。也就是说，在SMPC场景中，两个或者多个拥有隐私输入的参与方想要使用这些输入共同计算某个功能性。在这个过程中，安全性要求每个参与方除只能得到自己的目标输出之外，不能得到更多的信息。在这里，功能性是一个通用的概念，可以指几乎任意密码学任务，比如加密、认证、零知识证明、承诺方案、不经意传输和其它非密码学协议（也就是说，面向应用的任务，包括合同签署、电子投票、机器学习、基因数据处理等等）。可以说，SMPC是密码学领域中最通用也最基础的理论研究方向。只要涉及多个参与方的任何密码学任务都可以看成一个SMPC任务。SMPC的大量研究推动了基础原语的发展，比如零知识证明、不经意传输和秘密共享。SMPC在交互协议中为可证明安全性建立了理论基础，也极大地推动了现代密码学的发展。
这篇概述的目的是为SMPC的安全解决方案的技术发展水平做一个全面总结。在进入单个方案和对应的性质的描述之前，我们在第2节中先给出通用的框架，包括基础概念、研究领域、安全性要求和各种不同的组织模块。第3节给出了安全计算的通用构造，包括半诚实和恶意模型的安全协议和各种构造技术。接着，在第4节中，我们讨论云辅助SMPC解决方案。第5节阐述各种不同的计算领域的面向应用的计算。最后，第6节是本概述的总结。
二、安全的多方安全计算：威胁，安全要求，构造块
在分布式的多方安全计算（Secure Multi-Party Computation , SMPC）环境中,含有隐私输入的两方或者多方参与者希望协作和交互式地计算一个目标函数
2.1研究领域
SMPC从理论到实践涵盖了广泛的研究领域，其中包括多方安全计算的构造块，多方安全计算协议，基于云的多方安全计算，以及面向应用的协议等。图2显示了SMPC研究领域的高级概述。
理论研究包括安全模型、可行性和复杂性等方面的研究。理论研究的目的是将来自理论研究的优雅的理论想法转化成解决现实世界安全问题的具体的SMPC协议。实用的多方安全协议注重于效率问题。SMPC理论协议涉及的研究和方法主要从计算成本、通信成本和交互轮数方面提高通用和特定协议的效率。
通用SMPC包括将目标计算任务转换为算术或布尔电路，将分解为一系列算术门或逻辑门的基本组合，以及在特定安全模型下为电路设计SMPC协议。用于此目的的底层加密工具包括秘密共享、全同态加密、不经意传输和混淆电路。所开发的电路能够逐层执行计算，最终以安全的方式完成计算任务。近年来，研究人员致力于在各种安全模型下提高此类协议的效率。同时，为了平衡效率和安全性，提出了一些安全性较低的新模型。
基于云的SMPC的研究旨在通过利用云服务器上的可用资源来显著降低计算和通信开销，从而提高协议效率。
面向应用的SMPC包括隐私集合计算、隐私保护机器学习、数据挖掘和安全基因组计算等领域的研究。
所有这些协议都涉及到基本的构造块，如不经意传输、秘密共享、投币、同态加密、承诺方案、零知识证明等。这些构造块为理论和实用的SMPC奠定了基础。
2.2 威胁和安全要求
SMPC考虑了不诚实者的不诚实行为的可能性。攻击的目的可能是发现他人的私人信息或在计算任务中造成错误。在一个SMPC的任务中，对手可能控制参与者的某些子集。被对手控制的一方被称为被腐坏(腐化、收买)的参与者，在执行协议时完全遵循对手的指示。为了证明一个协议是安全的，研究者们提出了许多关于安全性的定义，这些定义主要是为了保证以下几点重要的安全性要求：
-
隐私性：任何一方都不能获得除了自己的输出和可以从自己的输入和输出中可得出的信息之外的其他信息。
-
正确性：每个参与者收到的输出应是正确的。
-
输入独立性：被腐坏的参与者选择的输入必须独立于诚实参与者的输入。
-
输出保证性：被腐坏的参与者不应阻止诚实的参与者获得他们自己的输出。换句话说，对手不应通过运行“拒绝服务”攻击来中断计算。
-
公平性：被腐坏的参与者收到自己的输出, 当且仅当诚实参与者收到了自己的输出。
理想/现实模拟范式：上述清单不构成安全性定义；它仅仅列举了安全协议必须满足的某些要求。相比之下，安全性定义应包括所有重要的安全要求，并涵盖所有可能的对抗性攻击。此外，它应该简单且足够简洁以供实际应用。
安全的现行标准定义如下。考虑一个“理想世界”，其中有一个外部的受信任方去帮助参与者进行计算。在这样一个世界中，参与者只需通过一个完全安全的通道将其输入发送给受信任方，然后受信任方计算所选的功能并将相应的输出独立地秘密地发送给每个参与者。因为参与者执行的唯一操作是将他们的输入发送给受信任方，所以留给对手的唯一自由就是选择被腐坏方的输入。因此，在一个理想的世界中，上面列出的所有安全要求都得到了满足。
然而，在“现实世界”中，没有任何一方是可以被所有参与者信任的，相反的是，参与者在没有任何外部协助的情况下共同执行协议。如果该协议能够模拟在上述理想世界中得到的结果，即如果参与者执行的真实协议能够保证没有对手能够在理想世界中执行时造成比可能更大的伤害，则该协议被称为安全协议。这个条件可以表示为：对于任何在现实世界中执行成功攻击的对手，理想世界中的对手必须始终能够成功执行相同的攻击。然而，在理想世界中，攻击是不可能成功执行的；因此，所有针对协议执行的真实攻击都必须失败。
下面给出了更直观的安全定义。协议的安全性可以通过两种联合输出分布的比较来评估：真实世界中的对手和诚实参与者获得的输出分布，以及在理想世界中通过执行获得的输出分布。即，对于针对真实协议执行任何攻击的对手，考虑在理想世界中执行相同攻击的对手，并且如果理想世界中的对手和参与者的联合输入/输出分布与真实世界中的相应分布相同，则满足安全准则。在这种情况下，真实协议的执行“模拟”了理想世界的效果。正如图3所示，其安全性定义称为理想/现实模拟范式。
2.3 安全模型
上述对安全的非正式定义没有考虑安全模型。在SMPC的研究中，安全模型定义了对手的能力。协议的安全性只有在特定的安全模型下讨论才有意义。协议只有在相应的安全模型下能够抵抗任何对抗性攻击，才被认为是安全的。根据对手的行为，安全模型可分为以下不同类型。
半诚实对手模型：在半诚实对手模型中，被腐坏的参与者必须正确执行协议。但是，对手可以获得关于每一个被腐坏方的内部状态的全面信息（包括所有收到的信息的抄本），并将试图利用这些信息获取应保密的其他信息。尽管这是一个非常弱的对手模型，但它捕捉到了许多实际场景。例如，假设多个组织或公司希望在某个任务上进行协作。他们不会因为被发现作弊而蒙受名誉损失或负面新闻而做出不诚实的行为；然而，他们希望获得尽可能多的其他参与者的私人信息以获得优势。
恶意攻击模型：在恶意模型中，被腐坏的参与者可以根据对手的指令任意偏离协议的规范。一个可以安全抵御恶意攻击者的协议能保证任意一个恶意攻击都将要失败。然而，要实现这一级别的安全性，必须在协议的效率方面付出沉重的代价。这是竞争对手之间执行联合计算任务的首选模型。参与者的行为可能不诚实，以导致错误，或产生错误的计算结果，即使他们可能被发现作弊，以最大限度地提高他们的利益。
隐蔽的攻击模型：上述的半诚实对手模型过于脆弱，但恶意对手模型在安全性要求下导致协议效率太低。为了克服这些困难，提出了一种隐蔽敌手模型。一个隐蔽的对手可能表现出恶意行为，但它有一定的概率被诚实的参与者发现作弊。这一模型代表了许多金融或政治环境，在这些环境中，诚实的行为是不可能假设的，但所涉及的公司和机构不能承受与被发现作弊有关的名誉损失。在这个模型中，对手必须权衡被抓住的风险和作弊的好处。
2.4 构造块
这一章节，我们简要的介绍一下在多方安全计算领域使用的一些构造块，包括混淆电路、不经意传输及其扩展、cut-and-choose、承诺方案和同态加密。.
2.4.1混淆电路：
姚的协议是基于混淆电路两方安全计算（S2PC）的方法。混淆电路是一种基本的密码原语，在实现通用协议中起着重要的作用。给定目标函数的混淆电路具有以下性质：
-
每条电路线对应两个混淆码：一个是比特 0，一个是比特 1。
-
如果电路的每一条输入线都有一个给定的混淆密钥，那么整个混淆电路就可以在不泄漏任何其他信息的情况下不经意间地计算得到电路的输出值。
通过将电路门逐层组合，可以直接构造出一个混淆电路。具体地说，由于电路中的前一个门的输出线用作下一个电路门的输入线，因此前一个混淆门输出的混淆密钥也是下一个混淆门的输入的混淆密钥。因此，一旦为每个电路线选择了两个混淆密钥，就可以如上关于混淆或门 G(n) 的构造所述逐层构造每个电路门的混淆本，因此，最终可以构造整个混淆电路构建。
在一个加密电路的构造完成后，如果给电路的每条输入线一个加密密钥，电路的第一层就可以被成功解密。在第一层中的每一个混淆门被成功解密之后，结果就是输出线上的混淆密钥。因为这些输出密钥也是下一层中的混淆门的输入密钥，所以混淆电路的解密可以逐层的方式继续链接，最后得到电路的输出值。
2.4.2 不经意传输及其扩展
不经意传输扩展。不经意传输在 SMPC 协议中有着广泛的应用。例如，在基于混淆电路的SMPC 协议中，每条输入线必须运行一个不经意传输协议。在基于秘密共享的SMPC协议中，每个与门必须至少运行一个不经意传输协议。因此，数以百万计的不经意传输的实例必须在SMPC协议中运行，这导致了过高的操作成本。针对这一问题，提出了一种扩展不经意传输的方法。不经意传输扩展协议通过运行几个“base”不经意传输实例来工作。“base”实例的数量取决于使用的安全参数。基于这些“base”实例，我们可以进一步获得更多的不经意传输实例，而只需使用计算上廉价的对称密码操作就可以进一步获得更多的不经意传输实例。这样，可以高效地实现不经意传输扩展。
2.4.3 同态加密
同态加密是一种加密方法，它允许在密文上的计算产生一个加密的结果，当解密时，与在明文上进行计算会得到的结果一致。通过同态加密，可以对加密数据进行产生正确结果的计算（例如，算术运算、搜索、比较和编辑）。此外，在整个过程中，数据是以密文形式处理的，不需要解密。同态加密的这一特殊属性在构建加密方案和安全协议方面发挥了关键作用。
根据不同加密方案对所支持功能的不同限制，同态加密方案可分为有限同态和完全同态方案。有限同态的加密算法只支持某些特定的功能（如有限的加法和乘法运算）。有限同态算法容易实现，其计算开销也小；因此，这种算法已经在实践中使用。相比之下，完全同态算法可以支持任意函数，但其计算开销巨大；因此，它们离实际应用还有一定距离。现在，我们对C-同态加密和全同态加密（FHE）进行详细描述。
同态加密和全同态加密
通过FHE算法，数据用户可以将加密数据外包给服务器，直接对这些数据执行各种操作，而不暴露这些数据包含的任何机密信息。支持的操作包括查询和修改加密数据。一旦对加密数据操作的操作已经完成，结果就返回给数据用户，数据用户使用相应的解密密钥对接收到的加密数据进行解密。在整个过程中，服务器帮助数据用户执行复杂的操作，而无需从用户的数据中获取任何信息。
门限完全同态加密和多密钥完全同态加密。在SMPC中应用时，通常采用多用户FHE的形式。在这个场景中，多个用户加密他们自己的私有数据。所有需要的函数都是基于这些加密数据计算的。最后，用户对结果进行解密，得到相应的明文。
多用户同态加密主要有两种类型：门限FHE和多密钥FHE。在前者中，密钥生成过程是一个交互式SMPC协议，其中多个用户共同协商一个公钥并获取相应私钥的秘密份额。然后，所有用户都使用公共公钥对其私有数据进行加密并将其发送到服务器，其中，该服务器具有强大的计算能力。此服务器对收到的密文执行任意函数计算。最后，用户交互地应用解密协议来获得计算结果的明文。
门限全同态加密和多密钥全同态加密区别：在前一种情况下，每个用户都有一个公私钥对。用户使用自己的公钥，而不是使用公共公钥来加密他们的私有数据。这样，每个用户都可以使用自己的公钥加密希望外包的个人数据，然后将其存储在外部服务器上。当用户请求服务器计算特定函数时，服务器使用存储的加密数据在本地执行计算，而不需要任何用户交互。在计算完成之后，用户交互地应用解密协议来恢复计算结果的明文。
三、通用安全多方计算
一种通用的SMPC协议允许两方或多方，以一种安全的方式来联合计算任意函数。像这样的协议不是用来解决某个特定问题的，它是一个通用协议。在本节中，我们研究了文献中几个重要的方法。
3.1 半诚实模型中的安全计算
在Yao的协议中，每个电路门只涉及恒定数量的对称的密码操作(除了由于调用了不经意传输（ OT ），也涉及不对称操作的输入门);因此，该电路非常高效。但是，由于所需要的电路可能非常大，以前认为使用基于电路的协议来完成SMPC任务是不切实际的。Yao的协议的出现引起了密码学学界的广泛关注。该方法的主要研究方向之一是优化混淆电路的构造方法，从而有效地提高计算效率。
以前，人们认为Yao的开创性作品仅仅是理论成果;但是，在2004年，Malkhi等人实现了一个被称为Fairplay的基于电路的通用安全计算平台。从那时起，出现了更多的针对SMPC编程工具的实现的研究工作，这大大促进了提高通用SMPC协议的效率并将其应用于实践的努力。
3.2 实现针对恶意敌手的安全性
Yao的协议只有在对付半诚实的敌手时实现安全，这在实践中是不够的。为了抵御恶意敌手的攻击，早期的解决方案通常使用通用的零知识证明来约束参与者的行为。尽管这些技术有助于设计常数轮安全协议，但这些协议并不实用。关于如何避免使用通用零知识证明的文献也存在，但这些协议的轮复杂度在电路深度上是线性的。我们总结了在恶意模型中构建高效SMPC协议的几种流行技术。
Cut-and-choose范例。cut-and-choose范例是由Lindell和Pinkas最先提出的，其目标是约束潜在的恶意生成器Gen以一种半诚实的方式行动。cut-and-choose范例迫使Gen构建一个混淆电路，以正确计算目标功能和仅显示预期输出。具体来说，Gen需要构造相互独立的混淆电路的s实例(其中s是一个统计安全参数)并将它们发送给电路评估器Eval。然后，Eval打开一些这样的实例(被称为校验电路)来检测这些混淆电路是否都被正确构造。如果混淆电路都被正确构造，Eval假定有很高的可能性，剩余的混淆电路(被称为求值电路)也被正确地构造。否则，Eval将中止该协议。然后，双方按照Yao的协议计算每个计算电路，并将大部分的计算结果视为协议输出。
将 cut-and-choose 方法应用到 Yao 的协议中是在恶意模型中实现安全性的一种有效方法。cut-and-choose 技术用统计安全参数 S 代替了复杂和低效的零知识证明。这个参数被用于描述不依赖于任何密码图形计算假设而只依赖于混淆电路的数量的作弊概率。
除了上述方法之外，研究人员还利用了其他技术来提高cut-and-choose基础协议的效率。例如，为了获得好的平摊效率，研究人员提出了分批cut-and-choose方法，即同一功能的一批实例在使用可能不同输入的相同各方之间有效地执行。
3.3 通用SMPC的其他先进方法
LEGO。不同于Lindell和Pinkas在整个电路中采用cut-and-choose技术的方法，Nielsen和Orlandi提出的LEGO方法依赖于为了获得更好的渐近效率而在门级进行的cut-and-choose测试。这个方法要求电路发生器Gen向接收器发送多个与非门。接收者Eval打开这些门的随机子集以进行检查。如果检查成功，Eval将未打开的门随机排列到桶中，表示冗余的与非门。Eval在Gen的帮助下，将每个桶内的门焊接在一起，然后再将桶焊接在一起，形成一个即使每个桶中有少数门故障，也能正确计算出函数的电路。
但是，LEGO为每个门调用公钥原语，这是协议效率的一个缺点。除此之外，LEGO不兼容已知的优化技术的混淆电路。为了克服这些缺点，Frederiksen等人提出了MiniLEGO，MiniLEGO在实现了相同的统计安全性的同时，用一个更高效的xor同态承诺方案取代了LEGO中使用的Pedersen承诺方案。与LEGO不同，由于MiniLEGO使用标准的混淆电路，所有已知的混淆电路的优化方法都适用。最近的一个独立工作提出了一个名为TinyLEGO的实现，该实现在实践中演示了LEGO方法的效率。然而，协议的安全性仍然取决于每个桶中的大部分电路是否正确。最近，Zhu和Huang提出了一个更快的LEGO协议，他们称之为JIMU。新提出的协议不依赖同态承诺，但只要每个桶中至少有一个混淆门是正确的，就能保证安全性。检测出故障的门的概率是以前的两倍。
IPS编译器。Goldreich等人基于单向函数，展示了如何将一个针对半诚实敌手的安全计算协议编译成一个针对恶意敌手的安全协议。这种有名的技术被称为GMW编译器。在2008年，Ishai等人提出了一个完全不同的结构，称之为IPS编译器。它利用多方协议进行半诚实敌手的基本操作(在这种情况下大部分是诚实的)，并在恶意模型下将诚实多数的多方协议转换为不诚实多数的多方协议。为了计算多方协议，IPS编译器的底层结构是一个工作原理类似于GMW编译器，适用于两方和多方场景的黑盒子。此外，它提供了更好的渐进复杂性，并在非交互上下文中产生了单轮协议。但是，它的常数比预处理模型的常数大，并且在在线阶段不如预处理模型高效。Ishai等人利用IPS编译器研究了有限环上的算术电路在存在恶意敌手的情况下的安全计算。该方法可用于仅执行对环操作和标准密码原语的黑盒调用，并在OT混合模型中实现无条件性。为了确保协议安全性，同时最小化黑盒和通信成本，Lindell等人优化了IPS编译器中的监视列表创建阶段，并提出了，在给定的敌手模型下，使用隐藏安全协议作为实现更高效的渐进安全性的底层组件。此外，Lindell等人分析了IPS编译器的具体效率，并证明在某些情况下它可能是最有效的协议。
3.4 不同方法的比较
在表2中，对四种不同的通用SMPC方法进行了比较
四、云辅助的安全多方计算
虽然存在多种技术构建通用 SMPC 协议，但是他们目前计算量很大，导致 SMPC 仍然难以实用。为了实现计算效率更高的 SMPC，最近的研究重点是开发用于将最昂贵的计算任务外包给云的安全技术。相对于将云作为一个可信第三方而言，这些外包协议寻求在不泄露任何输入和输出值的情况下使用云计算。通过允许各方安全地将他们的计算外包给云提供商，云辅助 SMPC 提供了一种不同但有效的方法来使通用 SMPC 协议变得实用且可扩展。
4.1新挑战
Kamara 等人[24] 首次提出了 server-aided SMPC(cloud-assisted SMPC 的另一种形式)。云服务器的加入有助于提高 SMPC 协议的运行效率。然而，它也带来了新的挑战。特别是，它改变了SMPC的计算模式和安全模式。在经典的 SMPC 中，隐含地假设计算是在同构计算环境中执行的，其中所有参与者扮演相似的角色。在云辅助 SMPC 中，协议在异构环境中运行，该环境除了包含评估功能的各方之外，还包含不可信服务器，该服务器(1)不向正在计算的函数提供输入，(2)不从计算任务接收任何输出，但是(3)可以访问大量计算资源。这种设置在server-aided SMPC 或 cloud-assisted SMPC 中被提及，如图 7 所示。在这种模式下，评估功能的各方可以将SMPC 的繁重计算任务外包给云服务器。
尽管新的计算模型显著提高了协议效率，但是云辅助的 SMPC 面临着新的安全挑战。例如，云服务器可以与一部分参与方串通，以获得关于其他参与方的输入的附加信息。此外，恶意或“懒惰”的云服务器可能会向外包方返回伪造的计算结果。因此，需要新技术来保证云辅助 SMPC 的安全。
4.2 实施方案
基于混淆电路的云辅助 SMPC。在基于混淆电路的 S2PC 中，一方是电路发生器，另一方是电路评估器。在云辅助模型中，混淆电路的生成和评估都可以外包给云服务器。将自己的计算任务外包出去的一方称为外包方，其他方称为非外包方。
在这样的外包环境中，期望设计具有线性复杂度的 SMPC 协议，这意味着外包方的计算和通信成本随着其输入和输出的大小而线性增加。为了达到这种复杂程度，非共谋假设是必要的。尽管非共谋模型的安全性弱于 SMPC 标准恶意模型，但非共谋模型有时更可取，因为它支持广泛的应用。
Kamara 等人的开创性工作 [24] 提出了两个安全的 single-server-aided S2PC 协议，其中电路评估任务外包给云。后来 Carter 等人 [5] 考虑对手机等限电设备外包安全功能评估。与 [24] 中提出的协议相反，在 [24]中，双方被假设具有低计算能力但高带宽，而 [5] 中提出的工作考虑了一种场景，其中双方，一个具有低带宽的移动设备和一个应用服务器，想要在云服务器的帮助下运行S2PC协议。在此提议的协议中，移动设备将电路评估所需的复杂计算外包给云服务器。在 [5] 中，引入了一种称为外包不经意传输的原语，它允许移动设备将混淆密钥传输任务委托给云服务器。Mood 等人[35]主要考虑了在云中重用加密值的云辅助协议。这些作者提出了 PartialGC 的概念，它允许在混淆电路计算期间生成的加密值被重用。
除了电路评估任务，电路生成任务也可以外包给云服务器。与 [5] 中提出的场景相比，Carter 等人 [4] 将移动设备视为混淆电路生成器，并成功地将混淆电路的生成安全地外包给不可信的云服务器。
上述工作考虑了 single-server-aided 模型中的外包协议。相比之下，Kerschbaum [25] 提出了一种方案，将混淆电路的生成外包给多个服务器，分为加密服务器和评估服务器。这两种类型的服务器分别负责加密和评估混淆电路。该协议实现了三种类型的不经意：输入输出不经意、函数不经意和外包不经意。
基于同态加密的云辅助 SMPC 。同态加密可以自然地与云计算相结合，构建云辅助的 SMPC 协议[32，36，40]。基本思路如下。为了执行计算任务，所有参与方用 FHE 方案加密他们的数据，并将生成的密文上传到云中。然后，云对这些密文执行计算，并返回结果密文。所实现的数据隐私取决于潜在的 FHE 方案的安全性。然而，任何参与方都不应直接拥有FHE方案的秘钥。因此，问题变成了一方如何解密计算结果。
在 [1] 中，Asharov 等人通过在所有参与方之间共享密钥来解决这个问题。他们基于门限 FHE 方案构建了一个云辅助的 SMPC 协议。在这种情况下，在每次计算过程中，所有参与者都需要生成系统的参数，包括私钥、公钥和评估密钥。然而，在实践中，当参与这样的协议时，参与者更喜欢提前生成他们自己的长期参数。因此，López-Alt 等人 [32] 提出了一个动态多方计算模型。在他们的模型中，所有参与者都有自己的长期公/私钥对，并且所使用的 SMPC 协议可以通过多密钥 FHE 方案来构建。
上述工程的效率 [1，32] 取决于基础 FHE 方案的效率。为了提高协议效率，Peter 等人 [40] 提出了一种新的实用协议，该协议仅基于加法同态加密方案。他们使用了一种特殊类型的加法同态加密，称为 BCP 加密方案，其中有一个主密钥，可以用来解密用任何公钥加密的密文。此外，这些作者假设存在两个非共谋的云服务器：一个存储底层加密方案的主密钥，另一个存储所有用户生成的密文。这两个服务器在所有相关用户上传数据后交互执行必要的计算。
比较。基于 FHE 的云辅助 SMPC 框架比基于混淆电路的框架简单。然而，遵循这种方法的实现的实用性依赖于 FHE 方案的效率，并且不幸的是，如何构造实际的 FHE 方案的问题仍然是一个未解决的问题。然而，如果目标不是为了构建通用协议，对于某些特定的功能，实现只需要某种程度上的同态加密方案，并且仍然可以制定实用的协议。
基于混淆电路的云辅助 SMPC 协议的构建不需要使用低效的公钥密码工具。然而，这样的协议仍然有两个缺点。首先，基于混淆电路的云辅助 SMPC 协议只能在非共谋的假设下实现安全性，而基于同态加密方案实现的安全性即使在任意腐败方共谋时也成立。然后，当执行基于混淆电路的协议时，至少一个用户(不是云服务器)必须执行其开销与电路的电路大小成线性关系的计算，而对于基于同态加密的协议，云服务器之外的任何参与方的开销仅取决于该参与方的输入/输出的长度，从而最小化参与者的本地计算和通信成本。不同方法的简要比较见表 3。
4.3 云计算在特定 SMPC 环境中的应用
云计算引入了资源组织和利用的新范式。不可避免的是，需要为云环境设计和实施安全协议。作为一种强大的外部资源，云不仅是 SMPC 的补充服务，也是安全执行密码学中特定计算任务的重要参与者，包括加密方案和数学计算 [6]。此外，在云计算时代，一些新的安全问题已经引入或重新出现，如可搜索加密、不经意 RAM、可验证计算 [7] 和安全重复数据删除 [26]。这些问题也可以抽象为 SMPC 功能，并可以通过 SMPC 协议解决。因此，在云计算环境下为 SMPC 提供全面实用的方案至关重要。
五. 面向应用的安全多方计算
除了研究通用的SMPC协议的前沿技术之外，许多研究者关注着SMPC的实际应用，例如面向应用的SMPC。这一节，我们重点介绍一些实用的的SMPC应用，包括隐私保护的机器学习，隐私集合求交集（PSI）以及安全的基因组序列比较。
5.1 通过SMPC确保机器学习的安全
机器学习通常被认为是大数据系统中最重要的工具，因为它能够有效地挖掘隐藏在大量数据中的有价值的知识。然而，即使在使用多GPU加速的情况下，用深度学习技术来训练图像处理算法仍然需要数个小时甚至几天的时间。因此，许多云服务提供商提供机器学习服务，例如Azure机器学习和谷歌云机器学习引擎。使用这些平台，用户可以把他们的机器学习任务外包给云，然而，因为安全和隐私方面的担忧，他们不愿意向云披露他们的数据。因此，隐私和安全已成为外包学习任务的热点问题。本节，我们总结在不同框架和不同安全需求下，使用SMPC保护机器学习任务的最新研究成果。
多数据源的隐私保护机器学习 在这个场景，数据是从不同用户收集的。例如，智能穿戴设备可能会从佩戴者那里收集数据，并且把这些数据上传给一个数据中心。另外一个应用的例子是，用户为了从服务提供商获得基于位置的服务，会把位置信息上传到云上。出于隐私方面的考虑，一些用户不希望他们的敏感数据泄露给云。因此，具有挑战性的问题出现了，即如何在保护每个用户敏感数据的同时，确保基于机器学习的服务可以为所有用户提供。迄今为止，已经提出了从分布式的数据源进行私密学习的两种技术方案。一种是基于随机化，例如使用差分隐私，在原数据上加入噪声。另外一种通过SMPC构造的。对于后者，通用的方法是首先设计一个数据聚合方案，将使用不同密钥加密的数据聚合到一个整合的数据集中。此外，目前也有许多针对多数据源的特定隐私保护机器学习任务的研究工作。例如，[16]构造了一种隐私保护的朴素贝叶斯分类方法。
在两方情况下保护数据和训练好的模型 在这个场景中，一个云服务器（称作Bob）拥有一个数据集并通过一个特定的机器学习算法训练一个模型，Bob希望不把这么模型泄露给其它实体。用户（称作Alice）希望基于他自己的数据得到定制化的服务，但是他不想私有数据被泄露。这种情况适用于经典SMPC协议的应用：Alice输入她的私有数据，Bob输入模型。协议执行的最后，Bob不知道Alice的数据，Alice不知道Bob的模型。这类方法包括[3,11]。
5.2 隐私集合计算
集合计算是SMPC中常用的基本运算。它们是隐私保护的数据查询和数据挖掘等任务的基本工具。Freedman等首先研究了两方集合求交，并提出了一个基于Paillier同态加密系统的协议。该协议在标准模型中实现了对半诚实敌手的安全性，并在随机oracle（RO）模型中抵抗了恶意方。Freedman等工作引入了隐私集合计算的研究方向，他们所使用的工具成为了后续研究工作的基础。一个研究方向是扩大集合运算的范围，然而另外一个研究方向是在在一个更强的安全模型或更简单加密假设下设计隐私集合交集（PSI）协议。为了在不引入低效的零知识证明的情况下设计一个抵抗恶意敌手的PSI协议，Hazay和Lindell提出使用不经意伪随机函数评估（OPRF）来解决集合求交和模式匹配问题。对于完全恶意安全模型，基于其它范式的PSI协议有不同的方法[18,44]。主要有五种不同的技术来构造高效的PSI协议，包括朴素解决方案、基于三方的PSI、基于公钥的PSI、基于电路的PSI、基于OT的PSI。最近，越来越多基于OT的PSI的研究工作出现了。这一段，我们主要介绍基于OT扩展的PSI协议。Dong等提出了一个基于OT扩展和Bloom过滤器的PSI协议。Pinkas等人使用随机混淆Bloom过滤器协议优化了Dong等人的工作，这个协议是基于随机OT扩展，在半诚实模型中实现了安全性。[42]中规范了安全性的弱概念，Rindal和Rosulek在其中描述了PSI的一个廉价协议范式，并对[41]进行了优化，以实现弱恶意安全性。随后，Rindal和Rosulek[43]试图扩展PSI协议，使其在存在恶意对手时安全，并表明基于Bloom过滤器的协议对抵抗恶意对手并不安全。
5.3 安全基因组序列比较
基因组序列比较是基因组计算中最基本和应用最广泛的操作之一。对安全的基因组计算来说，采用最主要技术是S2PC。隐私保护的基因组序列比较是S2PC的一个特定的场景，专注于以安全的方式实现两个基因组序列的校准。基于底层所使用的技术，S2PC协议的一般构造方法分为两大类：基于同态加密的构造和基于混淆电路的构造。通用构造可以实现任何功能的安全计算并具有许多优点：即在大多数情况下更直观、更安全、更高效。由于这些优势，学术界对安全基因组序列比较方法研究大多数基于通用的构造方法。
基于混淆电路的构造 基于混淆电路技术，Jha等人在半诚实模型下提出了三种安全序列比较协议。第一种协议中，电路是直接基于姚混淆电路的方法构造的。第二种协议中，对电路进行划分，每个电路的结果在参与者之间共享，以获得更好的性能。最后一种协议结合了前两种协议，并在协议效率和可扩展性方面进行了优化。这种解决方案的主要缺点是处理大规模计算任务时效率不高。Huang等人进一步优化[23]呈现的方案，减少参与方的计算开销，尽管参与方间的交互开销仍然很高。Wang等人将编辑距离问题正式定义为类似的患者查询问题，并引入了一个通用的参考序列用于基因组数据集的预处理。通过计算近似的编辑距离，大数据集序列比较的效率极大提高。然而，这种方法也引入了一些问题，第一，一个通用的参考序列导致泄露数据分布的一些信息。第二，基于参考序列执行计算会导致精度下降。近期，Zhu和Huang等研究了更广义的编辑距离算法，包括加权编辑距离，最长公共子序列和最重公共子序列算法。
基于同态加密的构造 除了上述方法，研究者也结合了同态加密和编辑距离去构造更加安全的基因组序列比较协议。编辑距离指将一个串编辑成另一个串所需的最小操作数。这个指标在生物信息学、搜索引擎、入侵检测和语音识别方面有着广泛的应用。它定量地描述两个串之间的相似性。安全地计算两个基因组序列之间的编辑距离常用的方法时采用动态规划。然而，由于动态规划算法的计算复杂度太高，基于基础方法的协议的效率都不高。利用外包计算来降低参与方的局部计算代价是提高计算效率的有效途径之一。Me等人研究了序列比较算法的安全外包方式，引入了多个服务器来分配参与方的计算任务，并构造了一个能够抵抗恶意攻击的外包协议。
六、总结
在经过30多年的SMPC研究和发展之后，SMPC的基础理论已经变得相对成熟了。研究者们已经设计出了很多理论模型。但是，最近，随着互联网技术和计算能力的提升，研究者们已经更加关注SMPC的实际应用了。不仅是通用目的的SMPC协议的效率有了极大的提升，而且也提出并研究了各种不同应用场景的SMPC模型。本概述为现有SMPC解决方案做了一个系统梳理，包括通用构造方法和云辅助安全计算，也包括具体应用协议，比如隐私保护机器学习、隐私集合运算和安全基因计算。虽然大量研究已经解决了SMPC中很多的挑战，但是还有很多值得关注的问题仍待开发。作为密码学领域中一个核心方向之一，SMPC已经在所有方面展示了强有力的身姿。SMPC本身包含的丰富理论值得不懈努力和深入研究。
