冯登国院士团队重磅论文！《具体高效的安全多方计算协议综述》解读

开放隐私计算 2022-12-10

文章简介
近日，中国科学院院士、北京信息科学技术研究院院长、中国科学院软件所客座研究员、博士生导师冯登国教授和密码科学技术国家重点实验室杨糠副教授的一篇重磅论文《Concretely eﬃcient secure multi-party computation protocols: survey and more》（《具体高效的安全多方计算协议综述》）在Security and Safety上在线发表，引发业界热烈讨论。本文是OpenMPC社区对该论文翻译后的整理介绍，仅供学习参考，欢迎交流讨论。

1全文摘要

安全多方计算(MPC)允许一组参与者在他们的私有输入上联合计算一个函数，只显示函数的输出。在过去的十年里，MPC已经从一个纯粹的理论研究迅速发展成为一个具有实际意义的研究对象，人们对隐私保护机器学习(PPML)等实际应用越来越感兴趣。本文是一篇关于“具体高效的安全多方（MPC）计算协议”的综述性文章，全面调查了在多数不诚实和多数诚实设置中，针对半诚实和恶意的两种安全性条件下具体高效 MPC 协议的现有工作。本文专注于考虑带有中止特性的安全性概念，这意味着恶意方可能会阻止诚实方在收到输出请求后完成接收输出。本文提出了基础和关键的一整套方法，设计不同风格的 MPC 协议和 MPC 的关键模块。对于 MPC 应用程序，本文比较了基于 MPC 构建的已知 PPML 协议，并描述了最先进的 PPML 协议其私有推理过程和训练的效率。此外，本文总结了几个用以突破 MPC 协议效率所存在的当前挑战和未解决的问题，以及一些值得解决的未来工作。本文的目的是向有兴趣了解、改进和应用具体高效的 MPC 协议的研究人员提供 MPC 的最新发展和关键方法。

2安全多方计算简介

安全多方计算(MPC)允许一组参与者在他们的私有输入上联合计算一个函数，而不泄露函数的输出。具体来说，MPC允许N方共同计算以下函数：

其中每一方持有一个输入，得到一个输出，除了外什么也学不到，函数通常被建模为一个布尔电路或算术电路。MPC是密码学的基础，也是大数据时代协作计算中保护数据隐私的核心技术。

安全多方计算保证隐私（意味着协议只显示输出）和正确性（意味着计算出正确的函数），以及其他（例如，输入的独立性，意味着一方不能根据其他方的输入选择其输入）。在存在对抗行为的情况下，必须保证安全属性。目前主要考虑两个经典的对手：

半诚实：半诚实的对手（又称被动对手）遵循协议规范，但可能试图从协议记录中了解更多；
恶意：恶意对手（即活动对手）可以执行任意攻击策略，试图破坏协议。

设计 MPC 协议的主要方法有两种：

秘密共享方法，它使各方为电路的每个非线性门进行交互，并且具有低通信带宽，但循环次数与电路深度呈线性关系；
乱码电路方法，让各方构建一个加密版本的电路，只允许计算一次，并且轮数恒定，但通信带宽大。

一般来说，秘密共享方法更适用于局域网（LAN）等低延迟网络，而乱码电路方法在广域网（WAN）等高延迟网络中表现更好。

3基于秘密共享的MPC协议

基于秘密共享方法，具体高效的 MPC 协议使各方能够在每个非线性门中发送短消息，但具有与正在计算的电路深度成线性关系的轮数。目前，具体高效的 MPC 协议主要采用三种线性秘密共享方案（LSSSs）：加法秘密共享、Shamir 秘密共享和复制秘密共享（又名 CNF 秘密共享），其中加法秘密共享主要用于多数不诚实设置中的 MPC 协议，而 Shamir 和复制秘密共享用于多数诚实 MPC 协议。本文首先以统一的视角回顾这些 LSSSs 的结构。为了实现应对恶意方的安全性，加法秘密共享需要配备信息论消息认证码（IT-MACs），因此本文定义了多数不诚实在 MPC 中使用的两种类型的 ITMAC。请注意，对于多数诚实设置中的 Shamir/复制秘密共享，IT-MAC 是不必要的。然后，基于 LSSSs，本文描述了如何构建具有统一结构的半诚实 MPC 协议。最后展示了如何使用最先进的检查技术将半诚实的 MPC 协议转换为恶意保护 MPC 协议。

线性秘密共享方案

MPC 中使用的三种 LSSSs 都是 -阈值秘密共享方案，它使方可以在各方之间共享秘密，使得方的任何子集都无法获得关于秘密的任何信息，而任何方的子集可以重建秘密。加性秘密共享只能在时进行，而 Shamir/复制秘密共享允许任何（对于多数诚实 MPC，通常采用。三种 LSSSs 定义在字段上。虽然加法/复制秘密共享允许任意大小的字段（包括），但 Shamir 秘密共享需要。接下来将描述这些 LSSSs 的结构以及设计 MPC 协议的有用程序。

一般的LSSSs执行流程如下：

：对于，中介生成份秘密。通过表示秘密的共享。
：这个过程只允许获得秘密。当任何份通过私有通道发送给时，秘密可以由重构。
：这个过程允许所有参与方都知道。这很容易通过执行 , 来实现，其中不需要私有通道。

信息论消息认证码

在多数不诚实设置中，MPC 协议可以使用加法秘密共享来私下执行电路评估。这对于半诚实的安全性来说已经足够了。然而，在恶意设置中，需要引入 IT-MAC 来保证秘密值的正确性。目前，在 MPC 协议中使用了两种风格的 IT-MAC：BDOZ 风格和 SPDZ 风格。虽然最初的 IT-MAC 是在单个大字段上定义的，但很容易对其进行扩展，以便在任意大小的字段上定义值，并在一个大的扩展字段上完成身份验证。

SPDZ 风格的 IT-MAC 比 BDOZ 风格的 IT-MAC 更紧凑。然而，在应用于MPC时，这两种风格的IT-MAC是无法比拟的。虽然 BDOZ 风格的 IT-MAC 更适合用于基于分布式乱码的恒定轮 MPC 协议，但 SPDZ 风格的 IT-MAC 主要用于将半诚实的 GMW 协议转换为具有恶意安全性的高效 MPC 协议。

半诚实协议

在半诚实的设置中，本文使用一个简单的框架来统一最先进的具体高效的 MPC 协议，包括 1）基于加法秘密共享的优化的 GMW 协议；2）基于Shamir秘密共享的具有优化的BGW协议；3）基于复制秘密共享的安全三方计算（3PC）协议。这里，对于基于复制秘密共享的 MPC，为了简单起见，本文重点关注三方案例。

虽然最初的 GMW 协议只考虑布尔电路，但很容易将其扩展到任何有限域上的算术电路。类似地，虽然在多数诚实设置中具有半诚实安全性的最先进的 3PC 协议专注于布尔电路的情况，但很容易将该协议扩展到任何有限域 .对于更多的参与方（例如，参与方的数量是或），可以有效地构建基于复制秘密共享的 MPC 协议。在存在半诚实的对手的情况下，类 GMW 协议和基于复制秘密共享的 MPC 协议可以直接扩展为在诸如（或）的环上工作。此外，类似 BGW 的协议基于 Shamir 秘密共享的协议也可以在通用环上工作。虽然整数计算模型对于现代计算机来说更自然，并且可能有助于简化机器学习 (ML) 等实现和应用程序。

本文展示了半诚实设置中基于秘密共享的 MPC 协议的框架，如下图所示。

具体来说，输入在各方之间秘密共享，然后逐层评估电路其中一层中的所有门都可以并行计算，因此通信轮次与电路深度成线性关系。最后，重构每一方的输出。虽然加法门在没有任何通信的情况下是免费的，但 MPC 协议的主要成本是通过执行半诚实乘法协议来计算乘法门。对于不同种类的 LSSSs，的构造方式不同。本文在下图中勾勒出的三种经典结构，对应于三种秘密共享，其中协议分为两个阶段：电路和输入未知的预处理阶段和电路和输入已知的在线阶段各方。

恶意安全协议

上述的基于秘密共享的 MPC 协议在半诚实的对手存在时保证安全。为了实现“恶意安全”，需要增加一些检查程序。在多数不诚实 MPC 和多数诚实 MPC 之间，确保抵御恶意对手安全的底层技术是不同的。例如，不诚实多数设置中的 MPC 需要 IT-MAC 来验证各方共享的值，但这对于多数诚实的 MPC 来说是不必要的。因此，本文在两种不同的设置中展示了恶意安全 MPC 的开发。

多数不诚实： Goldreich、Micali 和 Wigderson (GMW) 提出了一种通用编译器，用于将半诚实的 MPC 协议转换为恶意安全的 MPC 协议，以完成相同的计算任务。然而，这个编译器是非黑盒的，它使用通用的零知识证明来证明每一步计算的正确性，因此效率不高。后来，Ishai、Prabhakaran 和 Sahai (IPS) 提出了一种黑盒编译器，其中具有半诚实安全性的内部 MPC 协议在 OT 混合模型中计算电路，而具有恶意安全性的外部 MPC 协议在多数诚实设置用于在存在恶意对手的情况下保证整个 MPC 协议的安全性。IPS 编译器针对多方设置进行了改进，并针对两方设置进行了进一步优化。然而，基于 IPS 编译器的恶意安全 MPC 协议的具体效率仍然不够高。最近，基于 IPS 框架，Hazay 等人提出了一种使用两级共享的新编译器，其中外层是 Shamir 秘密共享或代数几何（AG）秘密共享，内层是加性秘密共享。他们的编译器允许在半诚实的 GMW 协议上具有恒定通信开销的任意大小的字段，但具体效率仍然很低。

多数诚实： 在恶意设置中，只需要检查乘法门的正确性，因为加法门是在本地计算的并且总是正确的。2017 年，Lindell 和 Nof 观察到，半诚实的协议在存在恶意对手的情况下保证了秘密值的隐私，并允许对手在输出中引入附加错误，即两个共享 , ，协议将输出一个共享，其中其中是一个附加误差。这一观察也适用于 GRR 协议和基于复制秘密共享的乘法协议。他们采用 Beaver 三元组和随机线性组合方法来检查乘法门的正确性，与半诚实协议相比，这引入了相对较大的开销。随后，Chida 等人提出了一种不同的方法来验证乘法门的正确性，其中半诚实乘法协议被执行两次，然后各方使用另一个相关的乘法三元组检查乘法门的正确性。与半诚实的协议相比，他们的 MPC 协议仍然引入了两倍的通信开销。同时，Nordholt 和 Veeningen 也实现了两倍的通信开销。在三方设置中，Furukawa 等人使用“Cut-and-Choose”方法将布尔电路的半诚实协议转换为恶意安全协议，这将引入的开销，其中是乘法门的数量，此开销小于自然重复方法，但不是最佳的。

4基于乱码电路的恒轮MPC

目前，已知的具体有效的恒轮 MPC 协议是基于乱码电路构建的，这些电路是基础电路的加密版本，只能计算一次。首先考虑半诚实协议，然后展示如何编译它们以恶意保护 MPC 协议。

半诚实协议

安全的两方计算：Yao 提出了第一个恒轮安全两方计算（2PC）协议，实现了半诚实的安全性。Yao 的 2PC 协议采用乱码电路（GC）和 OT 作为构建块。具体来说，使用乱码方案，乱码器能够生成乱码电路、编码信息和解码信息。

然后，评估器可以用评估，然后根据获得输出位。乱码方案使能够获得函数输出，但不会透露有关输入的任何其他信息。大致上，Yao 提出的具有半诚实安全性的 2PC 协议如下图所示。

2PC 协议可以使用预计算 OT 思想进一步优化，其中在预处理阶段运行随机不经意传输（ROT）协议，并在在线阶段使用选择的选择位将 ROT 转换为标准 OT。此外，GC 可以以流水线方式发送，这允许 GC 实现扩展到无限数量的门使用几乎恒定的内存。后续研究主要集中在优化2PC协议两个方面：改进GCs的构建和设计更高效的OT扩展协议。

安全的多方计算：在多方设置中，恒轮MPC必须处理多方合谋欺骗诚实方的情况。因此，不能只让一方构建乱码电路，而是让各方以分布式的方式共同构建乱码电路，使用分布式乱码方案来生成多方乱码电路。第一个分布式乱码方案由 Beaver、Micali 和 Rogaway 在 1990 年引入。基于分布式乱码，他们提出了一个在不诚实多数设置下的恒轮 MPC 协议，但该协议的具体效率非常低。令人惊讶的是，在不诚实的多数设置中，直到 2016 年，BMR 乱码才首次使用 free-XOR 技术进行优化。基于优化的BMR乱码电路，他们提出了一种具有半诚实安全性的高效恒轮MPC协议，特别是他们改进的 BMR 乱码电路。

恶意安全协议

安全的两方计算：对于恒轮 2PC 协议，在 2017 年之前，一种流行的设计恶意安全协议的方法是使用“Cut-and-Choose”（C&C）技术。使用这种技术有两种不同的风格。第一个是由 Lindell 和 Pinkas 引入并优化的电路级 C&C 方法，其中准备了许多乱码电路，打开并验证其中的随机子集，其余未经检查电路进行评估。在单执行设置中，在输入上一次计算电路，需要为统计安全性准备乱码电路，并且此设置中最有效的 2PC 协议是由 Wang 等人提出的。在不同输入上多次评估相同电路的摊销设置中，只需要准备乱码电路来对执行进行摊销，并且此设置中最著名的 2PC 协议是由 Rindal 和 Rosulek 提出的。第二种是由 Nielsen 和 Orlandi 引入并称为 LEGO 的门级 C&C 方法，其中准备了许多单独的乱码 AND 门，其中的一个随机子集被打开和验证，其余未经检查的乱码使用 XOR 同态承诺将门焊接到乱码容错电路。随后，LEGO协议进行了优化，与电路级 C&C 方法相比，门级 C&C 方法具有较低的渐近复杂度，并支持电路和输入均未知的函数无关预处理（不支持此类预处理）通过电路级 C&C 方法，但在摊销设置中效率较低，并且在单执行设置中的某些功能的效率也较低。2017 年，Wang、Ranellucci 和 Katz 的里程碑式工作提出了构建高效 2PC 协议的认证乱码方法，其中构建和传输单个“认证”乱码电路。

安全的多方计算：在多数不诚实设置中，对于容忍非一个恶意破坏的恒定轮次 MPC 协议，一些研究采用剪切和选择方法或 BMR 和 SPDZ 的组合方法来构建 MPC 协议。但是，它们的具体效率非常低。在这种情况下，最著名的 MPC 协议遵循基于 TinyOT 类协议的分布式乱码框架。这些 MPC 协议与 2PC 协议具有相同的结构，但需要执行一致性检查程序来检查多次执行之间共享或全局密钥的一致性。最近，Poddar 等人应用具有恶意安全性的恒定轮次 MPC 协议构建了一个称为参议院的系统，该系统允许方协作运行分析 SQL 查询，同时保持个人数据的私密性。Yang等人提出了具有恶意安全性的最先进的常量轮MPC协议，并可用于进一步提高上述应用程序的性能。虽然半门优化完全应用于两方设置中的分布式乱码构建，但这仅在多方设置中部分完成。将半栅技术（甚至最近的切片和切割技术）完全应用于多方乱码电路是一个挑战。

在多数诚实设置中，可以使用较少的通信和计算基于复制的秘密共享来构建恒定轮次 MPC 协议。在最多一个恶意方的三方设置中，Mohassel 等人通过构建单个 Yao 式的乱码电路，提出了目前最有效的三轮 3PC 协议，其中恶意安全的 3PC 协议与半诚实的 Yao 的 2PC 协议具有基本相同的成本。同时，Ishai 等人构建了一个两轮3PC协议，同时需要发送三个乱码电路。在最多有一次恶意破坏的四方设置中，Byali 等人提出了最先进的协议，并且有五轮通信，需要发送一个单Yao式的乱码电路。该协议可以实现更强的安全属性，即GOD。在最多有两个恶意破坏的五方设置中，Chandran 等人提出了最著名的 MPC 协议，进行了 8 轮通信。他们采用 BMR 乱码电路来防止串通，并提出了一种经过验证的 OT 原语，使整个 MPC 协议只依赖于对称密钥原语，而不需要 OT 协议。在通信成本方面，它们的恶意安全协议比不诚实多数的半诚实 MPC 协议减少 60%，而其半诚实变体需要的通信减少 8 倍。他们的构造也可以扩展到阈值的方。后来，Byali等人构建了具有公平性或 GOD 的安全五方计算 (5PC)，其开销比 5PC 协议的开销小，满足中止的安全性。

5不经意转移和不经意线性函数评估

不经意转移

不经意传输 (OT) 是发送者和接收者之间的基本密码原语，它使只能获得的两个输入消息之一，而在的选择位上一无所知。它不仅可以用来构造Yao氏的2PC协议，还可以用来构造许多其他具有半诚实和恶意安全的MPC协议。此外，OT还可以用来设计很多其他种类的密码协议。OT 协议可以从不同的加密假设构建，包括决策 Diﬃe-Hellman (DDH) 、计算 Diﬃe-Hellman (CDH) 、学习错误 (LWE) 、学习奇偶噪声 (LPN) 和交换超奇异同源 Diﬃe-Hellman (CSIDH) 。但是，当需要生成大量的 OT 关联时（特别是对于 MPC 应用），这些基于公钥操作的 OT 协议是非常昂贵的。为了解决这个问题，Beaver 引入了 OT 扩展的概念，其中使用快速运算将少量基本 OT 有效地扩展到大量 OT（甚至是任何多项式数量的 OT）。Beaver的第一个 OT 扩展协议以非黑盒方式使用伪随机生成器 (PRG)，因此仅在理论上有意义。目前，具体有效的 OT 扩展协议分为两种风格：一种基于 IKNP 框架，另一种基于 PCG 框架。IKNP 风格的协议采用对称密钥原语 PRG 进行扩展并支持选择位，而 PCG 风格的协议利用 LPN 问题中噪声的稀疏特性来实现扩展，只允许随机选择位。

不经意线性函数评估

OLE： 不经意线性函数评估 (OLE) 是 OT 的算术推广，特别适用于为大范围的算术电路设计 MPC 协议。特别是，OLE 直接给出了两个秘密值相乘的两方加法共享。因此，通过成对的 OLE 协议执行，可以在多方设置中使用 OLE 生成 Beaver 乘法三元组而无需验证。OLE 可以使用 OT 扩展和 Gilboa 乘法方法构建，计算成本低，但通信成本高。存在一种使用基于 RLWE 的加性同态加密 (AHE) 设计 OLE 的标准方法，该方法已用于 Overdrive 和最近的工作，其中接收器将发送到发送器，并且然后计算并将其发送给，解密以获得大场的。这里，AHE 需要满足电路隐私财产。此外，OLE 也可以从某种同态加密构建，但需要更大的通信。在不依赖同态加密的情况下，OLE 也可以直接从 Ring-LWE构建。此外，还可以从 OT 和嘈杂的 Reed-Solomon 编码或 Paillier 加密构建 OLE 协议。在所有 OLE 协议中，基于 AHE 的协议获得了最佳的通信效率，而来自 RLWE 的协议具有最优的一轮通信。

最近，Boyle等人提出了一种直接基于 LPN 的 OLE 结构，其通信成本比上述 OLE 协议低得多，但需要至少的计算成本来生成个 OLE 相关性。后来，他们使用环 LPN 假设的变体解决了计算问题，并构建了用于计算大量 OLE 相关性的 OLE 协议。该 OLE 协议比基于 RLWE 的协议具有非常低的通信成本，并且提供了的计算复杂度。他们基于 ring-LPN 的 PCG 方法是生成大量 OLE 相关性的好方法（例如，）。对于少数 OLE 相关性，基于 RLWE 的方法可能更好。基于 ring-LPN，得到的 OLE 相关性是随机的（即是一致随机的），但足以设计 MPC 协议，其中在预处理阶段只需要生成随机乘法三元组。

VOLE： 向量不经意线性函数评估 (VOLE) 是 COT 对大域的算术推广，定义如下：

发送者持有一个统一的全局密钥。
对于每个 VOLE 执行，发送者获得一个向量，接收者获得两个向量，使得。

6MPC在机器学习中的应用

机器学习 (ML) 的最新进展推动了许多现实生活中的应用，例如医疗保健、金融风险分析、面部识别、自动驾驶汽车的图像和视频分析、推荐系统、文本翻译、语音助手、图像分类等。对于关键任务应用程序（例如医疗保健），所需的准确度水平很高。准确性主要受两个因素控制：1）训练深度学习模型所需的大量计算能力；2）数据集的差异，来自于从多个不同来源收集数据，单个公司通常无法实现。

为此，多家公司（例如，微软、亚马逊、谷歌）提供机器学习即服务（MLaaS），它以以下两种不同的方式工作：

推理：公司提供经过训练的 ML 模型，客户能够查询特征输入以获得推理结果。
训练：多家公司合作使用他们的数据集训练一个高精度模型。

在第一种情况下，公司希望对 ML 模型保密，因为训练模型可能需要大量资金，并且客户希望保护其输入的隐私，其中输入信息可能是敏感的，例如个人健康数据或人脸。在第二种情况下，公司不愿意共享他们的数据，因为数据是公司的专有信息，这些公司可能具有竞争力，并且由于隐私法而被禁止共享客户信息。在这里，ML 模型是保密的，这意味着模型参数是隐藏的，但模型结构（例如，使用了哪些函数）仍然是已知的。在保持 PPML 具体高效的同时保护模型结构的隐私是一项挑战。

因此，为了解决机器学习应用中的上述隐私问题，隐私保护机器学习（PPML）是非常可取的，并且已经成为一个蓬勃发展的研究领域。特别是，PPML 允许对私有数据进行 ML 计算，同时确保数据的隐私性。由于隐私保护的要求，PPML使得已经是计算密集型的机器学习算法在高计算能力和大通信成本方面要求更高。然而，许多日常用户没有这样的计算和通信能力来执行 PPML。因此，用户将 ML 任务以按使用付费的方式安全地外包给一组强大且专业的云服务器可能是经济且方便的，其中台服务器中最多台服务器串通作弊时，安全性得到保证（根据使用的具体 MPC 协议，或）。在这种情况下，可以通过以下方式实现推理和训练：

外包推理：公司可能以秘密共享的方式将其训练有素的 ML 模型托管到个（不受信任的）服务器上。客户可以在相同的个服务器之间秘密地共享其特征输入。服务器可以以共享方式计算推理结果并将结果返回给客户。
外包培训：多家公司可以秘密地将他们的数据集共享给一组（不受信任的）服务器，这些服务器在他们的联合数据集上合作训练一个通用模型，同时保持他们个人数据集的私密性。

MPC 是实现 PPML 的关键技术之一，是在上述基于秘密共享的外包计算环境中执行 PPML 最有前途的方法。一系列 PPML 协议已经建立在 MPC 技术之上。可以将这些 PPML 协议分为两类：一类是多数不诚实设置，另一类是多数诚实设置。本文调查了基于 MPC 的已知 PPML 协议，并在下表中进行了比较。

上表中显示的所有 PPML协议以及其他PPML 协议都通过以下方式定制：

基于已知的 MPC协议，改进ML算法，使其对 MPC更加友好。
根据机器学习算法的定义，剪裁已知的MPC协议。

这些定制的 PPML 协议可以为特定的学习任务获得高效率。最近，Zheng等人为通用 ML 任务的隐私保护训练和推理设计了一个平台，该平台支持新的神经网络架构，但效率较低。

在多数不诚实设置中，PPML 协议侧重于两方情况，除了Helen和Cerebro 两个协议。Helen和Cerebro分别在4方和 2-12方之间实现了 ML算法的推理和训练，并允许对手是半诚实的或恶意的。对于容忍 11 次半诚实损坏的 12 方，最近的PPML协议Cerebro 可以在大约 20 秒的平均时间内执行 12 层的决策树推理。在六方半诚实设置中，Cerebro可以在16分钟左右实现逻辑回归训练，在 100 秒左右实现线性回归训练。根据 Cerebro 中的实验结果，恶意安全 PPML 协议比半诚实版本慢 61-3300 倍。在不诚实多数的多方设置中，用于 ML 推理的模型很小，用于 ML 训练的数据集和神经网络架构也很小。需要利用更多的效率优化来支持更大的数据集和模型。恶意安全协议需要进一步改进，以减少半诚实协议的开销。现在将注意力转向两方案例。大多数两方 PPML 协议都认为是半诚实的对手。唯一的例外是 QuantizedNN，它使用 SPDZ2k 和 Overdrive 来设计恶意安全协议，其中 SPDZ2k 和 Overdrive 已在 MP-SPDZ 库中实现。他们的恶意安全协议大约比半诚实协议慢 3-9 倍。在半诚实的两方设置中，除了 SecureML 和 QUOTIENT 之外，大多数 PPML 协议都专注于ML推理。然而，SecureML 和 QUOTIENT 只实现了具有 60000 个训练样本和 10 个不同类别的小型数据集 MNIST。对于具有半诚实安全性的两方 ML 推理，最先进的 PPML 协议 CrypTFlow2 能够在复杂的深度神经网络 (DNN) 上执行私有推理，如 ResNet-50（50 层，2350 万参数）和 DenseNet121（121 层，850 万个参数），可以在包含超过 1000000 个训练样本和 1000 个不同类别的大规模数据集 ImageNet 上进行训练。他们的实现对于 ResNet-50 需要大约 546 秒和 32 GB 的通信，对于DenseNet-121 需要 463 秒和 35 GB 的通信。在两方设置中，对于具有半诚实安全性的 ML推理似乎效率很高，但针对恶意对手的 ML推理和ML训练仍然效率较低，这需要在未来的工作中加以解决。

在多数诚实设置中，已知的PPML协议仅考虑三方和四方情况容忍一个恶意方。在这种情况下，可以实现相对较高的私有推理和训练效率。通过使用 GPU加速半诚实的3PC，CryptGPU可以使用 9.3 s 和3.1 GB的通信（分别为 25.8 s 和 6.6 GB 通信）。CryptGPU 实现的私有训练能够支持 VGG-16（16 层，1.38 亿参数），它是在包含100000个训练样本和 200 多个不同类的 Tiny ImageNet 数据集上训练的。他们的实现报告了单次私人训练迭代的运行时间和通信，分别为13.9 s和7.6GB。对于恶意安全，最著名的PPML协议 Falcon 可以在使用Tiny ImageNet训练的神经网络 VGG-16 上运行私有推理，运行时间为12.1秒，通信量为 0.4 GB。然而，具有恶意安全性的Falcon 需要3 年多的时间和大约 012TB的通信才能在 Tiny ImageNet 数据集上训练VGG-16 模型。当大多数方是诚实的时，多个PPML协议也可以使用少量开销实现比中止安全性（即公平性和 GOD）更强的安全性。在这种情况下，四方设置中的PPML协议比三方设置中的性能更好，但需要对诚实方的数量进行更强的假设。在这些实现公平或GOD的PPML协议中，Tetrad拥有目前具有最好的效率。特别是，Tetrad在包含50000 个训练样本和10个不同类别的小型数据集 CIFAR-10上训练VGG-16模型需要183秒和35GB的通信量。总体而言，在三方/四方设置中，私有推理是实用的，并且可以扩展到复杂的模型和大型数据集，即使存在恶意对手。在相同的设置中，私人训练提供了高效率并支持中等大小的数据集以实现半诚实的安全性，但对于恶意安全性的效率非常低。此外，设计具有至少五方和两个腐败方的诚实多数PPML协议将是一项有趣的未来工作。

对于 ML应用程序，需要处理多种不同类型的函数。例如，在DNN中，需要为线性层计算矩阵乘法、卷积等，为非线性层计算ReLU、Max Pooling、Sigmoid、SoftMax 等。因此，需要构建混合模式的MPC协议，它既支持算术电路又支持布尔电路，并允许在算术电路和布尔电路之间进行转换。此外，对于除法运算或表示为具有较大深度的电路的功能，可能需要使用乱码电路的方法来实现更好的效率。在多数不诚实设置中，类ABY协议开发了在半诚实对手存在的情况下实现算术共享、布尔共享和Yao的GC之间的转换的技术。ABY 类协议侧重于在两方之间执行电路评估的情况。在多方设置中，最近的工作提出了半诚实协议，以支持算术共享、布尔共享、Yao氏GC以及任意两个表示之间的转换。然而，他们的协议需要一个可信方来在评估电路的各方之间分配所有相关的随机性，这使得协议的安全保证较弱。对于恶意安全，分布式乱码电路和SPDZ风格的认证共享之间的转换可以使用双重认证位 (daBits) 技术或更有效的扩展 daBits (edaBits) 技术来实现。具体来说，一个 daBit 由一对随机共享 () 组成，其中并且对于素数或者或者。DaBits 技术首先由Rotaru 和Wood 提出，用于的情况。然后，最新工作中的情况下，性能进一步提高，并且环上的 daBits也显示在工作中，其中已知的实现大约需要11.8 KB用于生成一个具有大质数的 daBit，在双方恶意设置中每秒可以生成约2150个daBit。最先进的 edaBits 协议采用“Cut-and-Bucketing”技术来检查两个不同域中值的一致性，其中 edaBit 由一组随机共享（) 在二进制域中和在算术域中共享，使得 mod . 在两方恶意设置，与daBits技术相比，edaBits方法将实现63位整数比较的通信成本降低2倍。用于恶意安全的“Cut-and-Bucketing”技术导致的开销至少是半诚实协议的3 倍。构建一个具有恶意安全性的具体有效的edaBits协议是一个有趣的开放问题，它实现了2甚至更小的开销。在多数诚实设置中，可以更有效地构建针对恶意对手的协议，这些协议允许在算术、布尔和乱码世界之间进行转换，其中基于常量轮 MPC协议的技术可以使用和调整。

另一方面，Boyle 等人最近的研究提出了一种基于功能秘密共享 (FSS) 构建混合模式 MPC 协议的新方法，这对于具有最佳在线通信和回合复杂度的 ML 应用程序很有用。他们的 FSS 方法支持与非算术运算混合的算术运算。特别是，对于 ReLU 等非算术函数，两方可以获得两个简洁的FSS密钥来评估函数，其中是双方共享的随机性。一般来说，基于FSS的方法在预处理阶段需要比GC或GMW方法更多的通信，除非FSS密钥由受信任的经销商分发，或者输入长度相对较小。这自然留下了未来的工作，以减少通过具体有效的2PC协议分发FSS密钥的预处理成本。对于在线通信成本和回合数，基于FSS的方法优于GC和GMW方法。他们基于FSS的方法也可以抵御恶意对手。目前，Boyle等人仅提出了用于函数的有效构造，包括比较（例如，ReLU）、样条（例如，用于sigmoid）、位分解、零测试和算术/逻辑移位。ML 和科学计算中仍然使用许多函数（例如，取幂、tanh和平方根的倒数），其具体有效的基于FSS的2PC协议是未知的。此外，Boyle等人只给出了两方结构。构建具有最佳在线通信和多方回合（即）的具体高效的基于FSS的MPC协议是一项有趣的未来工作。虽然先前的工作对整个ML推理使用统一的位宽，但Rathee等人最近的工作提出了混合位宽方法，即在低位宽下运行，仅在必要时才使用高位宽。他们设计了新的协议来切换位宽和对不同位宽值的操作。他们的方法很有趣，并且能够获得更好的效率。虽然有工作仅考虑两方设置中的私有ML推理，但值得进一步开发用于私有ML训练和多方设置的混合位宽方法。

7总结与展望

本文已经描述了（最近）具体高效的MPC协议的发展以及这些MPC协议背后的关键技术。特别是，本文介绍了最近的 MPC协议和 OT/OLE 协议中的高级思想。作为MPC应用的一个例子，本文讨论了隐私保护机器学习，并总结了相关工作以及转换和基于FSS的技术。希望本次调查能够帮助新的研究人员（对MPC感兴趣）快速了解具体高效 MPC的最新发展，并初步了解一些关键技术，作为MPC研究的起点。

要大规模部署MPC，标准化是必要的一步。然而这并不是一件容易的事，因为存在许多不同类型的MPC协议，它们在安全性和效率方面具有不同的优势。此外，在MPC的设计中使用了许多技术和不同的假设。这些使MPC标准化程序变得困难。当然，可以先在同一个设置中标准化一批 MPC协议，然后在另一个设置中标准化下一批。当标准化是一个长期的过程并且需要占用大量的财力资源时，这种方法非常昂贵。此外，如何在不同的标准化过程中保持多种 MPC协议的兼容性是一个问题。这些都需要在今后的工作中加以解决和解决。最近，ISO正在准备基于秘密共享的MPC标准化过程。此外，NIST 将在未来标准化多方阈值密码学，其中 MPC是实现 AES 加密/解密、EdDSA 签名、RSA的分布式密钥生成等的关键技术。NIST 也打算伴随这一进展隐私增强密码学领域的新兴技术，包括 MPC、ZK、HE 等。

本文在前面的章节中总结了一些未解决的问题和未来的工作。本文将通过进一步列出几个开放问题和未来针对具体高效的 MPC 协议的工作来结束这项工作。

恒轮2PC： Rosulek 和Roy 最近的突破性工作将乱码电路的大小从每个AND 门的位减少到每个AND 门的位。一个自然的开放问题是是否可以做得更好，例如，每个 AND 门大约位，同时保持与自由 XOR 的兼容性和高计算效率。如果这似乎是不可能的，可以尝试证明每个 AND 门 ≈ 位在线性乱码模型更具包容性的模型中是最优的。当关注半诚实的对手时，另一个悬而未决的问题是将切片和切块技术扩展到两方分布式乱码，可用于设计恶意安全的2PC协议，方法是结合BDOZ 风格的 IT-MAC。

恒轮MPC： 本文总结了设计恒轮MPC 的三项未来工作。

乱码的多数不诚实：对于仅基于对称原语的多方分布式乱码，Yang 等人的最新技术在乱码电路的大小方面实现了位。基于仍然对称的原语将其进一步减少到大约位是一项具有挑战性的任务。换句话说，半门技术是否可以完全应用于多方分布式乱码？
AND 三元组的多数不诚实：目前，使用类似 TinyOT 的协议来生成经过身份验证的 AND 三元组，这需要至少 3 的开销才能实现相对于相应的半诚实协议的恶意安全性，其中开销来自分桶技术的使用。这是一个有趣的开放问题，它使用一种新技术设计了一个经过身份验证的三重协议，实现了 2（甚至更小）的开销。
多数诚实：如果当事方数量，Chandran 等人提出了一个带有损坏阈值的恒轮 MPC 协议。当时，构建一个能够容忍个损坏方的恒轮具体高效 MPC 协议是一项有趣的未来工作。

SPDZ： SPDZ 式协议的效率瓶颈是在大范围内生成经过身份验证的三元组。基于环形 LPN 假设的变体的最先进的协议获得了相对较低的通信复杂度，比 Overdrive 小两个数量级。然而，该协议的编码计算复杂度为（同时使用快速傅里叶变换），这对于大来说很大，其中是生成的经过身份验证的三元组的数量。未来的一项重要工作是降低计算复杂度，同时保持基于环LPN协议的较小通信复杂度。
MPC 的 LPN 变体： COT和OLE及其变体是多数不诚实设置中MPC的关键构建块。为了设计低通信的COT和(V)OLE协议，已经提出了几种LPN变体，包括具有规则噪声分布的LPN、具有静态泄漏的LPN 、具有可约多项式的环LPN和规则的噪声分布。一项重要的未来工作是进一步分析在 MPC 上下文中提出的LPN变体，这可以对这些LPN问题的难度建立更多的信心。
多数诚实的大规模 MPC： 对于恶意环境中的诚实多数MPC，最近的几项工作设计了大规模MPC协议，实际上可以扩展到数十万方。但是，它们的具体效率仍然不高。构建具有更高具体效率的大规模恶意安全MPC协议以及为数千方提供有效的实施扩展将是一项有趣的未来工作。

原文链接：
https://sands.edpsciences.org/articles/sands/full_html/2022/01/sands20210001/sands20210001.html
引用格式：
Feng D and Yang K. Concretely efficient secure multi-party computation protocols: survey and more. Security and Safety 2022; 1: 2021001. https://doi.org/10.1051/sands/2021001
期刊介绍：
Security and Safety (S&S)致力于快速报道多个领域中涉及网络安全与功能安全共性交叉的具有创新性和应用性的高水平研究成果。
期刊网址：https://sands.edpsciences.org