机器学习中的多方计算

在我今年夏天的实习期间，我构建了一个多方计算（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方。然后每方存储以下值作为其秘密份额：

1
2
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。每方生成并分发随机值以获得以下秘密份额。再次注意：

1

(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)

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

1

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

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

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

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

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

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

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

结语

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