优化互联网中的半诚实安全多方计算

陆叁 2021-11-06

446

点击上方蓝字获取更多新鲜资讯

写在前面

今天为大家带来的是《Optimizing Semi-Honest Secure Multi-party Computation for the Internet》的文章解读，该篇文章由Lindell等人，在2016年发表在CCS '16。

为什么要解读这篇文章呢？其实根本原因是作者没有读过BMR协议，在看Motion 的多方 Yao's share 时，非常痛苦，所以，回过头来看了这篇文章。如果有像我一样情况的小伙伴，可以把本系列文章作为一个参考。当然，还是鼓励阅读原文。

多啰嗦一句，本篇文章还是非常值得读的，读过后，对于在Yao' GC会有一个更深的认知。另外，能够学习到，在什么场景下，适用什么类型的MPC协议。

摘要

在安全的多方计算的设定中，一组拥有私人输入的各方希望在不透露任何东西的情况下计算他们的输入的某些函数，但不透露他们的输出。在过去的十年里，安全的两方计算的效率有了飞跃性的进步，其速度提高了几个数量级，使其快到足以在实践中使用。相比之下，多方计算（有两方以上）的进展要慢得多，所做的工作非常少。目前，唯一实现的高效的多方协议有许多轮的通信（与正在计算的电路的深度成线性关系），因此不适合于延迟比较高的类似互联网的环境。

在本文中，我们为半诚实对手的多方计算的设置构建了高效的恒定回合协议。我们的协议通过构建一个多方乱码电路来工作，正如 BMR（Beaver等人，STOC 1990）中提出的那样。我们的第一个协议使用不经意传输，并构成了第一个针对无诚实多数情况的具体有效的恒定回合多方协议。我们的第二个协议使用BGW，比同样使用BGW的FairplayMP协议（Ben-David等人，CCS 2008）效率高得多。

我们进行了广泛的实验，将我们不同的协议相互比较，并与半诚实的GMW的高度优化的实现进行比较。由于我们的协议是恒定回合的，它在类似互联网的环境中明显优于GMW。例如，13个当事方位于弗吉尼亚和爱尔兰亚马逊地区，SHA256电路有90000个门，深度为4000，我们协议的整体运行时间为25秒，而GMW为335秒。此外，我们的在线时间低于半秒，而GMW为330秒。

1. 引言

1.1 背景知识

在安全多方计算(MPC)的设置中，一组当事人希望计算他们的私人输入的联合函数，而不透露任何东西，只有输出。安全计算的协议在存在对抗行为的情况下，保证隐私(指协议除了输出外什么都不透露)和正确性(指计算出正确的函数)。有两种典型的敌手模型通常被认为是：半诚实的（敌手遵循协议规范，但可能试图从协议记录中了解更多允许的内容）和恶意的（敌手可以运行任何任意的多项式时间策略来试图破坏安全）。在本文中，我们专注于多方设置和半诚实的敌手。我们的重点是为这种情况构建具体有效的协议（这里的 "具体有效 "是指在实践中运行时间更快）。

安全计算的两种范式

有两种主要的范式来构建可用于安全地计算任何函数的一般安全的双方和多方计算协议。GMW(GoldreichMicali-Wigderson)范式[15]的工作方式是让各方互动计算电路中的每一个(AND)门(这种方法也被用于信息论协议和算术电路)。这样的协议通常每个门发送的带宽非常少，但会受到多轮通信的影响，在电路的深度上是线性的。因此，它们在局域网环境中非常快，但在互联网上进行通信时却非常慢。与此相反，在乱码电路范式[32]中，整个电路的构造方式使其能够在不透露任何东西的情况下被评估（除了输出）。姚[32]的原始构造只对两方有效，而多方乱码电路的概念后来由BMR（BeaverMicali-Rogaway）在[5]中展示。这样的协议在局域网环境中通常较慢，因为它们需要更多的带宽，但在互联网等较慢的网络上有可能更快，因为它们有恒定的轮数。

具体的效率和过去的十年

安全的双方计算在过去十年中取得了飞跃性的进展。它已经从一个只有理论意义的概念，发展成为一项甚至被多家公司商业化的技术。为了证明这一进展，我们回到2004年Fairplay[29]中姚氏乱码电路的首次实现。在这篇论文中，他们在一个总体上有4383个门的 "大电路 "上运行了安全计算，在有半诚实的敌手的情况下是安全的。在一个局域网上，他们的协议运行时间为7.09秒。2014年，在一个大约5倍于此的电路上运行一个类似的执行，需要大约16毫秒，该电路的门数超过22000个，其中6800个是AND门[17]。请注意，摩尔定律（说计算能力每两年翻一番的版本）只能说明32倍的速度提升。这一惊人的进展是由于一系列专注于该问题的所有加密和算法方面的工作，以及以AES-NI 等形式出现的无处不在的加密硬件加速；一些例子见[25，20，18，3，6，31，33]。目前的情况是，我们现在对实践中安全的两方计算的成本有了非常好的理解。

我们强调，这些工作不仅在对半诚实敌手安全的协议方面取得了令人印象深刻的进展，而且也推动了对恶意敌手安全的协议的进展。特别是，用于加快乱码电路生成和评估的技术和方法被直接纳入恶意敌手的协议中，半诚实情况下的快速OT扩展成为恶意情况下的快速OT扩展的基础。

类似地，第一个实现多方协议（有两方以上）的是 2008 年的 FairplayMP [7]，它采用了 [5] 的多方乱码电路方法。他们计算的最大电路有1024个门，运行协议的时间从5方的约10秒到10方的55秒不等。2012年，[10]为多方设置实现了GMW协议。对于一个有5500个AND门的电路（大约是FairplayMP的5倍），他们报告的时间从5方的约7秒到10方的约10秒不等。

令人惊讶的是，据我们所知，对于半诚实的敌手和不诚实多数的情况，没有其他关于通用（基于电路）多方安全计算的工作。

特别是，自FairplayMP以来，多方乱码电路方法没有任何改进，而且运行多方计算所需的时间比双方计算要多出几个数量级。此外，FairplayMP协议只对诚实的大多数是安全的。因此，对于不诚实大多数半诚实敌手的情况，还没有描述或实现过具体有效的恒定回合多方协议。

我们指出，许多应用都需要多方设置，如拍卖、交易、选举、隐私保护调查等等。因此，我们认为，纠正目前高效的多方计算远远落后于高效的双方计算的情况是非常重要的。

1.2 贡献

在本文中，我们研究了有半诚实对手的多方计算问题。我们有三个主要贡献:

我们提出了第一个具体有效的恒定回合多方协议，该协议对任何数量的腐坏方 (corrupted parties) 都是安全的。我们的协议是基于[5] 的多方乱码电路方法，并要求每一方在每个门上与其他每一方进行不经意传输，以构建乱码电路。
继FairplayMP[7]之后，我们也提出了基于BGW[8]（BenOr-Goldwasser-Wigderson）的构建多方乱码电路的协议，这些协议对于诚实的大多数来说是安全的。我们的协议比 [7] 中提出的协议要有效得多。
我们进行了广泛的实验，比较了我们不同协议之间以及多方GMW之间的性能。我们在3个不同的网络上进行了实验，有不同数量的参与方，也有不同的电路。我们的结果加深了我们对回合复杂性对效率影响的理解，以及哪些协议适合低延迟和高延迟网络。

我们的协议对于半诚实的敌手都是安全的。当各方在一定程度上信任对方，但担心无意中的泄漏或由于隐私规定不能分享他们的原始信息时，半诚实的安全性是足够的。在可以合理地假设运行协议的各方无法替换已安装的代码的情况下，它也是足够的。尽管如此，针对恶意敌手的安全性是最好的，可以提供高得多的保证。然而，这种协议的效率总是要低得多。此外，我们认为，获得针对恶意对手的高效协议的第一步是了解半诚实的情况以及如何使其变得非常高效。两方计算的情况确实如此，为半诚实情况进行的优化和工作是为恶意对手情况获得高效协议的一个重要因素。

在继续之前，我们要说明的是，多方案例中的乱码电路方法与双方案例中的乱码电路方法有根本的不同，并引入了许多困难。在双方的情况下，一方构建乱码电路，另一方对其进行评估。因此，构建和评估乱码电路的计算是局部的。相反，在多方的情况下，一方不可能自己构建乱码电路。这是因为，如果该方与评估电路的一方串通，那么各方的输入都会被暴露（因为构建电路的一方知道所有的密钥）。相反，所有各方都有必要通过一个安全的协议合作构建电路。因此，这种方法的有效实例需要

一种有效的乱码电路方法，和
一种有效的协作生成方式。

请注意，乱码电路的构建（这是协议中比较昂贵的部分）可以在一个离线阶段进行。然后，一旦收到输入，在线阶段可以用非常少的通信来运行，只是对多方乱码电路进行局部评估。

现在我们将详细说明我们的每一项主要贡献。

不诚实的大多数

正如我们提到的，[7]设计了一个使用BGW协议安全计算多方乱码电路的协议。由于构建一个乱码门需要在一个大数值和一个比特之间进行乘法，这就自然而然地适合采用算术电路的方法。然而，这在[7]中引入了许多复杂的问题，特别是由于他们在一个素数阶有限域(prime-order finite field) 上工作。与此相反，我们观察到，一个字符串与一个比特的乘法实际上可以用一个单一的字符串不经意传输（OT）来进行。此外，比特和字符串的OT在今天是非常便宜的，由于现有的极快的OT扩展协议，在局域网上每次遗忘传输的速率大约只有1微秒，而在较慢的网络上无论延迟是多少，都会达到1微秒[20，3] 。除了我们的基本协议外，我们还展示了如何去除约1/4的OT成本。这使用了一种新的方法，使我们能够通过发送一个单一的消息，并将其与用于计算乱码门中其他条目的OT的结果相结合，来计算每个乱码门中的一个条目。然后，我们进一步降低了成本，因为我们实际上只需要OT的一个变种，称为相关OT (correlated OT)，它甚至更有效率[3]。最后，我们是第一个将 free-XOR[25] 纳入多方乱码电路的人。以前的工作没有利用 free-XOR[7, 28]，因为他们在一个素数阶有限域上工作。无需多言，就像在两方的情况下一样，这种优化对于获得高性能是至关重要的。

我们注意到，纳入存在于两方情况下的乱码电路优化并不一定是简单的。这是因为电路本身必须通过一个安全协议来计算。例如，我们不知道在建立一个多方乱码电路时如何有效地进行乱码行还原。这使得姚氏乱码电路的 half-gates 优化[33]不适用，因为当没有行还原时，它的效率较低。我们猜想，减行 (row reduction) 以及半门不适合于多方设置。

诚实的大多数

FairplayMP 的多方乱码电路构造使用了BGW，并在素数有限域上工作。正如我们所提到的，这有一些缺点：首先，它与 free-XOR 优化不兼容；其次，它需要一个额外的乘法，将可能是的数值份额转换成的比特份额。相比之下，我们在上工作，其特征为 2。这使我们能够纳入 free-XOR，并节省了将转换成的乘法。使用 free-XOR 的另一个好处是，我们能够定义一个公式来计算每个乱码门中的每个值，从而节省了一个额外的乘法。因此，[7]要求在BGW内每个门的每个元素进行4次安全乘法，而我们在BGW内每个门的每个元素只需要进行2次安全乘法。除了计算成本外，这还将回合复杂度从6降至4。

实验评估

我们进行了多个实验，将我们不同的恒定轮次协议相互比较，并与高度优化的GMW[10]的实现进行比较。这些将在第4节中深入描述。我们的代码是开源的，可在SCAPI库[2]中使用，以使其他人能够复制我们的结果并与未来的工作进行比较。

我们的结果显示，对于在类似互联网的网络上计算深层电路，我们的协议远远超过了GMW。例如，在亚马逊上运行的、在弗吉尼亚和爱尔兰之间通信的机器（往返时间为75ms），在具有90,000个AND门和深度为4,000的SHA256电路上，GMW协议需要超过5分钟（3至13方），而我们的协议从3方的约6秒到13方的25秒不等。此外，GMW中的绝大部分时间是在线时间，而我们协议中的绝大部分时间是离线时间。因此，我们得到的3方和13方的在线时间分别为170ms到455ms，而GMW的在线时间约为5分钟。

令我们惊讶的是，我们的协议在不诚实多数的情况下是安全的，并且使用OT，几乎总是比我们基于BGW的协议更有效率。这是出乎意料的，因为OT使用了加密操作，而BGW只使用了更简单的信息论操作。然而，仔细观察就会发现，BGW中的场乘法数量实际上是各方数量的立方，而遗忘传输协议中的成本是二次的。结合这个事实，当今最好的遗忘转移扩展协议[3, 24, 22]是如此之快，BGW协议只比遗忘转移协议多出了一小部分当事方。

我们实验的另一个有趣的结果是，GMW协议实际上在低深度电路或非常快的网络中表现得非常好。这是由于当电路很浅的时候，那么GMW的轮数也是很小的。在这种情况下，与需要大量信息传输的乱码电路方法相比，小带宽是一个很大的优势。此外，在延迟很低的快速网络中，GMW的许多轮次并不明显影响运行时间。

结论

在互联网上的安全多方计算环境中（这是上述拍卖、选举、隐私保护调查等应用的自然环境），我们的协议采用乱码电路方法，比以前的所有协议都快得多。此外，我们的协议具有极快的在线时间，使其适用于有可能进行预处理和需要快速响应时间的场景。

还需要注意的是，GMW的复杂度随着计算方的数量上呈线性增长，与此相反，多方乱码电路方法在各方数量上呈二次增长（我们计算每一方的复杂度，因此GMW的线性复杂度意味着每一方的工作在每门的各方数量上是线性的）。因此，当各方的数量非常大时，这个成本可能是非常大的。我们的工作中出现的一个非常有趣的开放性问题是，是否有可能在时间上构建和评估一个多方乱码电路，其效率与各方的数量成线性关系

1.3 相关工作

正如我们所提到的，在半诚实和恶意的情况下，优化安全的两方计算的工作已经有很长一段时间了；参见 [25, 20, 18, 3, 6, 31, 33]。第一个在半诚实对手的多方环境中实现的协议是2008年的FairplayMP [7]。后来，在2012年，[10]提出了一个针对半诚实对手的多方GMW协议的高度优化版本。这个实现使用了OT扩展 [20]，使OT的成本变得微不足道。此外，[10] 在离线阶段在随机输入上运行所有的OT，然后在在线阶段每个OT只需要在每个方向发送一个比特。这使得在线阶段的速度非常快，带宽非常小。对于三方的特定情况，Sharemind 协议实现了快速计算 [9]，但只适用于3方，而且只适用于诚实的大多数。

此外，他们的协议也有很多轮，就像GMW一样，所以不适合类似互联网的设置。最近[30]的工作使用姚氏乱码电路实现了3方诚实多数的恶意安全，但没有扩展到3方以外。除了关于半诚实的多方计算的工作，还有关于在恶意敌手存在的情况下安全的多方计算的工作。SPDZ 协议 [13，12]，以及 [23] 的改进，是这个领域的最新技术。这些成果的离线阶段比我们的慢一个数量级，这完全是由于他们实现了对恶意敌手的安全，而这是更难的。更重要的是，SPDZ协议的在线时间遵循GMW范式（但由于必须执行正确性，所以费用更高一些）。因此，在慢速网络中，它与我们在此比较的GMW协议存在同样的问题。其他注重效率的多方协议包括 [21] 和 [27]；然而，这些协议还没有被实施，而且在实践中似乎要慢得多。在恶意设置中，与我们的协议最接近的比较是 [28]，它使用SPDZ来建立一个多方乱码电路。因此，[28]预计其在线时间与我们的协议相似。然而，其离线时间估计超过400秒，3 方计算 AES 电路（比我们的慢两个数量级）。我们强调，关于对恶意敌手安全的协议的讨论不是为了比较我们的协议（因为我们只实现了半诚实的安全），而是为了强调半诚实模型产生了更有效的协议，因此对于半诚实安全已经足够的应用来说是很重要的研究。这种比较也强调了在这一领域还需要很多进展；我们相信对半诚实情况的改进对恶意情况也会有很大帮助。

2. BMR 协议

2.1 背景知识

正如我们所提到的，在BMR协议中，各方构建了一个类似于姚氏乱码电路的多方协议。在姚的乱码电路构造中，随机标签（只是密钥）被分配给每条线；一个标签代表 0 值，另一个标签代表 1 值。

然后，每个门都是通过将适当的输出线标签与适当的输入线标签进行加密来构建的。例如，让是一个有输入线和输出线的 AND 门，让表示安全参数。此外，让表示线上的标签，同样表示线和上的标签。然后，在下、下和下被双重加密，而在下被双重加密。请注意，给定每个输入线上的单一标签，通过解密可以用每个输入线上的一个标签解密的单一密码文，就有可能计算出正确的输出线标签。此外，通过以随机顺序提供这些密码文本，计算门的一方不知道它获得的是还是（因为它们都只是随机值）。因此，评估电路的一方根本没有从计算中了解到任何东西。在两方的设定中，一方准备好乱码电路，另一方对其进行评估。

在多方设置中，所有各方必须共同准备乱码电路，而且它必须具有这样的特性：任何串通各方的子集都无法了解正在计算的值。因此，多方乱码电路是通过让所有各方对每个门的乱码做出贡献来构建的。特别是，所有的方都在每条线上选择他们自己的随机 0 标签和随机 1 标签，并且输出线的标签在每一方的输入线标签下被分别加密。因此，一个诚实的一方的输入线标签隐藏了所有其他方的输出线标签。假设是一方对线上的值所持有的输入标签；同样，对和线也是如此。由于每个值有个当事方和个输出线标签，加密的工作方式是用每一对 , 和掩盖所有的。更确切地说，让表示一个双密钥伪随机函数，它需要两个密钥，只要至少有一个密钥是秘密的，就能保持安全性。滥用符号，用表示门函数（以及用表示门索引），我们有，对于每一个，所有各方的输出标签与位相关的输出标签被加密为

其中表示字符串连接。请注意，为了学习（所有密钥/标签的串联在 [5, 7] 中被称为 "超级种子"）。我们注意到，输入到PRF 的值是 gate number，然后是被盲化的标签的索引。这确保了所有的输出线标签都是用独立的值进行盲化。

为了隐藏正在处理的和的值，使用了 " point-and-permute 技术 "（最初是由BMR发明的）。根据这项技术，一个随机的秘密 "permute bit " 与每条

.线相关联（这是通过每一方选择一个随机并设置实现的）。然后，如果输入线和到门的实际位是和，那么各方看到和，这将指导他们解密哪个密码文本。此外，他们得到的输出使他们能够进入下一个门。

构建多方乱码电路

在协议的第一部分，各方运行一个安全协议来计算乱码电路。这个阶段与各方的实际输入无关，因此可以在一个单独的离线阶段运行。作为 " BMR 成名之作" 的重要属性是，整个电路可以在恒定的回合数内构建，与电路的深度无关。这是由于计算多方乱码门的电路非常浅，而且所有乱码门都可以并行计算（因为给定所有导线上的乱码标签，每个门都可以独立计算）。因此，有可能使用任何一般安全计算的协议，其回合复杂度与电路的深度成线性关系，以便在恒定的回合数中安全地计算一个多方乱码电路（不管其深度如何）。直观地说，每一方在本地计算，其中，每个，这些都输入到计算门的电路。请注意，这意味着每一方必须对每个门进行次 double-key PRF 计算。

对 BMR 电路进行评估

与姚的乱码电路一样，给定个密钥集和，就有可能对乱码门中的单行进行解密，得到。因此，这种方法可以用来评估整个电路。此外，一旦各方收到每个电路输入线上的密钥集，他们可以各自在本地计算整个电路并获得输出。因此，该协议的在线运行时间非常小：各方只需发送极少量的信息，然后整个电路就被本地计算出来了。请注意，为了进行门的计算，每一方都需要计算因此，多方乱码电路的评估需要每个门进行次 PRF 计算。

2.2 Free XOR

在这一节中，我们描述了我们是如何将free-XOR优化纳入多方乱码电路的。BMR[5]的原始工作，以及FairplayMP[7]系统都是在free-XOR技术[25]之前发表。这项技术使XOR门可以在姚氏乱码电路中免费计算，并已成为在该环境中使用的标准。在最近的BMR-SPDZ协议[28]中，使用BMR来实现恶意敌手存在下的安全，free-XOR 也没有被纳入。这似乎是由于他们在素数的有限域中工作（为了优化协议的SPDZ部分），而这并不适合free-XOR。我们在这项工作中的第一个优化是将free-XOR纳入BMR。这很重要，有两个原因。首先，最明显的是，free-XOR减少了乱码和评估电路的AES操作的数量。由于评估每个门需要次AES操作（对于方），这一点很重要。其次，由于只有AND门需要加密，free-XOR大大减少了乱码电路的带宽。BMR中大量的通信是有问题的，所以这一点很重要。

直观地说，BMR中的free-XOR与Yao中的工作方式相同。对于每个，选择一个固定的（随机的） difference parameter （只为所知）。然后，对于每条线，标签是随机的，而标签被设定为等于。由于这种关系，XOR 门可以通过简单地将输入线上的乱码标签进行 XOR 来计算，并将输出线上的乱码标签作为结果。我们在图 1 中正式描述了输出BMR电路的功能；这个功能需要在离线阶段进行安全计算。我们设计该功能的方式是将安全计算协议中的必要计算降到最低（因此，在运行之前，所有预结算值的所有份额都由各方准备）。

我们在图1中解释了的计算过程。permutation 位随机地移植了每条线上的值。特别是，双方在输入线上看到的是，但和线上的实际值分别是和。由于是随机的，因此，按照要求，, 没有透露任何关于实际值的信息）。现在，AND门的输出正好是，因为这是实际值的乘积。暂时假设为。那么，如果，将是的加密，否则它将是的加密。相反，如果，那么结果将是相反的。因此，这保留了双方持有密钥的不变性，其中等于电线上的实际值与的XOR。

在本文的完整版本中，我们正式证明了在 BMR 的背景下 free-XOR 构造的安全性，在相关稳健的循环性假设下，就像在[11]中一样（对oracle成立）。

2.3 使用多方乱码电路的 MPC

考虑到功能，我们现在表明任何多方功能都可以在恒定的回合数内被安全地计算。我们已经在第 2.1 节中非正式地解释了协议的工作原理，现在我们提出离线协议和在线阶段的正式规范。这些规范假定了的实现，这是协议的主要挑战，我们将在下面第3节中看到。

我们所描述的MPC协议是BMR协议的一个变体，是在 -混合模型中设计的。这个变体与原始 BMR 协议的主要区别在于，我们的 BMR 电路包含了 free-XOR。(当然，我们的完整协议在有效计算方面有额外的区别。) 该协议由两个阶段组成。

Part 1 - the Offline Phase:

在这个阶段，各方首先运行一个本地计算，以准备他们对的输入。图 2 给出了这个局部计算的正式规范。请注意，各方以一种特殊的方式选择导线标签，以确保 free-XOR 属性的工作。接下来，各方安全地计算 Functionality ，以获得乱码电路。

最后，每一方在每条电路输出线上发送它的 permutation 位的份额。此外，所有各方在与的私人输入相关的电路输入线上向发送它们的 permutation 位份额。(回顾一下，图1中出现了Functionality 的正式规格。)

Part 2 - the Online Phase:

给出他们的私人输入，这一阶段开始时，各方在相关线路上广播他们的私人输入与 permutation 位的XOR。接下来，其他各方会发送适当的乱码标签。最后，每一方在本地计算乱码电路并获得输出（使用输出线上的知识将输出的乱码值转换成实际的输出位）。因此，在线阶段包括很少的通信和主要的本地计算。图3给出了这个阶段的正式规范。