文章简介
 

近日，中国科学院院士、北京信息科学技术研究院院长、中国科学院软件所客座研究员、博士生导师冯登国教授和密码科学技术国家重点实验室杨糠副教授的一篇重磅论文《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 协议的主要方法有两种：

    秘密共享方法，它使各方为电路的每个非线性门进行交互，并且具有低通信带宽，但循环次数与电路深度呈线性关系；

    乱码电路方法，让各方构建一个加密版本的电路，只允许计算一次，并且轮数恒定，但通信带宽大。

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

    3基于秘密共享的MPC协议

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

    线性秘密共享方案

    信息论消息认证码

    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，为了简单起见，本文重点关注三方案例。

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

    恶意安全协议

    上述的基于秘密共享的 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 协议上具有恒定通信开销的任意大小的字段，但具体效率仍然很低。

    4基于乱码电路的恒轮MPC

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

    半诚实协议

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

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

    恶意安全协议

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

    不经意转移

    6MPC在机器学习中的应用

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

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

    推理：公司提供经过训练的 ML 模型，客户能够查询特征输入以获得推理结果。

    训练：多家公司合作使用他们的数据集训练一个高精度模型。
 

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

    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协议将是一项有趣的未来工作。

    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 协议的工作来结束这项工作。

    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