多方计算在机器学习中的应用

在我今年夏天的实习期间，我构建了一个多方计算（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三元组是一种著名的乘法方法，它将操作分解为一系列安全加法、标量加法和标量乘法。更具体地说，该方法利用以下属性：

Beaver三元组的秘密份额与输入值的秘密份额一起创建。Beaver三元组是两个随机值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协议，包括他们的秘密共享、加法和乘法方法。我还开发了专门的安