多方安全计算之Beaver三元组

回想一下，我们的任务是设计一个协议，也就是一组Alejandra和Bonifacio要遵循的规则，以这样的方式计算函数z = (x-y)*(x+y)，并且不泄露其他任何信息。Alejandra有她的输入x，Bonifacio有他的输入y。乍一看，似乎要计算z，各方需要知道x和y，这些值定义了结果。有了这两个值，计算过程将简单进行如下（从现在开始的所有算术都是模7进行的）：

计算u = x+y和v = x-y

相乘得到z = u*v，并返回z。

现在，我希望你熟悉加密方案：这些方案允许将数据转换为“隐藏”的表示方式，以便稍后可以通过某个秘密密钥恢复它。暂时想象一下，我们有一种方法来将输入加密为Enc(x)和Enc(y)，并且所使用的加密方案是这样的，只要你有两个值的加密，就可以通过对这两个值进行加减乘等操作得到相应操作的加密。在这种情况下，我们可以运行上述完全相同的步骤，除了在开始时包含一个加密步骤来加密输入，并在最后包含一个解密步骤来恢复输出：

Alejandra将x加密为Enc(x)，Bonifacio将y加密为Enc(y)，计算Enc(u) = Enc(x)+Enc(y)和v = Enc(x)-Enc(y)，相乘得到Enc(z) = Enc(u)*Enc(v)，解密z，并返回z。

这在概念上很简单，希望它能让你相信，在“隐藏”数据上进行计算的想法可能并不像听起来那么疯狂！你‘只需’找到一种以不泄露底层值为代价的替代表示方法，同时在处理这些值时仍然可以执行操作...但是...我们真的取得了进展吗？让我再说一遍：找到一种以不泄露底层值为代价的方式来隐藏数据，而仍然可以在其上进行计算...我认为这听起来仍然像是MPC本身一样疯狂，而且实际上确实如此！但是这有助于我传达这样一个观点，即要安全地计算一个函数，你只需要切换到一种代表方式，该方式在处理值时不泄露任何关于这些值的信息。

具有上述特性的加密方案确实存在！这些方案属于一个称为完全同态加密的领域，在过去的十年中已经产生了越来越高效的构造。然而，即使按照我上面描述的方式使用其中一种方案将为Alejandra和Bonifacio提供学习z的协议，这绝对不是在实践中进行此操作的方式。主要原因是这些方案不够高效。此外，它们也是相当过度的：除了最后的解密步骤，计算可以由任何人在本地执行，甚至是“外部人员”。在MPC协议中，我们可以利用各方可以相互通信并相互帮助来进行计算的事实。这将使我们能够获得增强的效率，接下来我将讨论这一点。

想象一下，Alejandra和Bonifacio拥有共享值[u]和[v]，他们想要获得份额[u*v]的值，而在此过程中不泄露u和v的任何信息。非常类似于上面协议的第3步。有很多方法可以解决这个问题，而且通常你应该知道这是大多数MPC协议的瓶颈，最近的许多研究工作都集中在改进这个具体任务上。我将在这里展示的方法基于所谓的乘法三元组思想，这是由Beaver提出的一种相当聪明和简单的解决问题的方式。

离线-在线范式

首先，我们将整个执行过程分为两个部分，一个是离线阶段，一个是在线阶段。在第一阶段，也称为预处理阶段，各方执行与输入无关的所有操作。第二阶段是需要定义输入的计算部分，为了了解，建立通信通道（例如通过密钥交换）可以在某种程度上被视为离线阶段的一部分。这种分离是有意义的，因为在许多使用情况中，人们更关心从提供输入到获取输出的性能，而在此之前发生的任何事情对于效率来说不那么重要。

Beaver的想法非常简单和通用，但它并不能完全解决安全乘法的问题。简而言之，这个想法是假设各方在离线阶段花费了足够的时间和精力来生成某些共享数据（与输入无关）。然后，在在线阶段，一旦提供了输入，这些预处理材料就可以用于以非常简单的方式安全地计算乘法。

乘法三元组

各方需要预处理的秘密共享值被称为乘法三元组，有时也称为Beaver三元组。这是一个元组（[a]，[b]，[c]），其中c=a*b，而a和b是均匀随机且任何一方都不知道的。为了说明生成这些[a]（和[b]）的潜在方法，考虑Alejandra和Bonifacio分别随机选择一些a1和a2。然后，可以将a定义为a1+a2。Alejandra不知道a，因为她不知道a2，Bonifacio也不知道a，因为他不知道a1。获得[c]更困难，因为这又是计算两个秘密值的乘积的份额的问题。

幸运的是，Beaver方法的美妙之处在于我们实际上并不关心这些三元组是如何生成的！只要它们满足上述条件，它们就可以在在线阶段中用于处理乘法。这种模块化具有许多优点。首先，上面描述的在线阶段使用这些三元组执行安全乘法，享有高效和完美安全的良好特性。鉴于此，在提高整体协议效率方面，通常只需专注于生成乘法三元组的具体任务，虽然这并不特别容易，但比起安全计算函数的任务要容易得多。

这种分离的另一个好处是，生成乘法三元组甚至不需要通过协议来完成，至少如果你愿意有一个“部分”受信任的第三方的话。例如，Alejandra和Bonifacio可以考虑一个共同的朋友Camilo，他的唯一任务就是随机选择一个三元组（a，b，c），并将这些值的份额分发给Alejandra和Bonifacio。我们要求Camilo在计算这些三元组时是诚实的，并且他不应该告诉Alejandra和Bonifacio原始值是什么。一旦Camilo分发了这些预处理数据，他就不再需要了。特别要注意的是，他不会对各方的实际输入信任，并且他不需要参与计算。

在线阶段

假设Alejandra和Bonifacio拥有两个值的份额[u]和[v]。将它们视为某种程度上依赖于输入数据的值，例如在我们考虑的协议中，u = x+y且v = x-y。还假设他们以某种方式获得了一个乘法三元组([a]，[b]，[c])；同样，我们实际上并不关心如何获得。可以将这个乘法三元组用于计算份额[u*v]，具体步骤如下：

各方（本地）计算[d] = [u]-[a]和[e] = [v]-[b]。

各方重构d和e，将它们转化为公开已知的值。

各方（再次本地，使用线性操作可以处理而不需要通信的事实）计算[u*v] = d*[b]+e*[a]+[c]+d*e。

关于这个协议有两个主要问题需要讨论：正确性（产生了正确值的份额）和隐私（在过程中没有泄露关于u和v的任何信息）。第一个问题实际上非常容易证明：只需将u替换为d+a，v替换为e+b，在u*v中，你会得到等式右边在第3步中计算的结果。对于隐私属性，只需注意到只有d和e这两个值被公开。现在，这些值并不泄露关于u和v的任何信息，你能看出为什么吗？（提示：回想一下a和b是均匀随机且任何一方都不知道的。）

请注意，尽管上面的协议相对简单，但确实涉及通信（在第2步中，各方需要宣布他们的份额以重构d和e）。我们永远无法摆脱这一点：安全乘法始终需要某种形式的交互。

此外，请注意，上面的模板非常通用，实际上并不限于两个参与方。我们将在后面讨论如何在更一般的环境中使用这个范例。

这个协议是否具有主动安全性？

我不知道，你告诉我，不，但是说真的，试着想一想，如果突然有一方开始任意行动，会发生什么破坏。事实证明，协议会破裂。最容易分析的部分是在整个协议中的最后一步中重构结果[z]，但是如果你能看出在乘法协议中特别破裂了什么，那就更加厉害了。

我们将在后续的文章中看到如何添加主动安全性。与这里所看到的一样，首先实现在线阶段的主动安全性会更容易，也就是假设我们从预处理阶段获得了所需的任何内容。确保离线阶段的主动安全性非常麻烦，我甚至不确定我们是否会在本系列中讨论这个问题。

最后，我想简要讨论一下当你面对的是与f(x, y) = (x+y)(x-y) mod 7不同的函数时该怎么办。例如，在著名的百万富翁问题中，Alejandra和Bonifacio想要计算的函数会输出一个比特位，指示两个输入（代表工资）中的哪一个较大。在私有集合交集问题中，各方拥有输入的集合，他们希望输出是这些集合的交集。如何使用我在这里介绍的技术来计算这样的函数？

首先，让我给你一个理论学家的答案。在本文中，我们不仅看到了如何计算f(x, y)的方式，还看到了如何安全计算加法和乘法（模7）。那么，如果你可以在一个域上进行加法和乘法运算（这就是整数模7），那么你可以计算该域上的任何函数（因此也可以通过将数据编码到该域中来计算任何函数）。这是因为每个将元组作为输入并返回域元素的函数都可以表示为多元多项式，它只由加法和乘法组成。计算机科学家通常不会讨论多元多项式，而是使用由加法和乘法门组成的算术电路，但它们实际上是完全一样的。

这个答案可能不完全令人满意，因为通常在“正常”条件下，许多函数在用这种不自然的域-多元多项式表示时可能变得过于复杂。这不是在实践中处理事物的方式。在实际应用MPC时，思路是尽可能将其表达为加法和乘法的组合。如果涉及整数运算，那么可以使用足够大的模数来避免任何溢出。如果涉及实数运算，可以使用定点算术，通过特定的协议处理截断等操作。如果计算需要，例如，对两个共享值进行比较或计算数学函数如e^x：这些都可以使用专门的“子”协议来计算。

不幸的是，我没有时间讨论使MPC适用于实际应用的基本原语。目前，你只能满足于一年级的加法和乘法运算。从理论上讲，这足够了！