机器学习中的多方计算 - The Trail of Bits Blog

Jim Miller
2019年10月4日
密码学, 实习项目, 机器学习

今年夏季实习期间，我构建了一个多方计算（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

页面内容
MPC入门
安全MPC协议
加法
乘法
优化
结果
结语
最近帖子
构建安全消息传递很难：对Bitchat安全辩论的细致看法
使用Deptective调查您的依赖项
系好安全带，Buttercup，AIxCC的评分回合正在进行中！
使您的智能合约超越私钥风险
Go解析器中意外的安全陷阱
© 2025 Trail of Bits。
使用Hugo和Mainroad主题生成。