论文作者为中国科学院院士、北京信息科学技术研究院院长、中国科学院软件所客座研究员、博士生导师冯登国教授和密码科学技术国家重点实验室杨糠副教授。本文为开放隐私计算社区整理，分享仅供学习参考，如有转载，请标记出处。
文章简介
近日，中国科学院院士、北京信息科学技术研究院院长、中国科学院软件所客座研究员、博士生导师冯登国教授和密码科学技术国家重点实验室杨糠副教授的一篇重磅论文《Concretely efficient secure multi-party computation protocols: survey and more》（《具体高效的安全多方计算协议综述》）在Security and Safety上在线发表，引发业界热烈讨论。本文是OpenMPC社区对该论文翻译后的整理介绍，仅供学习参考，欢迎交流讨论。
安全多方计算(MPC)允许一组参与者在他们的私有输入上联合计算一个函数，只显示函数的输出。在过去的十年里，MPC已经从一个纯粹的理论研究迅速发展成为一个具有实际意义的研究对象，人们对隐私保护机器学习(PPML)等实际应用越来越感兴趣。本文是一篇关于“具体高效的安全多方（MPC）计算协议”的综述性文章，全面调查了在多数不诚实和多数诚实设置中，针对半诚实和恶意的两种安全性条件下具体高效 MPC 协议的现有工作。本文专注于考虑带有中止特性的安全性概念，这意味着恶意方可能会阻止诚实方在收到输出请求后完成接收输出。本文提出了基础和关键的一整套方法，设计不同风格的 MPC 协议和 MPC 的关键模块。对于 MPC 应用程序，本文比较了基于 MPC 构建的已知 PPML 协议，并描述了最先进的 PPML 协议其私有推理过程和训练的效率。此外，本文总结了几个用以突破 MPC 协议效率所存在的当前挑战和未解决的问题，以及一些值得解决的未来工作。本文的目的是向有兴趣了解、改进和应用具体高效的 MPC 协议的研究人员提供 MPC 的最新发展和关键方法。
安全多方计算(MPC)允许一组参与者在他们的私有输入上联合计算一个函数，而不泄露函数的输出。具体来说，MPC允许N方共同计算以下函数：
其中每一方持有一个输入，得到一个输出，除了外什么也学不到，函数通常被建模为一个布尔电路或算术电路。MPC是密码学的基础，也是大数据时代协作计算中保护数据隐私的核心技术。
安全多方计算保证隐私（意味着协议只显示输出）和正确性（意味着计算出正确的函数），以及其他（例如，输入的独立性，意味着一方不能根据其他方的输入选择其输入）。在存在对抗行为的情况下，必须保证安全属性。目前主要考虑两个经典的对手：
设计 MPC 协议的主要方法有两种：
一般来说，秘密共享方法更适用于局域网（LAN）等低延迟网络，而乱码电路方法在广域网（WAN）等高延迟网络中表现更好。
基于秘密共享方法，具体高效的 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”方法将布尔电路的半诚实协议转换为恶意安全协议，这将引入 的开销，其中 是乘法门的数量，此开销小于自然重复方法，但不是最佳的。
目前，已知的具体有效的恒轮 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 协议的开销小，满足中止的安全性。
不经意传输 (OT) 是发送者 和接收者 之间的基本密码原语，它使 只能获得 的两个输入消息之一，而 在 的选择位上一无所知。它不仅可以用来构造Yao氏的2PC协议，还可以用来构造许多其他具有半诚实和恶意安全的MPC协议。此外，OT还可以用来设计很多其他种类的密码协议。OT 协议可以从不同的加密假设构建，包括决策 Diffie-Hellman (DDH) 、计算 Diffie-Hellman (CDH) 、学习错误 (LWE) 、学习奇偶噪声 (LPN) 和交换超奇异同源 Diffie-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 对大域的算术推广，定义如下：
机器学习 (ML) 的最新进展推动了许多现实生活中的应用，例如医疗保健、金融风险分析、面部识别、自动驾驶汽车的图像和视频分析、推荐系统、文本翻译、语音助手、图像分类等。对于关键任务应用程序（例如医疗保健），所需的准确度水平很高。准确性主要受两个因素控制：1）训练深度学习模型所需的大量计算能力；2）数据集的差异，来自于从多个不同来源收集数据，单个公司通常无法实现。
为此，多家公司（例如，微软、亚马逊、谷歌）提供机器学习即服务（MLaaS），它以以下两种不同的方式工作：
推理：公司提供经过训练的 ML 模型，客户能够查询特征输入以获得推理结果。
训练：多家公司合作使用他们的数据集训练一个高精度模型。
在第一种情况下，公司希望对 ML 模型保密，因为训练模型可能需要大量资金，并且客户希望保护其输入的隐私，其中输入信息可能是敏感的，例如个人健康数据或人脸。在第二种情况下，公司不愿意共享他们的数据，因为数据是公司的专有信息，这些公司可能具有竞争力，并且由于隐私法而被禁止共享客户信息。在这里，ML 模型是保密的，这意味着模型参数是隐藏的，但模型结构（例如，使用了哪些函数）仍然是已知的。在保持 PPML 具体高效的同时保护模型结构的隐私是一项挑战。
文章导读： 论文作者为中国科学院院士、北京信息科学技术研究院院长、中国科学院软件所客座研究员、博士生导师冯登国教授和密码科学技术国家重点实验室杨糠副教授。本文为开放隐私计算社区整理，分享仅供学...