基于安全多方计算协议实现私密深度学习模型

作者：Morten Dahl

编译：weakish

编者按：奥胡斯大学密码学PhD、Datadog机器学习工程师Morten Dahl介绍了如何基于安全多方计算协议实现私密深度学习模型。

受最近一篇混合深度学习和同态加密的博客的启发（见基于Numpy实现同态加密神经网络），我觉得使用安全多方计算（secure multi-party computation）替换同态加密实现深度学习会很有趣。

在本文中，我们将从头构建一个简单的安全多方计算协议，然后尝试基于它训练简单的神经网络进行基本布尔值计算。本文的相关代码可以通过GitHub取得（mortendahl/privateml/simple-boolean-functions）。 假设有未串通的三方、、，愿意一起进行计算，即训练神经网络并使用它们进行预测；然而，出于一些理由，他们不愿意泄露学习好的模型。同时假定有些用户愿意在保持私密的前提下提供训练数据，有些用户也有兴趣在他们的输入保持私密的前提下使用学习好的模型。

为了能够做到这一点，我们需要安全地在特定精度下计算有理数；具体而言，对它们做加法和乘法。我们同时需要计算sigmoid函数，这一函数的传统形式在安全设定下会导致惊人沉重的运算。因此，我们将依照基于Numpy实现同态加密神经网络中的做法，使用多项式逼近sigmoid函数，不过我们会进行一点优化。

安全多方计算

同态加密（Homomorphic Encryption，HE）和安全多方计算（secure Multi-Party Computation，MPC）是现代密码学中密切相关的两个领域，常常互相使用对方的技术以便解决大致相同的问题：计算接受私密数据输入的函数而不泄露任何东西，除了（可选）最终输出。例如，在我们的私密机器学习设定下，两种技术可以用来训练我们的模型并进行预测（不过在HE的情形下，如果数据来自使用不同加密钥的用户，需要做一些专门的技术处理）。

就其本身而言，从高层看，HE经常可以用MPC替换，反之亦然。至少就今天而言，两者的区别大致是HE不怎么需要交互，但是需要昂贵的计算，而MPC的计算很廉价，但需要大量交互。换句话说，MCP用两方或多方间的交互取代了昂贵的计算。

目前而言，这在实践中提供了更好的性能，以至于人们可以主张MCP是明显更成熟的技术——作为这一主张的依据，已经存在好几家公司提供基于MPC的服务。

定点数算术

运算将在一个有限域上进行，因此我们首先需要决定如何将有理数表示为域元素，即取自的整数（Q为质数）。我们将采用典型的做法，根据固定的精度放大每个有理数，比如，在位精度的情形下，我们将放大倍，然后将结果的整数部分作为定点数表示。例如，时，我们得到和。

注意，在这一表示下，加法是直截了当的，，而乘法添加了额外的放大因子，我们需要处理掉以保持精度和避免爆掉数字：。

共享和重建数据

编码输入后，每个用户接着需要一种和他方共享数据的方式，以便用于计算，不过，数据需要保持私密。

为了达到这一点，我们需要的配料是秘密共享（secret sharing）。秘密共享将一个值以某种方式分成三份，任何见到少于三份数据的人，无法得知关于值的任何信息；然而，一旦见到所有三份，可以轻易地重建值。

出于简单性考虑，这里我们将使用复制秘密共享（replicated secret sharing），其中每方收到不止一份数据。具体而言，私密值分成部分、、，满足。方收到(,)，收到(,)，收到(,)。不过本教程中这一点将是隐式的，本文会直接将共享的储存为由三部分组成的向量。

当两方以上同意将一个值表露给某人时，他们直接发送他们所有的部分，从而使重建得以进行。

然而，如果部分是以下小节提到的一次或多次安全运算的结果，出于私密性考虑，我们在重建前进行一次再共享。

严格来说这是不必要的，但是进行这一步可以更容易地说明为什么协议是安全的；直观地，它确保分享的部分是新鲜的，不包含关于我们用于计算结果的数据的信息。

加法和减法

这样我们已经可以进行安全的加法和减法运算了：每方直接加减其拥有的部分，由于，通过这一操作可以得到的三部分（技术上说应该是，但是隐式写法更易读）。

注意这不需要进行任何通讯，因为这些都是本地运算。

乘法

由于每方拥有两个部分，乘法可以通过类似上面提到的加法和减法的方式进行，即，每方基于已拥有的部分计算一个新部分。具体而言，对下面的代码中定义的、、而言，我们有（技术上说……）

然而，每方拥有两个部分的不变性没有满足，而像直接将发给这样的做法是不安全的。一个简单的修正是直接将每份当成私密输入共享；这样就得到了一个正确而安全的共享（乘积）。

不过还有一个问题，如前所述，具有双精度：它编码时使用的放大因子是，而不是。在不安全设定下，我们本可以通过标准的除法（除以）来修正这一点，然而，由于我们操作的是有限域中的秘密共享元素，这变得不那么直截了当了。

除以一个公开的常量，这里是，足够简单：我们直接将部分乘以其域中的逆元素。对某和，如果，那么乘以逆元素得到，那么就是我们要找到的值。在不安全设定下，残值足够小，可以通过取整消除。与此不同，在安全设定下，基于有限域元素，这一语义丢失了，我们需要通过其他方法摆脱残值。

一种方法是确保。具体而言，如果我们事先知道，那么我们可以不对作除法，而对作除法，接着我们就如愿以偿，得到和，即，没有任何残值。

剩下的问题当然是如何安全地得到，以便计算。具体细节见CS’10，不过基本的思路是首先在上加上一个大的掩码，将掩码后的值表露给其中一方，使其得以计算掩码后的。最后，共享和解掩码这一掩码后的值，然后计算。

注意上面的是本地操作，将每个共享部分乘以公开的常数，这里是的域中逆元素。

安全数据类型

最后，我们将以上过程包裹进一个定制的抽象数据类型，这样我们之后表达神经网络的时候就可以使用NumPy了。

基于这一类型，我们可以安全地对这样的值进行操作：

此外，需要调试的时候，我们可以切换为不安全类型而不需要修改其余（神经网络）代码。再比如，我们可以隔离计数器的使用，查看进行了多少次乘法，进而让我们模拟下需要多少通讯。

深度学习

这里用“深度学习”这个术语属于夸夸其谈，因为我们只是简单地摆弄了下基于Numpy实现同态加密神经网络中的神经网络学习基本布尔值函数。

一个简单函数

第一个实验是训练网络以识别序列中的第一位。下面的代码中，中的四行是输入的训练数据，中相应的列是所需输出。

我们将使用同样的双层网络，不过我们会将下面定义的sigmoid逼近函数作为参数。函数是一个简单的辅助函数，将所有值转换为我们的安全数据类型。

同时，我们将使用原文提出的sigmoid逼近，即标准麦克劳林/泰勒多项式的前五项。出于可读性考虑，我这里用了一个简单多项式演算，有待进一步优化，比如使用秦九韶算法减少乘法的数目。

实现了这个之后我们就可以训练和演算网络了（细节见notebook），这里使用了10000次迭代。

注意训练数据在输入网络之前是安全共享的，并且学习到的权重从未泄露。预测同理，只有网络的用户知道输入和输出。

从上面的演算来看，神经网络确实看起来学习到了所要求的函数，在未见输入上也能给出正确的预测。

稍微高级些的函数

在下一个实验中，神经网络无法像之前一样镜像三个组件的其中一个，从直观上说，需要计算第一位和第二位的异或（第三位是偏离）。

如Numpy实现神经神经网络：反向传播一文所解释的，使用双层神经网络只能给出无意义的结果，本质上是在说“让我们扔一枚硬币吧”。

提议的补救措施是在网络中引入另一层：

然而，如果我们采用之前的方式训练网络，即使仅仅迭代100次，我们都将面临一个奇怪的现象：突然之间，误差、权重、预测分数爆炸了，给出混乱的结果。

导致这一切的原因很简单，但也许乍看起来不是那么明显（至少对我而言）。尽管（前五项）麦克劳林/泰勒逼近sigmoid函数在前面的网络中表现良好，当我们进一步推进时，它完全崩塌了，产生的结果不仅不精确，而且数量级也不对。因此很快摧毁了我们可能使用的任何有穷数字表示，即使在非安全设定下也是如此，数字开始溢出了。

技术上说sigmoid函数演算的点积变得太大了，就我所知，这意味着神经网络变得非常自信。就此而言，问题在于我们的逼近不允许神经网络变得足够自信，否则精确度会非常糟糕。

我不清楚基于Numpy实现同态加密神经网络是如何避免这一问题的，我最好的猜测是较低的初始权重和alpha更新参数使它可能在迭代次数较低的情形下绕过这个坑（看起来是少于300次迭代）。无比欢迎任何关于这方面的评论。

逼近sigmoid

既然是我们的sigmoid逼近阻碍了我们学习更高级的函数，那么很自然地，我们接下来尝试使用麦克劳林/泰勒多项式的更多项。

如下所示，加到第9项（而不是第5项）确实能稍微增加一点进展，但这点进展远远不够。此外，它塌得更快了。

或者我们该转而使用更少的项以更好地牵制崩塌？比如，只加到第3项？这确实有点作用，能让我们在崩塌之前训练500次迭代而不是100次。

然而，误差和预测很糟糕，也没有多少空间供增加迭代次数了（大约在550次迭代处崩塌）。

插值

作为替代，我们可以放弃标准多项式逼近，转而尝试在区间上进行多项式插值。这里主要的参数是多项式的项数，我们希望它保持在一个较低的值，以提高效率。不过，系数的精度也是相关参数。

一同绘制标准逼近和插值多项式（红色曲线）的图像我们看到了改进的希望：我们无法避免在某点崩塌，但它的崩塌点显然要大很多。

当然，我们也可以尝试其他项数、精度、区间的组合，如下所示，不过对我们的应用而言，上面的参数组合看起来已经足够了。

现在让我们回到我们的三层网络，我们定义一个新的Sigmoid逼近：

……然后开始训练：

现在，尽管我们运行了10000次迭代，没有发生崩塌，预测表现也提升了，只有一个预测错误（[0 1 0]）。

注意错误情形的分数不是完全偏离，某种程度上和正确预测的零值有所不同。再运行5000次迭代看起来不会改善这一点，这时我们已经快要崩塌了。

结语

本文重点介绍了一个简单的安全多方计算协议，而没有显式地论证开头提到的安全多方计算比同态加密更高效。我们看到，使用非常基本的操作实现私密机器学习确实是可能的。

也许更需要批评的是我们没有测量运行协议需要的通讯量，主要是每次乘法时所需交换的一些消息。基于这一简单的协议进行大量计算的话，显然让三方通过高速局域网连接会比较好。不过更高级的协议不仅减少了来回收发的数据量，同时改善了其他性质，比如回合数（像乱码电路（garbled circuits）就可以将回合数压到一个小常数）。

最后，本文基本上将协议和机器学习过程看成是正交的，让后者仅仅以一种黑盒的方式使用前者（除了sigmoid计算）。两者更好的配合需要两个领域的专门知识，但可能显著地提升总体性能。