FALCON：基于傅里叶变换的快速安全卷积神经网络预测方法

87050FALCON：一种基于傅里叶变换的快速和安全的卷积神经网络预测方法0Shaohua Li 1 Kaiping Xue 1 Bin Zhu 1 Chenkai Ding 1 Xindi Gao 1 David Wei 2 Tao Wan 301中国科学技术大学 2福特汉姆大学 3CableLabs0lshhsl@mail.ustc.edu.cn kpxue@ustc.edu.cn { cnzb01, chimkie, khronos } @mail.ustc.edu.cn0dsl.wei01@gmail.com t.wan@cablelabs.com0摘要0深度学习作为一种服务已被广泛部署，利用深度神经网络模型提供预测服务。然而，这引起了隐私问题，因为客户需要将敏感信息发送到服务器。在本文中，我们关注的是客户希望使用托管在服务器上的卷积神经网络模型对私人图像进行分类的场景，同时双方都保持其数据的私密性。我们提出了一种名为FALCON的快速和安全的基于快速傅里叶变换的卷积神经网络预测方法。我们的解决方案利用完全同态加密，使得卷积神经网络模型的线性层可以简单高效地进行评估。我们还引入了第一个高效且保护隐私的softmax函数协议，这是卷积神经网络中不可或缺的组成部分，在以前的工作中由于其高复杂性尚未得到评估。01. 引言0深度学习已经应用于许多领域，以克服传统数据处理方法的局限性，例如图像分类[19, 17]、语音识别[3,4]、医学诊断[28,11]等。一些公司和机构也投资于深度学习技术，并训练自己的深度神经网络模型，为用户提供付费或免费服务。例如，Google Vision[9]为开发者和普通用户提供了一个用于图像分类的API，用户可以将图像上传到云端以获取分类结果及其对应的概率。尽管这些服务为用户提供了丰富的体验，但它们也引起了严重的隐私问题，因为上传的用户数据可能包含私人信息[29]，例如人脸照片和X射线图像。尽管许多公司声称他们永远不会泄露或利用用户的数据进行商业用途，但不断增加的数据泄露事件提醒我们，他们的承诺并没有任何保证[2]。0当然，客户的输入数据不是唯一的敏感信息，因为对于服务器来说，它们自己的模型也需要受到来自对抗性客户的保护。首先，模型可能是使用大量私人数据进行训练的，例如医疗记录，以获得用于疾病预测的模型。因此，如果将训练好的模型披露给恶意客户，可能会从中提取出敏感信息[30,31]。其次，模型参数和详细的预测结果，即对所有类别的准确概率，可以用于生成对抗性示例，欺骗深度学习模型，导致错误的分类结果[27,8]。第三，许多预测模型本身，即使不考虑敏感的训练数据，也需要知识产权保护，不能向包括客户在内的第三方披露[21,18]。为了解决这个问题，研究人员提出了一种安全的深度学习场景，其中服务器拥有一个模型，客户拥有数据，这两者以一种方式进行交互，以便客户可以在不向服务器泄露任何信息的情况下获得预测结果，同时对模型一无所知。他们通常使用同态加密（例如CryptoNets[15]）、安全多方计算[34]（例如MiniONN[21]）或它们的组合（例如GAZELLE[18]）进行安全评估。在本文中，我们关注的是卷积神经网络（CNNs）的快速和安全解决方案，CNNs是深度学习中最重要的神经网络之一。CNNs的特点是空间输入数据，例如图像和语音。通常，CNN模型由卷积、激活、池化和全连接层组成，并且通常后面跟着一个softmax层。卷积和全连接层具有线性特性，而激活和池化是非线性层。softmax层用于将输出归一化为概率，通常用作CNN的最后一层。softmax层在许多用例中是不可或缺的。例如，CNN模型将X射线图像分类为“肺炎”，概率为5%。尽管“肺炎”是最高标签，但实际结果表明，患者可能没有这种疾病，这87060没有概率输出的情况下无法得知最终结果。由于softmax函数涉及除法和指数运算，在使用隐私工具进行计算时会引入极高的开销，现有的工作（例如CryptoNets、MiniONN和GAZELLE）使用argmax函数代替softmax函数仅获取最高的一个标签。然而，我们提出了一种新颖的高效协议用于softmax层。本文提出了用于快速和安全的卷积神经网络预测的FALCON。我们的贡献可以总结如下：0•对于卷积层和全连接层，我们使用完全同态加密来保护它们，并通过基于快速傅里叶变换（FFT）的密文计算实现高效率。0•对于ReLU和池化层，我们提出了一种安全的两方计算协议来评估它们。我们的优化处理流程进一步提高了它们的计算效率。0•对于Softmax函数，任何先前的工作都未解决其安全计算问题。我们提出了一个近似定理来简化softmax函数的计算，基于该定理我们实现了第一个安全高效的两方softmax计算协议。02. 相关工作0CryptoNets[15]启发我们使用分级同态加密（LHE）来安全处理神经网络模型。由于只使用了LHE，CryptoNets需要用线性函数替换非线性激活和池化函数，并重新训练模型。SecureML[23]提出了基于安全两方计算的协议，用于在两个非合谋的服务器之间训练多种机器学习模型。DeepSecure[25]仅使用了Yao的GarbledCircuits来实现半可信客户端和服务器之间的可扩展执行神经网络模型。Chameleon[24]使用了加法秘密共享[6]、Yao的GarbledCircuits[34]和GMW协议[16]来实现安全的CNN评估，但需要额外的半诚实第三方。MiniONN[21]将神经网络模型转化为遗忘版本，并使用加法同态加密首先生成乘法三元组，然后使用安全两方计算高效地评估模型。GAZELLE[18]利用完全同态加密，并为保护卷积和矩阵-向量乘法操作设计了高效的方案。GAZELLE在卷积层和全连接层使用同态加密，在ReLU和池化层使用安全两方计算。由于MiniONN和GAZELLE优于所有先前的工作，我们将FALCON与它们进行比较以展示我们的性能优势。02.1. 构建模块02.2. 快速傅里叶变换0在图像处理中，著名的快速傅里叶变换（FFT）是一种可以将图像从空间域转换为频率域表示的算法，反之亦然[33]。设 f(x, y) 表示图像在点 (x, y) 处的像素值，经过FFT后，f(x,y) 将变为复数 Ff(u, v)。为简单起见，我们将输入 x的FFT表示为F(x)。本文使用的FFT的一个重要特性是线性性，即对于两个输入 x 和 y，我们有：F(x) + F(y) = F(x + y)。（1）0FFT还有一个重要的卷积定理：空间域中的卷积等效于频率域中的逐点乘积。将F-1表示为逆FFT，x和y之间的卷积可以通过以下方式计算：x * y = F-1(F(x) ∙ F(y))。（2）02.2.1 基于格的同态加密。0为了在FALCON中实现保护隐私的卷积，我们需要两种同态操作：SIMDAdd和SIMDMul。这里的SIMD表示我们可以将一个明文元素的向量打包到一个密文中，并对与每个明文元素对应的密文进行计算，从而减少所需的密文大小和计算时间。SIMDAdd表示两个密文之间的同态加法，而SIMDMul表示密文和明文之间的同态乘法。所有这些要求都可以通过现代基于格的同态加密系统[14, 12,7]来满足。这些方案中有三个必需的参数，即明文槽的数量n，明文模数p和密文模数q。参数n是以SIMD方式处理的最大数据数量。参数p限制了明文数据的范围。参数q可以根据给定的n和p计算得出。在本文中，我们将x的密文表示为[x]。02.2.2 安全双方计算。0安全双方计算协议允许两个参与方在保护隐私的同时共同评估彼此的私有数据上的函数。函数被表示为布尔电路，然后由这些协议计算。Yao的GarbledCircuits是这类协议的一种典型实现，本文将在客户端和服务器之间的安全计算中使用它。ABY框架[10]是一个支持安全双方计算的开源库，我们使用这个库来实现安全的ReLU、最大池化和softmax层。该库封装了几个基本操作0flattenPneumonia 0.61Cardiopathy 0.1587070�0w0h0卷积层0激活层 池化层0�0FC层0logits0Softmax0Softmax层0c0k0�0ReLU0图1. 卷积神经网络示例。0用于安全计算，我们在这里介绍本文中使用的操作（注意，以下内容中使用的术语“份额”指的是Yao分享，这是Yao的Garbled Circuits使用的一种分享类型）：0- ADDGate(a,b)对输入份额a和b执行算术加法，并将结果作为份额返回。- SUBGate(a,b)对输入份额a和b执行算术减法，并将结果作为份额返回。- GTGate(a, b)执行三元操作“a > b ? 1 : 0”，如果a >b，则返回1，否则返回0。- MUXGate(a, b,s)作为多路复用器执行，并在s为1时返回a，在s为0时返回b。03. FALCON执行流程0考虑这样的场景，医生想要从X射线图像中了解患者可能患有的疾病，仅知道顶部标签而没有相应的概率可能会导致不可靠的诊断结果。例如，输出的顶部标签“肺炎”和概率“0.9”和“0.1”肯定具有不同的治疗意义。在本节中，我们将概述使用图1中所示的卷积神经网络的执行流程。系统模型。我们考虑一个客户C，他想要使用服务器S持有的卷积神经网络模型来预测一个输入（例如X射线图像）。对于客户C，输入是私有的。对于服务器S，卷积和全连接层的参数也是私有的。我们的设计目标是在评估CNN模型时保护双方的隐私。我们假设C和S都是半诚实的。也就是说，他们遵守FALCON协议定义的执行流程，同时尽可能多地了解对方的私人信息。隐私保证。对于服务器S，FALCON保护以下关于模型的信息：所有卷积和全连接层的权重参数，以及卷积层的滤波器大小。FALCON不隐藏模型的架构，即层的类型、层的大小（层中的神经元数量）和层数。对于客户C，FALCON不泄露输入内容的任何信息，但不保护输入大小。高层次的执行流程。在开始时，C持有一个输入向量x和私钥，S持有神经网络模型。为了评估第一层，通常是卷积层，C加密0x的FFT，表示为[F(x)]，并将其传输给S。然后，S和C一起执行以下操作：01.（评估卷积层）S使用[F(x)]将卷积层馈送，并获得输出[F(y)]，其中y是明文输出。为了计算下一激活层，S和C将分别持有y的加法份额，即xS + xC =y。这可以通过提议的翻译方法来完成（详见第4.2节）。02.（评估ReLU层）对于ReLU层，S和C运行设计好的ReLU函数的布尔电路。注意，我们仍然要求输出值由两个参与方进行加法共享。（详见第4.3.2节。）03.（评估池化层）在两个加法共享上评估平均池化函数很简单。我们可以让这两个参与方分别对其共享进行平均池化。对于最大池化，我们还设计了布尔电路来实现它。注意，与ReLU一样，我们需要确保S和C对输出值进行加法共享。（详见第4.3.3节。）04.（评估FC层）通常，FC层被视为矩阵乘法。在我们的设计中，我们首先将该层转换为等效的卷积层，然后使用与卷积层相同的方法进行评估。注意，该层的输入由S和C进行加法共享，因此我们需要根据第4.1节中的描述将共享转换为密文。（详见第4.4节。）05.（评估softmax层）softmax函数的输入通常是FC层的输出。在我们的设计中，我们首先使S和C对输入进行加法共享。然后，我们将softmax函数分解为最大值和内积函数，以使客户端C能够高效地获得具有概率的目标类别。（详见第4.5节。）04. FALCON设计04.1. 设置0在进入每个层的实现细节之前，我们首先介绍加密方法和密文与加法共享之间的转换。在开始时，客户端C持有输入x并需要将其密文传输给服务器S。在我们的设计中，所有密文对应于频域中的明文数据。87080也就是说，对于尺寸为w×h的输入x，客户端C首先执行FFT以获得F(x)，然后对其进行加密得到[F(x)]。F(x)继承了x的尺寸，但其中的每个元素都是一个复数，例如F(x)0,0=a+bj，其中a和b是实数。注意我们不能直接对复数应用同态加密。因此，我们让客户端C分别加密实部（例如a）和虚部（例如b）为两个密文。也就是说，对于F(x)中的每个元素，C将所有实部打包成一个明文向量并加密该向量，记为[F(x)R]。相应地，所有虚部的密文记为[F(x)I]。FALCON中涉及的所有密文都具有这种形式。线性层（例如卷积层和全连接层）的输出是一个密文，而非线性层的输入是加法共享。因此，在将线性层的输出馈送到非线性层之前，我们需要从密文转换为加法共享。假设线性层的输出是[F(y)]，实际上是[F(y)R]和[F(y)I]，服务器S和客户端C的目标分别是分别获得xS和xC，满足xS+xC=y，并且保证S或C都不会泄露关于y的任何信息。为了实现这个目标，S生成与y相同尺寸的随机向量r，并执行FFT以获得F(r)R和F(r)I。使用SIMDAdd，S以同态方式将这些值添加到密文中，得到[F(y)R−F(r)R]和[F(y)I−F(r)I]。回顾FFT的线性性质（见公式1），我们有[F(y)R−F(r)R]=[F(y−r)R]和[F(y)I−F(r)I]=[F(y−r)I]。客户端C对其进行解密，并将虚部与实部组合起来获得F(y−r)，然后执行逆FFT以获得(y−r)。令xS=r和xC=(y−r)，我们得到了y的加法共享。要从加法共享转换为密文，即将非线性层的输出馈送到线性层，我们可以运行上述过程的逆过程。注意，FALCON在Zp中工作，其中p是同态加密的选择明文模数。对于任何中间值xm，xm<�p/2�意味着xm是正数，否则是负数。04.2. 安全卷积层0Conv层的输入图像（或特征图）为大小为w×h×c的x，其中w和h分别为宽度和高度，c为通道数。我们假设Conv层中总共有k个滤波器（或卷积核），每个滤波器的大小为fw×fh×c。在这部分中，我们首先介绍一个简单的情况，其中输入只有一个通道（c=1），层中只有一个滤波器（k=1），以展示我们的关键思想。然后我们描述一个更一般的情况，其中c>1且k>1。0简单情况（c=1，k=1）。首先，客户端C对大小为w×h的输入x执行FFT，得到F(x)R和F(x)I；服务器S对大小为fw×fh的滤波器fi执行FFT，得到0F(fi)R和F(fi)I。其次，客户端C将FFT结果加密为[F(x)R]和[F(x)I]，并将它们发送给服务器。假设x和fi的卷积结果为y，服务器S进行以下计算：0[F(y)R]=[F(x)R]�F(fi)R⊕[F(x)I]�(-F(fi)I)，[F(y)I]=[F(x)R]�F(fi)I⊕[F(x)I]�F(fi)R，0其中“�”表示SIMDMul，“⊕”表示SIMDAdd。然后S生成一个大小为w×h的随机向量r，并将其FFT值加密为[-F(r)R]和[-F(r)I]。最后，S将以下两个密文发送给C：0[F(y-r)R]=[F(y)R]⊕[-F(r)R]，[F(y-r)I]=[F(y)I]⊕[-F(r)I]。0客户端C解密密文，将实部与虚部相结合，并执行逆FFT以获得(y-r)，设置为C的共享xC。然后，服务器S将r设置为其共享xS。此时，卷积层已经被评估，结果y由S和C进行加法共享。0一般情况。为了清楚地展示我们的思想，我们首先解释如何在明文域和密文域中计算卷积。（明文域）对于包含c个通道fi（i∈[1,k]）和包含c个通道x1，x2，...，xc的输入x，首先，使用FFT对c×2-D滤波器和c×2-D输入进行变换，然后将相应的通道相乘得到c个中间结果。最后，将这些中间结果相加以在频域中获得最终输出。（密文域）将这些2-D滤波器和输入视为c个独立的组，服务器S对这些组应用在简单情况中显示的计算过程，得到c个中间密文，然后在使用随机向量r进行掩码后将它们返回给客户端C。C在明文域中解密这些密文并将它们相加。设y表示实际输出值，此时，S和C的共享分别为r和y-r。0安全分析。客户端C的输入数据、权重参数和滤波器的大小需要保护。由于在服务器S的评估过程中输入数据保持加密状态，因此数据是受保护的。客户端C只能获得掩码卷积结果，因此对权重参数一无所知。由于滤波器被填充到与输入相同的大小，它们的大小也得到了保留。04.3. 安全激活层和池化层0在接下来的内容中，我们首先介绍数据预处理，将加法共享转换为Yao共享。它还保证了Yao共享位于[0,p)之间。然后我们介绍ReLU和Max Pooling的实现。......Listing 3. Function description of Max Pooling.Listing 4. Function description of our Max Pooling and ReLU.proach, we can see that the number of max() operations inthe Max Pooling layer does not change, but the ReLU layeris reduced greatly. For a Max Pooling layer with (2 × 2) re-gion with a stride of 2, our method can save 75% of ReLUoperations. The pseudocode is shown in Listing 4. We firstapply Max Pooling operations to obtain max values of eachregion (line 9-14), and ReLU operations follow to filter outall negative values (line 16-17).-556-3312 -77-2 -7 -3 -99-6 -1 -6ReLU0560312070000900012790Max Pooling-556-3312 -77-2 -7 -3 -99-6 -1 -61279-1Max Pooling12790ReLUOriginal:Ours:Figure 4. Original ReLU and Max Pooling v.s. Ours.4.3.5Output circuits for ReLU and Max PoolingThe original outputs of ReLU or Max Pooling circuits arein the form of Yao sharing. Our aim is to additively sharethe result between C and S. This can be achieved by takingthe output y and a random vector (−r mod p) generated byS as two inputs of data preprocessing circuits, the result ofwhich is (y − r mod p) and is sent to C.Security analysis. Since ReLU and Max Pooling layers donot have private model parameters, we only focus on theconfidentiality of the input. Due to the security of Yao’sGarbled Circuits, the input data are hidden.4.4. Secure Fully Connected LayerNormally, a FC layer can be treated as multiplication of aweight matrix and an input vector, and this can be executedvery fast in the plaintext domain. However, in the ciphertextdomain, this kind of multiplication is expensive. Inspiredby the observation that FC layers can be viewed as convo-lutional layers with filters that cover the entire input regions[22], we propose an efficient solution by transforming theFC layer to the convolutional layer first, then utilizing theacceleration method in Section 4.2 to evaluate the FC layer.4.5. Secure Softmax LayerIn classification CNNs, the last FC layer is always fol-lowed by a softmax layer to generate probability distribu-tion over K different possible classes. However, to our bestknowledge, in all previous work, researchers presented thatthe server can return logits to the client, who could obtainprobabilities by performing softmax function locally, e.g.GAZELLE, or the client runs argmax using secure two-party computation to only obtain the classification resultwithout knowing logits and probabilities, e.g. MiniONN.The main reason why these schemes bypass the encryptedcomputation is that implementing softmax function wouldintroduce high computation complexity, no matter using ho-momorphic encryption or secure two-party protocols.This high computation overhead is due to the divisionand exponentiation operations in the softmax function andwe thus propose a division and exponentiation free protocolin FALCON. We notice that in a client-server scenario, byonly accessing prediction results, C is able to extract modelinformation [32, 30, 26]. To tackle this issue, S can onlyreturn necessary results, i.e., the class to which the inputbelongs and its corresponding probability, to C. Softmaxfunction is given byf(x)i =exi�Kk=1 exk ,for i = 1, 2, · · · , K,where f(x)i is the probability that the input belongs to theclass i. Letting the target class be t, our aim is to calculatept =ext�Kk=1 exk . Before moving to the detailed protocols,we first give the following theorem:Theorem 1. (Approximation Theorem) For pt =ext�Kk=1 exk ,where xt = max(x1, · · · , xK), and p′t =ext�xk≥xt−mexk ,where m ≥ ln�(10l − 1)(K − 1)�and l ≥ 1, we have|pt − p′t| ≤ 10−l.(The proof can be found in the full version [20].)This theorem shows that in the case of a precision re-quirement of 10−l, we can replace pt with p′t. In anotherword, we can set a threshold xt − m to filter all values lessthan xt − m. Also, p′t can be written as8710p′t =ext�xk≥xt−mexk =ext/ext−m�xk≥xt−mexk/ext−m=em�xk≥xt−mexk−(xt−m) ,where all the intermediate values are limited to�e0, em�,which enables us to use a small bit length to evaluate thesecure softmax with Yao’s Garbled Circuits. For example,for l = 10−3 and K = 100, we have m ≥ ln(10−3 ∗ 100 −100) ≈ 11.52, and e12 takes only 18 bits, while the originalxt may reach up to > 100 [8] and e100 takes 145 bits. Basedon the above analysis, the outline protocol of our proposedsecure softmax is as follows:1. Let [F(x)], where x = {x1, x2, · · · , xK} be the inputto the softmax layer. Server S masks it with a randomvector r, and sends [F(x − r)] to client C. Then S setsits share to xS = r = {r1, r2, · · · , rK} mod p.2. TheclientCdecrypts[F(x − r)]andper-formstheinverseFFTtoobtain(x−r).ThenCsetsitssharetoxC=x − r={x1 − r1, x2 − r2, · · · , xK − rK} mod p.3. Now C and S interact with each other to find the maxi-mum value xt and decide which xi can be ignored ac-cording to the selected integer m, and set the ignoredone and the left xi to 0 and m − (xt − xi), respec-tively. To be noted, the plaintext modulo is convertedto (m + 1), and there no longer exist negative values.At the end of this procedure, C and S hold newly gen-erated shares, xS = {r′1, r′2, · · · , r′K} mod (m + 1) andxC = {x′1 − r′1, x′2 − r′2, · · · , x′K − r′K} mod m + 1,where x′i is 0 or m − (xt − xi) and r′i is randomly gen-erated by S.4. Next, to calculate the denominator of p′t, client C andserver S first calculateexC = {ex′1−r′1, ex′2−r′2, · · · , ex′K−r′K} andexS = {er′1, er′2, · · · , er′K}.Then, they use Yao’s Garbled Circuits to calculate thedenominator of p′t. The boolean circuits used here forYao’s Garbled Circuits can be simply implementedwith ADDGate, MULGate and MUXGate, and weignore the details here.The xC and xS are used toguarantee that every e(x′i−r′i mod m+1)+(r′i mod m+1)does not exceed em+1 and decide whether to drop it.The final calculation result, i.e., the denominator of p′t,will be obtained by C.At this point, since the numerator em is public and C hasthe denominator of pt, C is able to calculate p′t. Note that,the potential leakage resulting from p′t is out of scope of thispaper. Actually, it is a general problem of neural networks[27]. Since the numerator of p′t, i.e. em, is public and con-tains no information about p′t, the possible information thatcould infer from the denominator of p′t is equal to p′t.Security analysis. The possible privacy leakages are fromx1, x2, · · · , xK as they are all that used by the client to cal-culate the final result. In our design, xi, i ∈ [1, K] remainsshared throughout the calculation, which means the clientcan only obtain xi −ri. Since ri is a random number gener-ated and kept by the server, xi is protected from the client.5. Performance EvaluationWe implemented FALCON in C++.For fast FourierTransform (FFT), we used FFTW library [13].Foradditively homomorphic encryption, we used the Fan-Vercauteren (FV) scheme [5]. For secure two-party com-puting, we used Yao’s Garbled Circuits implemented by theABY framework [10]. Specifically, the number of slots n,the plaintext module p, and the ciphertext module q areneeded for the initialization of the FV scheme. We chosen = 2048, which means we can process up to 2048 ele-ments in parallel, and the ciphertext module q was set to1152921504382476289. The plaintext module p was set to1316638721, which has 30-bit length and is enough for allthe intermediate values.We tested FALCON on two computers, both of which areequipped with Intel i5-7500 CPU with 4 3.40 GHz cores and8GB memory, and have Ubuntu 16.04 installed. We let onebe the client C and the other play as the server S. We tookexperiments in the LAN setting similar to previous work[21, 18]. Each experiment was repeated for 100 times andwe report the mean in this paper.5.1. Benchmarks for LayersHere we introduce the performance of FALCON on in-dividual layers. Since GAZELLE is the best known relatedwork, we compare FALCON with it in all layers except thesoftmax layer, which is not implemented by GAZELLE. Forbenchmarking, all input data to each layers are randomlysampled from [0, p). Parameters of Conv and FC layers arechosen from the CIFAR-10 model stated in Section 5.2.We present the benchmarks