机器学习中的多方计算

在我今年夏天的实习期间，我构建了一个多方计算（MPC）工具，该工具实现了用于感知机和支持向量机（SVM）算法的三方计算协议。

MPC 使得多方能够在私有数据集上执行分析，而无需彼此共享数据。我开发了一种技术，让三方能够跨非公开数据集获得机器学习的结果。现在，可以在私有数据集上执行数据分析，这在以前由于数据隐私限制是不可能的。

MPC 入门

对于 MPC 协议，一组参与方，每个都有自己的一组秘密数据 xi，共享一个输入函数 f，并且每个参与方都能够获得 f(x1,…,xn) 的输出，而无需了解其他参与方的私有数据。

MPC 的首次演示之一是姚氏百万富翁问题，其中两个人想要确定谁有更多的钱，而不透露各自的具体金额。每个人都有一个私有的银行账户余额 xi，他们想要计算 f(x1,x2) = x1 > x2。姚氏演示了如何使用混淆电路安全地计算这个函数以及任何其他函数。

每个参与方可能通过 MPC 函数的输出推断出关于对方数据的一些信息。泄露的信息仅限于对方的金额是大于还是小于自己的金额；具体金额从未被披露。

MPC 协议使用布尔和算术电路来计算任意函数（见图 1）。任何可计算函数都可以表示为布尔（AND/OR）和/或算术（ADD/MULT）门的组合。因此，通过一系列安全的 MPC 加法和乘法协议建立了一个安全的 MPC 协议。在实践中，我们希望将一个函数转换为电路，然后在该电路上运行 MPC 协议。

MPC 协议还必须在有限域中操作，因此许多 MPC 工具被设计为在整数模素数 p（一个有限域）上操作。这使得机器学习应用变得困难，并且有时不兼容，因为它们需要定点算术。几乎所有这些工具都需要一个合成工具来将程序（通常是 C 程序）转换为相应的算术电路表示。

以下是使 MPC 机器学习变得困难的几个挑战：

• 定点算术和截断协议不太适合 MPC 协议操作的有限域。
• 电路大小可能与输入数据一样大。当函数作为电路评估时，所有输入值必须加载到电路中。电路将为每个输入值设置输入门，这使得电路的输入层与数据集一样大。
• 存储电路和中间值需要大量内存。
• 机器学习引入了退出条件依赖于中间值的循环；然而，每个参与方必须在协议开始时与其他参与方共享其电路。它们不能依赖于中间值。

我项目的目标是创建一个新颖的 MPC 工具，可以从多方持有的秘密数据中训练机器学习模型。我们想要实现一个多于两方的计算协议，包括用于机器学习的任意精度的定点算术。我们还希望提供一种替代电路合成的方法，以执行具有复杂函数的 MPC。

图 1：（左）一个简单的算术电路。（中）一个简单的布尔电路。（右）执行多方计算的路线图。

安全 MPC 协议

对于三方，每个参与方将其数据分割成“秘密份额”并发送给其他人。秘密份额只有在全部组合时才能揭示秘密值信息，否则所有秘密值必须保持隐藏。这一属性被正式定义为隐私，并通过以下方式说明：

设 n=3 方。各方同意使用整数模 p，Zp，其中 p=43，一个随机小素数。参与方 1 有 x1=11，并希望为此值创建秘密份额。参与方 1 将生成 Zp 中的两个随机值，比如 r2=21 和 r3=36，并将 r2 发送给参与方 2，r3 发送给参与方 3。然后每个参与方存储以下值作为其秘密份额：

share1 = (x1 – r2 – r3) mod 43 = 40 mod 43
share2 = r2 = 21 mod 43
share3 = r3 = 36 mod 43

请注意，任何一个或两个秘密份额的组合都会揭示关于 x1 的信息。这就是秘密共享的力量所在。

在为所有私有数据创建秘密份额后，各方可以开始对其输入执行安全加法或乘法。两种操作的协议取决于所使用的秘密共享方法。我将演示如何为上述特定秘密共享方案进行加法和乘法。

让我们为 MPC 构建安全加法和乘法原语。

加法

考虑 n=3 的情况，使用域 Zp 和 p=43。这里，我们将三个输入值取为 x1=11，x2=12，x3=13。每个参与方生成并分发随机值以获得以下秘密份额。再次注意：

(share1,i + share2,i + share3,i) mod 43 = xi mod 43：

参与方 1 份额：share1,1=40，share1,2=13，share1,3=8
参与方 2 份额：share2,1=21，share2,2=2，share2,3=17
参与方 3 份额：share3,1=36，share3,2=40，share3,3=31

为了安全地加值 x1、x2 和 x3，三方只需添加这些值的各自份额。

参与方 1：share+,1 = share1,1 + share1,2 + share1,3 = 40 + 13 + 8 = 18 (mod 43)
参与方 2：share+,2 = share2,1 + share2,2 + share2,3 = 21 + 2 + 17 = 40 (mod 43)
参与方 3：share+,3 = share3,1 + share3,2 + share3,3 = 36 + 40 + 31 = 21 (mod 43)

就这样！现在，每个参与方都有一个值的秘密份额：

x1 + x2 + x3 = 11 + 12 + 13 = (18 + 40 + 21) mod 43 = 36。

标量加法和乘法

标量加法和乘法指的是将秘密值与公共值相加/相乘。假设每个参与方有某个值 z 的秘密份额，并且他们想要获得比如 5 + z 或 5z 的份额。这实际上也很容易。要执行加法，参与方 1 在其份额上加 5，其余参与方什么都不做，现在他们都有了 5 + z 的秘密份额。要执行乘法，所有参与方只需将其 z 的份额乘以 5，他们就都获得了 5z 的秘密份额。您可以轻松检查这些对于任何公共整数都成立。

乘法

安全乘法比加法更复杂，因为所有参与方必须交互。这在计算需要多次乘法的非平凡函数时降低了性能，特别是如果各方在延迟高的网络上操作。因此，大多数这些方案的目标是最小化安全乘法所需的通信量。

使用 Beaver Triples 是一种著名的乘法方法，它将操作分解为一系列安全加法、标量加法和标量乘法。更具体地说，该方法利用以下属性：

Beaver Triples 的秘密份额与输入值的秘密份额一起创建。Beaver Triples 是两个随机值 a 和 b，以及它们的乘积 ab=c。这些值的秘密份额被发送给其他参与方，因此每个参与方都有 x1、x2、a、b 和 c 的秘密份额。

要计算 x1 ✕ x2，每个参与方首先计算 (x1 – a) 和 (x2 – b) 的份额，并将其广播给其他参与方。(x1 – a) 的份额通过标量乘以 -1 并将结果加到 x1 来获得。(x2 – b) 也是如此。一旦这些份额被计算并广播，每个人现在可以计算 yz。在最后一步，各方通过标量乘法获得 yb 和 az 的份额，使每个人都拥有 yz 的值以及 yb、az 和 c 的秘密份额。

对 yb、az 和 c 的份额使用安全加法，以获得 (yb + az + c) 的秘密份额。然后，他们使用 yz 和其 (yb + az + c) 的份额执行标量加法。现在，获得了 (yz + yb + az + c) = x1 ✕ x2 的份额，协议完成。

优化

MPC 的一个主要瓶颈是由于乘法导致的各方之间的通信，这通常不能并行完成。为了优化，选择要么减少通信交换，要么减少函数所需的乘法次数。我的工作集中在后者。

整数比较对于算术电路来说很困难，如果从函数到电路的转换不够聪明，比较可能非常低效。但事实上，所有算术电路都可以用输入值的多项式表示。

让我们考虑表示 f(x1,x2) = x1 < x2 的多项式，其中零点的数量是输入空间的一半，与域大小成正比。由于这个函数不是常数零，多项式次数与零点的数量成正比。所以计算这个的算术电路有与域大小一样多的乘法门。非常低效！

但通过使用 Octavian Catrina 和 Sebastiaan de Hoogh 论文中的方法将一切分解为构建块，我们实际上可以获得指数级更小的算术电路。所需的主要构建块是一个高效的截断协议，他们通过一个由其他子协议构建的模余数协议来开发这个协议。重要的是，它们允许我们使用与域的位大小成正比的电路，而不是与域本身成正比的电路，使它们指数级更小。

结果

我选择实现 Araki 等人的 MPC 协议，包括他们的秘密共享、加法和乘法方法。我还开发了专门的安全比较和截断协议，以及点积协议。将复杂协议与加法和乘法结合被称为安全计算的混合模型。这种混合模型给了我们非常紧凑、直观的电路，甚至可以手工编写！（见图 2 和 3）

我将这个 MPC 协议应用于感知机和 SVM 算法，这需要将它们转换为构建块操作。SVM 算法可以使用比较和点积操作的复杂构建块手动合成为紧凑的混合电路。具体来说，每个算法的一次迭代只需要大约 15 个门。作为比较，使用合成工具合成 AES 将导致数千个加法和乘法门。

图 2：（左）感知机算法的伪代码。（右）表示感知机算法一次迭代的混合电路。

为了避免与数据集成正比的巨大电路，我只合成了每个协议一次迭代的电路。这避免了处理循环，并产生了一个可以用于任何数据集的非常紧凑的电路。最后，使用一次迭代提供了如何处理协议收敛的灵活性。这种方法提供了三个选项：

• 各方事先商定固定次数的迭代，
• 各方公开揭示一个 epsilon 值，或
• 各方根据另一个 MPC 计算收敛检查。

图 3：（左）支持向量机（使用部分梯度下降）的伪代码。（右）表示支持向量机一次迭代的混合电路。

一旦混合电路被手动合成，我在测试数据集上执行了算法并实现了任意定点精度。分类准确性也与原始算法相同。因此，该工具可用于使用感知机或 SVM 以任意精度训练秘密数据。

结语

我花了整个夏天解决与 MPC 和机器学习相关的几个困难。到夏天结束时，我对每个问题都有了高效的解决方案，并能够在三方之间安全地运行两种不同的机器学习算法。我很喜欢从事这个项目。在 Trail of Bits 实习之前，我刚完成博士的第二年。我最初认为从学校到行业的过渡会很剧烈。但我很快注意到，在这个实习中，我的项目将与博士研究非常相似，这是使 Trail of Bits 成为一个伟大工作场所的众多事情之一。

如果您喜欢这篇文章，请分享： Twitter LinkedIn GitHub Mastodon Hacker News