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

基于安全多方计算协议实现私密深度学习模型奥胡斯大学密码学PhD、Datadog机器学习工程师Morten Dahl介绍了如何基于安全多方计算协议实现私密深度学习模型。受最近一篇混合深度学习和同态加密的博客的启发（见基于Numpy实现同态加密神经网络），我觉得使用安全多方计算（secure multi-party computation）替换同态加密实现深度学习会很有趣。在本文中，我们将从头构建一个简单的安全多方计算协议，然后尝试基于它训练简单的神经网络进行基本布尔值计算。本文的相关代码可以通过GitHub取得（mortendahl/privateml/simple-boolean-functions）。 假设有未串通的三方P0、P1、P2，愿意一起进行计算，即训练神经网络并使用它们进行预测；然而，出于一些理由，他们不愿意泄露学习好的模型。同时假定有些用户愿意在保持私密的前提下提供训练数据，有些用户也有兴趣在他们的输入保持私密的前提下使用学习好的模型。为了能够做到这一点，我们需要安全地在特定精度下计算有理数；具体而言，对它们做加法和乘法。我们同时需要计算sigmoid函数1/(1+np.exp(-x)，这一函数的传统形式在安全设定下会导致惊人沉重的运算。因此，我们将依照基于Numpy实现同态加密神经网络中的做法，使用多项式逼近sigmoid函数，不过我们会进行一点优化。安全多方计算同态加密（Homomorphic Encryption，HE）和安全多方计算（secure Multi-Party Computation，MPC）是现代密码学中密切相关的两个领域，常常互相使用对方的技术以便解决大致相同的问题：计算接受私密数据输入的函数而不泄露任何东西，除了（可选）最终输出。例如，在我们的私密机器学习设定下，两种技术可以用来训练我们的模型并进行预测（不过在HE的情形下，如果数据来自使用不同加密钥的用户，需要做一些专门的技术处理）。就其本身而言，从高层看，HE经常可以用MPC替换，反之亦然。至少就今天而言，两者的区别大致是HE不怎么需要交互，但是需要昂贵的计算，而MPC的计算很廉价，但需要大量交互。换句话说，MCP用两方或多方间的交互取代了昂贵的计算。目前而言，这在实践中提供了更好的性能，以至于人们可以主张MCP是明显更成熟的技术作为这一主张的依据，已经存在好几家公司提供基于MPC的服务。定点数算术运算将在一个有限域上进行，因此我们首先需要决定如何将有理数r表示为域元素，即取自0, 1, ., Q-1的整数x（Q为质数）。我们将采用典型的做法，根据固定的精度放大每个有理数，比如，在6位精度的情形下，我们将放大10*6倍，然后将结果的整数部分作为定点数表示。例如，Q = 10000019时，我们得到encode(0.5) = 500000和encode(-0.5) = 10000019 - 500000 = 9500019。def encode(rational):upscaled = int(rational * 10*6)field_element = upscaled % Qreturn field_elementdef decode(field_element):upscaled = field_element if field_element te(w)return v不过还有一个问题，如前所述，reconstruct(w)具有双精度：它编码时使用的放大因子是10*6 * 10*6，而不是10*6。在不安全设定下，我们本可以通过标准的除法（除以10*6）来修正这一点，然而，由于我们操作的是有限域中的秘密共享元素，这变得不那么直截了当了。除以一个公开的常量，这里是10*6，足够简单：我们直接将部分乘以其域中的逆元素10*(-6)。对某v和u RSE)return d注意上面的imul是本地操作，将每个共享部分乘以公开的常数，这里是10*6的域中逆元素。安全数据类型最后，我们将以上过程包裹进一个定制的抽象数据类型，这样我们之后表达神经网络的时候就可以使用NumPy了。classSecureRational(object):def _init_(self, secret=None):self.shares = share(encode(secret) if secret isnotNoneelse return zdef reveal(self):return decode(reconstruct(reshare(self.shares)def _repr_(self):return"SecureRational(%f)" % self.reveal()def _add_(x, y):z = SecureRational()z.shares = add(x.shares, y.shares)return zdef _sub_(x, y):z = SecureRational()z.shares = sub(x.shares, y.shares)return zdef _mul_(x, y):z = SecureRational()z.shares = mul(x.shares, y.shares)return zdef _pow_(x, e):z = SecureRational(1)for _ in range(e):z = z * xreturn z基于这一类型，我们可以安全地对这样的值进行操作：x = SecureRational(.5)y = SecureRational(-.25)z = x * yassert(z.reveal() = (.5) * (-.25)此外，需要调试的时候，我们可以切换为不安全类型而不需要修改其余（神经网络）代码。再比如，我们可以隔离计数器的使用，查看进行了多少次乘法，进而让我们模拟下需要多少通讯。深度学习这里用“深度学习”这个术语属于夸夸其谈，因为我们只是简单地摆弄了下基于Numpy实现同态加密神经网络中的神经网络学习基本布尔值函数。一个简单函数第一个实验是训练网络以识别序列中的第一位。下面的代码中，X中的四行是输入的训练数据，y中相应的列是所需输出。X = np.array(0,0,1,0,1,1,1,0,1,1,1,1)y = np.array(0,0,1,1).T我们将使用同样的双层网络，不过我们会将下面定义的sigmoid逼近函数作为参数。secure函数是一个简单的辅助函数，将所有值转换为我们的安全数据类型。classTwoLayerNetwork:def _init_(self, sigmoid):self.sigmoid = sigmoiddef train(self, X, y, iterations=1000):# 初始化权重self.synapse0 = secure(2 * np.random.random(3,1) - 1)# 训练for i in range(iterations):# 前向传播layer0 = Xlayer1 = self.sigmoid.evaluate(np.dot(layer0, self.synapse0)# 反向传播layer1_error = y - layer1layer1_delta = layer1_error * self.sigmoid.derive(layer1)# 更新self.synapse0 += np.dot(layer0.T, layer1_delta)def predict(self, X):layer0 = Xlayer1 = self.sigmoid.evaluate(np.dot(layer0, self.synapse0)return layer1同时，我们将使用原文提出的sigmoid逼近，即标准麦克劳林/泰勒多项式的前五项。出于可读性考虑，我这里用了一个简单多项式演算，有待进一步优化，比如使用秦九韶算法减少乘法的数目。classSigmoidMaclaurin5:def _init_(self):ONE = SecureRational(1)W0  = SecureRational(1/2)W1  = SecureRational(1/4)W3  = SecureRational(-1/48)W5  = SecureRational(1/480)self.sigmoid = np.vectorize(lambda x: W0 + (x * W1) + (x*3 * W3) + (x*5 * W5)self.sigmoid_deriv = np.vectorize(lambda x: (ONE - x) * x)def evaluate(self, x):return self.sigmoid(x)def derive(self, x):return self.sigmoid_deriv(x)实现了这个之后我们就可以训练和演算网络了（细节见notebook），这里使用了10000次迭代。# 设置随机数种子以获得可复现的结果random.seed(1)np.random.seed(1)# 选择逼近sigmoid = SigmoidMaclaurin5()# 训练network = TwoLayerNetwork(sigmoid)network.train(secure(X), secure(y), 10000)# 演算预测evaluate(network)注意训练数据在输入网络之前是安全共享的，并且学习到的权重从未泄露。预测同理，只有网络的用户知道输入和输出。Error: 0.00539115Error: 0.0025606125Error: 0.00167358Error: 0.001241815Error: 0.00098674Error: 0.000818415Error: 0.0006990725Error: 0.0006100825Error: 0.00054113Error: 0.0004861775Layer0 weights:SecureRational(4.974135)SecureRational(-0.000854)SecureRational(-2.486387)Prediction on 000: 0 (0.50000000)Prediction on 001: 0 (0.00066431)Prediction on 010: 0 (0.49978657)Prediction on 011: 0 (0.00044076)Prediction on 100: 1 (5.52331855)Prediction on 101: 1 (0.99969213)Prediction on 110: 1 (5.51898314)Prediction on 111: 1 (0.99946841)从上面的演算来看，神经网络确实看起来学习到了所要求的函数，在未见输入上也能给出正确的预测。稍微高级些的函数在下一个实验中，神经网络无法像之前一样镜像三个组件的其中一个，从直观上说，需要计算第一位和第二位的异或（第三位是偏离）。X = np.array(0,0,1,0,1,1,1,0,1,1,1,1)y = np.array(0,1,1,0).T如Numpy实现神经神经网络：反向传播一文所解释的，使用双层神经网络只能给出无意义的结果，本质上是在说“让我们扔一枚硬币吧”。Error: 0.500000005Error: 0.5Error: 0.5000000025Error: 0.5000000025Error: 0.5Error: 0.5Error: 0.5Error: 0.5Error: 0.5Error: 0.5Layer0 weights:SecureRational(0.000000)SecureRational(0.000000)SecureRational(0.000000)Prediction on 000: 0 (0.50000000)Prediction on 001: 0 (0.50000000)Prediction on 010: 0 (0.50000000)Prediction on 011: 0 (0.50000000)Prediction on 100: 0 (0.50000000)Prediction on 101: 0 (0.50000000)Prediction on 110: 0 (0.50000000)Prediction on 111: 0 (0.50000000)提议的补救措施是在网络中引入另一层：classThreeLayerNetwork:def _init_(self, sigmoid):self.sigmoid = sigmoiddef train(self, X, y, iterations=1000):# 初始权重self.synapse0 = secure(2 * np.random.random(3,4) - 1)self.synapse1 = secure(2 * np.random.random(4,1) - 1)# 训练for i in range(iterations):# 前向传播layer0 = Xlayer1 = self.sigmoid.evaluate(np.dot(layer0, self.synapse0)layer2 = self.sigmoid.evaluate(np.dot(layer1, self.synapse1)# 反向传播layer2_error = y - layer2layer2_delta = layer2_error * self.sigmoid.derive(layer2)layer1_error = np.dot(layer2_delta, self.synapse1.T)layer1_delta = layer1_error * self.sigmoid.derive(layer1)# 更新self.synapse1 += np.dot(layer1.T, layer2_delta)self.synapse0 += np.dot(layer0.T, layer1_delta)def predict(self, X):layer0 = Xlayer1 = self.sigmoid.evaluate(np.dot(layer0, self.synapse0)layer2 = self.sigmoid.evaluate(np.dot(layer1, self.synapse1)return layer2然而，如果我们采用之前的方式训练网络，即使仅仅迭代100次，我们都将面临一个奇怪的现象：突然之间，误差、权重、预测分数爆炸了，给出混乱的结果。Error: 0.496326875Error: 0.4963253375Error: 0.50109445Error: 4.50917445533e+22Error: 4.20017387687e+22Error: 4.38235385094e+22Error: 4.65389939428e+22Error: 4.25720845129e+22Error: 4.50520005372e+22Error: 4.31568874384e+22Layer0 weights:SecureRational(970463188850515564822528.000000)SecureRational(1032362386093871682551808.000000)SecureRational(1009706886834648285970432.000000)SecureRational(852352894255113084862464.000000)SecureRational(999182403614802557534208.000000)SecureRational(747418473813466924711936.000000)SecureRational(984098986255565992230912.000000)SecureRational(865284701475152213311488.000000)SecureRational(848400149667429499273216.000000)SecureRational(871252067688430631387136.000000)SecureRational(788722871059090631557120.000000)SecureRational(868480811373827731750912.000000)Layer1 weights:SecureRational(818092877308528183738368.000000)SecureRational(940782003999550335877120.000000)SecureRational(909882533376693496709120.000000)SecureRational(955267264038446787723264.000000)Prediction on 000: 1 (41452089757570437218304.00000000)Prediction on 001: 1 (46442301971509056372736.00000000)Prediction on 010: 1 (37164015478651618328576.00000000)Prediction on 011: 1 (43504970843252146044928.00000000)Prediction on 100: 1 (35282926617309558603776.00000000)Prediction on 101: 1 (47658769913438164484096.00000000)Prediction on 110: 1 (35957624290517111013376.00000000)Prediction on 111: 1 (47193714919561920249856.00000000)导致这一切的原因很简单，但也许乍看起来不是那么明显（至少对我而言）。尽管（前五项）麦克劳林/泰勒逼近sigmoid函数在前面的网络中表现良好，当我们进一步推进时，它完全崩塌了，产生的结果不仅不精确，而且数量级也不对。因此很快摧毁了我们可能使用的任何有穷数字表示，即使在非安全设定下也是如此，数字开始溢出了。技术上说sigmoid函数演算的点积变得太大了，就我所知，这意味着神经网络变得非常自信。就此而言，问题在于我们的逼近不允许神经网络变得足够自信，否则精确度会非常糟糕。我不清楚基于Numpy实现同态加密神经网络是如何避免这一问题的，我最好的猜测是较低的初始权重和alpha更新参数使它可能在迭代次数较低的情形下绕过这个坑（看起来是少于300次迭代）。无比欢迎任何关于这方面的评论。逼近sigmoid既然是我们的sigmoid逼近阻碍了我们学习更高级的函数，那么很自然地，我们接下来尝试使用麦克劳林/泰勒多项式的更多项。如下所示，加到第9项（而不是第5项）确实能稍微增加一点进展，但这点进展远远不够。此外，它塌得更快了。Error: 0.49546145Error: 0.4943132225Error: 0.49390536Error: 0.50914575Error: 7.29251498137e+22Error: 7.97702462371e+22Error: 7.01752029207e+22Error: 7.41001528681e+22Error: 7.33032620012e+22Error: 7.3022511184e+22.或者我们该转而使用更少的项以更好地牵制崩塌？比如，只加到第3项？这确实有点作用，能让我们在崩塌之前训练500次迭代而不是100次。Error: 0.4821573275Error: 0.46344183Error: 0.4428059575Error: 0.4168092675Error: 0.388153325Error: 0.3619875475Error: 0.3025045425Error: 0.2366579675Error: 0.19651228Error: 0.1748352775Layer0 weights:SecureRational(1.455894) SecureRational(1.376838)SecureRational(-1.445690) SecureRational(-2.383619)SecureRational(-0.794408) SecureRational(-2.069235)SecureRational(-1.870023) SecureRational(-1.734243)SecureRational(0.712099) SecureRational(-0.688947)SecureRational(0.740605) SecureRational(2.890812)Layer1 weights:SecureRational(-2.893681)SecureRational(6.238205)SecureRational(-7.945379)SecureRational(4.674321)Prediction on 000: 1 (0.50918230)Prediction on 001: 0 (0.16883382)Prediction on 010: 0 (0.40589161)Prediction on 011: 1 (0.82447640)Prediction on 100: 1 (0.83164009)Prediction on 101: 1 (0.83317334)Prediction on 110: 1 (0.74354671)Prediction on 111: 0 (0.18736629)然而，误差和预测很糟糕，也没有多少空间供增加迭代次数了（大约在550次迭代处崩塌）。插值作为替代，我们可以放弃标准多项式逼近，转而尝试在区间上进行多项式插值。这里主要的参数是多项式的项数，我们希望它保持在一个较低的值，以提高效率。不过，系数的精度也是相关参数。# 我们想要逼近的函数f_real = lambda x: 1/(1+np.exp(-x)# 我们想要优化的区间interval = np.linspace(-10, 10, 100)# 给定项数，进行多项式插值degree = 10coefs = np.polyfit(interval, f_real(interval), degree)# 降低插值系数的精度precision = 10coefs = int(x * 10*precision) / 10*precision for x in coefs # 逼近函数f_interpolated = np.poly1d(coefs)一同绘制标准逼近和插值多项式（红色曲线）的图像我们看到了改进的希望：我们无法避免在某点崩塌，但它的崩塌点显然要大很多。当然，我们也可以尝试其他项数、精度、区间的组合，如下所示，不过对我们的应用而言，上面的参数组合看起来已经足够了。现在让我们回到我们的三层网络，我们定义一个新的Sigmoid逼近：classSigmoidInterpolated10:def _init_(self):ONE = SecureRational(1)W0  = SecureRational(0.5)W1  = SecureRational(0.2159198015)W3  = SecureRational(-0.0082176259)W5  = SecureRational(0.0001825597)W7  = SecureRational(-0.0000018848)W9  = SecureRational(0.0000000072)self.sigmoid = np.vectorize(lambda x: W0 + (x * W1) + (x*3 * W3) + (x*5 * W5) + (x*7 * W7) + (x*9 * W9)self.sigmoid_deriv = np.vectorize(lambda x:(ONE - x) * x)def evaluate(self, x):return self.sigmoid(x)def derive(self, x):return self.sigmoid_deriv(x)然后开始训练：# 设置随机数种子以获得可复现的结果random.seed(1)np.random.seed(1)# 选择逼近sigmoid = SigmoidInterpolated10()# 训练network = TwoLayerNetwork(sigmoid)network.train(secure(X), secure(y), 10000)# 演算预测evaluate(network)现在，尽管我们运行了10000次迭代，没有发生崩塌，预测表现也提升了，只有一个预测错误（0 1 0）。Error: 0.0384136825Error: 0.01946007Error: 0.0141456075Error: 0.0115575225Error: 0.010008035Error: 0.0089747225Error: 0.0082400825Error: 0.00769687Error: 0.007286195Error: 0.00697363Layer0 weights:SecureRational(3.208028) SecureRational(3.359444)SecureRational(-3.632461) SecureRational(-4.094379)SecureRational(-1.552827) SecureRational(-4.403901)SecureRational(-3.997194) SecureRational(-3.271171)SecureRational(0.695226) SecureRational(-1.560569)SecureRational(1.758733) SecureRational(5.425429)Layer1 weights:SecureRational(-4.674311)SecureRational(5.910466)SecureRational(-9.854162)SecureRational(6.508941)Prediction on 000: 0 (0.28170669)Prediction on 001: 0 (0.00638341)Prediction on 010: 0 (0.33542098)Prediction on 011: 1 (0.99287968)Prediction on 100: 1 (0.74297185)Prediction on 101: 1 (0.99361066)Prediction on 110: 0 (0.03599433)Prediction on 111: 0 (0.00800036)注意错误情形的分数不是完全偏离，某种程度上和正确预测的零值有所不同。再运行5000次迭代看起来不会改善这一点，这时我们已经快要崩塌了。结语本文重点介绍了一个简单的安全多方计算协议，而没有显式地论证开头提到的安全多方计算比同态加密更高效。我们看到，使用非常基本的操作实现私密机器学习确实是可能的。也许更需要批评的是我们没有测量运行协议需要的通讯量，主要是每次乘法时所需交换的一些消息。基于这一简单的协议进行大量计算的话，显然让三方通过高速局域网连接会比较好。不过更高级的协议不仅减少了来回收发的数据量，同时改善了其他性质，比如回合数（像乱码电路（garbled circuits）就可以将回合数压到一个小常数）。最后，本文基本上将协议和机器学习过程看成是正交的，让后者仅仅以一种黑盒的方式使用前者（除了sigmoid计算）。两者更好的配合需要两个领域的专门知识，但可能显著地提升总体性能。