基于同态加密的隐私保护深度学习

慢慢的写代码

714人浏览 · 2025-09-24 13:46:10

慢慢的写代码 · 2025-09-24 13:46:10 发布

基于加法同态加密的隐私保护深度学习

摘要

我们提出了一种隐私保护深度学习系统，在该系统中，多个学习参与者基于所有参与方的联合数据集进行神经网络的深度学习，而无需向中央服务器暴露其本地数据。为此，我们重新审视了肖克里和什马蒂科夫（ACM CCS 2015）的前期工作，并指出在他们的方法中，本地数据信息可能泄露给诚实但好奇的服务器。随后，我们通过构建一个增强型系统解决了该问题，该系统具备以下特性：1）不会向服务器泄露任何信息；2）与在相同联合数据集上运行的普通深度学习系统相比，准确率保持不变。我们的系统架起了深度学习与密码学之间的桥梁：我们将应用于神经网络的异步随机梯度下降方法与加法同态加密相结合。我们证明，我们的加密方法为普通深度学习系统带来的额外开销在可接受范围内。

索引术语

隐私，深度学习，神经网络，加法同态加密，基于LWE的加密，Paillier加密。

一、引言

A. 背景

近年来，深度学习（又称深度机器学习）在学术界和工业界均取得了令人振奋的成果，这些系统的准确率正接近甚至超越人类水平。这得益于算法上的突破以及应用于神经网络以处理海量数据的物理并行硬件。

大规模数据收集虽然对深度学习至关重要，但也引发了隐私问题。个人而言，一张被收集的照片可能会永久保存在公司服务器上，超出了所有者的控制范围。从法律角度看，隐私和机密性方面的顾虑可能会阻止医院和研究中心共享其医疗数据集，使它们无法享受基于联合数据集的大规模深度学习带来的优势。

肖克里和什马蒂科夫 [28] 提出了一种用于隐私保护的深度学习系统，该系统允许多个参与者将本地数据集保留在本地，同时参与者可以获得基于联合数据集训练出的神经网络模型。为实现这一目标，[28]中的系统需要满足以下条件：每个学习参与者首先使用本地数据计算神经网络的梯度；然后必须将其中一部分（例如 1% ∼ 100%）梯度发送给参数云服务器。该服务器是诚实但好奇的。也就是说，假设它在操作上是诚实的，但会好奇地试图提取个体的数据。

为了保护隐私，肖克里和什马蒂科夫的系统存在准确率/隐私权衡（见表I）：不共享任何本地梯度可实现完全隐私，但准确率不理想；另一方面，共享所有本地梯度会侵犯隐私，但能获得较好的准确率。作为折中方案，在[28]中共享部分本地梯度是维持尽可能高准确率的主要解决方案。

B. 我们的贡献

我们证明，在肖克里和什马蒂科夫的系统中，即使存储在云服务器上的梯度只有一小部分也可能被利用。也就是说，可以从这些梯度中秘密提取本地数据。例如，在第三节中，我们展示了几个例子，说明一小部分梯度如何泄露有关数据的有用信息。

然后，我们提出了一种新颖的深度学习系统，利用加法同态加密来保护在诚实但好奇云服务器上的梯度。所有梯度均被加密并存储在云服务器上。加法同态特性支持对梯度进行计算。我们的系统在第四节中进行了描述，并在图5中进行了展示，具有以下安全性和准确率方面的特性：

Security. 我们的系统不会向诚实但好奇的参数（云）服务器泄露参与方的任何信息。

准确率。 我们的系统实现了与在所有参与方的联合数据集上训练的相应深度学习系统（即异步SGD（ASGD））相同的准确率。

简而言之，我们的系统兼具加密安全性和深度学习准确率的优势。参见第四节中的定理1和定理2。

1) 我们的权衡： 保护梯度免受云服务器攻击的代价是学习参与者与云服务器之间增加的通信。

我们在表II中显示，增加的因子并不太大：对于具体的混合美国国家标准与技术研究院（MNIST）数据集[5]和街景门牌号（SVHN）数据集[24]，该因子小于三。例如，在MNIST的情况下，如果每个学习参与者在每次上传或下载时需要向服务器传输0.56 MB的明文梯度，则使用基于误差学习（LWE）加密的我们的系统后，每次上传或下载对应的通信开销变为 2.47（表II的因子） × 0.437（原始MB） ≈ 1 MB。通过1 Gbps信道传输大约需要8毫秒。技术细节见第五节和第六节。

在计算方面，我们估计，我们的系统在MNIST数据集上训练和测试时，采用具有109386个梯度的多层感知机，大约需要2.25小时完成，获得约97%准确率，这与[2]中给出的同类神经网络的结果一致。此外，在MNIST上使用与[28]相同的具有105506个梯度的卷积神经网络，我们估计我们的系统大约需要7.3小时完成（准确率约为99%，由于定理2，与[28]的结果相同）。

2) 关于权衡的讨论： 我们表明，[28]中的准确率/隐私权衡可以转移到我们的系统中的效率/隐私权衡。[28]的准确率/隐私权衡可能使得隐私保护深度学习相比普通深度学习吸引力下降，因为在该领域中准确率是主要优势。我们的效率/隐私权衡保持了普通深度学习的准确率不变，如果采用更多的处理单元和更专用的编程代码，则可进一步改善。

3) 威胁模型： 在整个论文中，我们将服务器视为一个诚实但好奇的实体，而将学习参与者视为诚实实体。这种情况适用于将学习参与者视为金融机构或医院等组织的情景。

C. 技术概述

简洁的比较见表I。下面我们介绍其背后的技术细节。

1) 异步SGD（ASGD）[16],[27], 无隐私保护： 我们的系统和[28]的系统都依赖于这样一个事实：神经网络可以通过一种称为异步SGD [16],[27]的方法进行训练，该方法结合了数据并行和模型并行。具体来说，首先为神经网络随机初始化一个全局权重向量Wglobal。然后，在每次迭代中，在本地数据集上运行神经网络的副本（即数据并行），并将相应的本地梯度向量Glocal发送到云服务器。

对于每个Glocal，云服务器随后按如下方式更新全局参数：
$$ W_{global} := W_{global} - \alpha \cdot G_{local} $$
其中 $\alpha$ 是学习率。更新后的全局参数$W_{global}$会被广播到所有副本，各副本随后使用这些参数替换其旧的权重参数。更新和广播$W_{global}$的过程将持续进行，直到达到预定义代价函数（基于交叉熵或平方误差）的期望最小值为止。对于模型并行，式(1)中的更新通过向量$W_{global}$和$G_{local}$的分量并行计算完成。

2) Shokri-Shmatikov系统： [28, 第 5]节中描述的系统可称为梯度选择性异步SGD，原因如下。在[28, 第 5], 节中，(1)处的更新规则被修改如下：
$$ W_{global} := W_{global} - \alpha \cdot G_{selective \ local} $$
其中向量 $G_{selective \ local}$ 包含了部分选择的（例如 1% ∼ 100%）来自 $G_{local}$ 的梯度。使用 (2) 进行更新，使得每个参与者可以选择哪些梯度在全球范围内共享，以期降低其本地数据集中的敏感信息泄露给云服务器的风险。然而，如第三节所示，即使少量梯度也会向服务器泄露信息。

在[28, 第 7], 节中，Shokri‐Shmatikov 提出了一种利用差分隐私来对抗梯度间接泄露的附加技术。他们的策略是在(2)式中的$G_{selective \ local}$加入拉普拉斯噪声。由于噪声的存在，该方法损害了学习准确率，而学习准确率正是深度学习的主要优势。

3) 我们的系统： 我们系统可称为梯度加密异步SGD，原因如下。在第四节的我们的系统中，我们使用了以下更新公式
$$ E(W_{global}) := E(W_{global}) + E(-\alpha \cdot G_{local}) $$
其中$E$是支持对密文进行加法运算的同态加密。解密钥匙仅由参与方掌握，云服务器无法获知。因此，即使诚实但好奇的云服务器也无法得知每个$G_{local}$的信息，从而无法获取各参与方本地数据集的任何信息。然而，由于
$$ E(W_{global}) + E(-\alpha \cdot G_{local}) = E(W_{global} - \alpha \cdot G_{local}) $$
利用$E$的加法同态性质，每个参与方通过解密将获得正确更新的$W_{global}$。此外，当(1)中的原始更新通过向量$W_{global}$和$G_{local}$的分量进行并行化时，我们的系统相应地对每个分量应用同态加密。

此外，为了确保同态密文的完整性，每个客户端将使用安全通道（例如TLS/SSL，且彼此不同）与服务器通信同态密文。

4) 我们的系统的扩展： 我们将加密更新规则应用于 (3)的思想可扩展到其他基于SGD的机器学习方法。例如，我们的系统可以方便地与逻辑回归结合使用，适用于每个持有本地数据集的分布式学习参与方。在这种情况下，唯一的变化是每个参与方将运行基于SGD的逻辑回归，而不是深度学习中的神经网络。

D. 更多相关工作

Gilad‐Bachrach等[18]提出了一种名为 CryptoNets的系统，该系统允许对加密数据在已训练好的神经网络中进行数据前向传播。由于CryptoNets假设神经网络中的权重已经预先训练好，因此该系统旨在对单个数据项进行预测。

本文的目标与[28]不同于[18],，因为我们的系统和 Shokri‐Shmatikov的方法正是旨在通过多个数据源来训练权重，而CryptoNets[18]则不是如此。

本文将云服务器视为对手，而学习参与者被视为诚实实体。我们的场景和对手模型与Hitaj et al.[20]所研究的不诚实的学习参与方不同。

Mohassel和Zhang [23]研究了在两个假设未共谋的服务器上进行线性回归、逻辑回归和神经网络训练的隐私保护方法。他们的模型与我们的不同。

在仅使用加法同态加密的同一研究方向上，隐私保护的线性/逻辑回归系统已在[8]和[10]中提出。

使用秘密共享，Bonawitz et al. [14]提出了一种安全聚合方法，并将其应用于深度神经网络以聚合用户提供的模型更新。特别是，该工作[14]试图应对大量（例如，2^14= 16384在实验中或更实际情况下）移动设备的情况，从而导致掉线（协议完成失败）可能频繁发生。相比之下，我们希望拥有多个（例如，10个）诸如医院或银行等机构形式的数据提供方，各自拥有大量关于患者或客户的数据库，因此不考虑掉线情况。例如，我们的设定 closely反映了脚注2中提到的医疗场景中的情形。我们方案的另一个应用场景是，多家银行和/或信用卡公司希望基于所有数据的联合数据集进行训练（例如用于欺诈检测任务），但它们担心中央服务器对其明文敏感数据的好奇心。

由于所使用的工具不同（[14]中使用秘密共享，而我们使用加法同态加密），安全性的条件也随之改变，例如[14]中的诚实多数与我们所依赖的计算假设（LWE）不同。我们在正确性方面没有任何阈值要求，而[14]则有。这种多样性是有益的，以便为特定应用提供可选方案。

训练模型的信息泄露问题同样重要，但与本工作正交。解决此问题的常用工具是差分隐私（通常由于添加噪声而导致准确率下降），如[6]中用于深度学习的方法。

E. 对会议版本的改进

本文的初步版本发表于[26]。本完整版本对主要系统进行了推广，增加了诚实但好奇服务器上的多个处理单元，并允许学习参与者上传和下载加密梯度的部分内容。此外，修订了通信开销，并重新给出了计算开销。

二、预备知识

A. 关于加法同态加密

定义1（同态加密）：公钥加法同态加密（PHE）方案由以下（可能为概率性）多项式时间算法组成。

ParamGen(1λ) → pp： λ为安全参数，公共参数pp将在后续算法中隐式输入。
KeyGen(1 λ ) →(pk, sk)：pk是公钥，而sk是私钥。
Enc(pk, m) → c：概率加密算法生成密文c，即消息m的密文。
Dec(sk,c) → m：解密算法返回在 c 中加密的消息m。
加法运算(c,c’)：对于密文c和c’，输出为明文加法运算cadd的加密结果。
DecA(sk,cadd)：解密 cadd 以获得明文的加法运算结果。

密文不可区分性针对选择明文攻击[19]（下文简称 CPA安全）确保了密文中不会泄露任何信息。

B. 关于深度机器学习

1) 一些概念和符号： 深度机器学习可以被视为应用于神经网络的一系列技术。图1展示了一个具有5个输入、2个隐藏层和2个输出的神经网络。带有+1的节点表示偏置项。

示意图0

神经元节点通过权重变量连接。在神经网络的深度学习结构中，可以有多层，每层包含数千个神经元。

每个神经元节点（偏置节点除外）都关联有一个激活函数 f。深度学习中 f 的示例包括 $f(z) = \max{0,z}$（修正线性）、$f(z) = \frac{e^z-e^{-z}}{e^z+e^{-z}}$（双曲正切）和 $f(z)=(1+e^{-z})^{-1}$（sigmoid）。第 $l+1$ 层的输出，记为 $a^{(l+1)}$，计算方式为 $a^{(l+1)}=f(W^{(l)}a^{(l)}+b^{(l)})$，其中 $(W^{(l)}, b^{(l)})$ 是连接第 $l$ 层和第 $l+1$ 层的权重，$a^{(l)}$ 是第 $l$ 层的输出。

学习任务是，给定一个训练数据集，确定这些权重变量以最小化预定义代价函数，例如交叉熵或平方误差代价函数[3]。该损失函数可以在整个训练数据集的所有数据项上进行计算；或者在训练数据集中一个子集（称为小批量）的t个元素上进行计算。将后一种情况下的损失函数记为$J_{|batch|=t}$。在极端情况下，t= 1对应于最大随机性，$J_{|batch|=1}$是定义在单个数据项上的损失函数。

2) 随机梯度下降（SGD）： 设W为由所有权重变量组成的展平向量。即，我们将神经网络中的所有权重依次排列，形成向量$W$。记$W=(W_1,…, W_{ngd}) \in R^{ngd}$。设
$$ G=(\frac{\delta J_{|batch|=t}}{\delta W_1},…,\frac{\delta J_{|batch|=t}}{\delta W_{ngd}}) $$
是损失函数$J_{|batch|=t}$相对于变量$W_1,…, W_{ngd}$的梯度。在随机梯度下降中，变量的更新规则如下，其中学习率为 $\alpha \in R$：
$$ W := W - \alpha \cdot G $$
其中 $\alpha \cdot G$是逐元素乘法，即 $\alpha \cdot G=(\alpha G_1 ,…, \alpha G_{ngd}) \in R^{ngd}$。学习率 $\alpha$也可以如[3]和[17]所述进行自适应调整。

示意图1

3) 异步（又称 Downpour）随机梯度下降 [16],[27]： 根据(4)和(5)，只要能够计算出梯度 G ，就可以更新权重W。因此，用于计算G的数据可以分布化（即数据并行）。此外，通过考虑向量的不同分量，更新过程也可以并行化（即模型并行）。

具体而言，如图2所示，异步SGD使用了多个神经网络副本。在每次执行之前，每个副本都会从参数服务器下载最新的权重；然后每个副本在其对应的数据分片（即训练数据集的一个子集）上运行。为了利用服务器拥有多个处理单元PU1,…, PUnpu时的并行计算能力，异步SGD将权重向量W和梯度向量G分割为若干个部分，即$W=(W^{(1)},…, W^{(npu)})$和$G=(G^{(1)},…, G^{(npu)})$，使得(5)处的更新规则变为如下形式：
$$ W^{(i)} := W^{(i)} - \alpha \cdot G^{(i)} $$
在处理单元PUi上进行计算。由于处理单元PU1,…、PUnpu可以并行运行，异步SGD显著提高了深度网络训练的规模和速度，如[16]中的实验所示。

III. 梯度泄露信息

本节表明，一小部分梯度可能泄露本地数据的信息。

示例1（单个神经元）： 为了说明梯度如何泄露数据信息，我们首先使用图4中的神经网络，该网络仅包含一个神经元。在图中，实数$x_i(1 \leq i \leq d)$是输入数据，对应的真实标签为$y$；实数$W_i(1 \leq i \leq d)$是待学习的权重参数；$b$是偏置。函数$f$是激活函数（可以是第二节-B中描述的sigmoid、修正线性或双曲正切函数）。损失函数定义为预测值$h_{W,b}(x) = {def}f(\sum {i=1}^d W_ix_i+ b)$与真实值 y之间的距离。
$$ J(W, b, x, y) = {def}(h {W,b}(x) - y)^2 $$

示意图2

示意图3

因此梯度是
$$ \eta_k = {def} \frac{\delta J(W, b, x, y)}{\delta W_k} = 2(h {W,b}(x) - y)\frac{\delta h_{W,b}(x)}{\delta W_k} = 2(h_{W,b}(x) - y)\frac{\delta f(\sum_{i=1}^d W_ix_i+ b)}{\delta W_k} = 2(h_{W,b}(x) - y)f’(\sum_{i=1}^d W_ix_i+ b)\cdot x_k $$
and
$$ \eta = {def} \frac{\delta J(W, b, x, y)}{\delta b} = 2(h {W,b}(x)- y)\frac{\delta h_{W,b}(x)}{\delta b} = 2(h_{W,b}(x) - y)\frac{\delta f(\sum_{i=1}^d W_ix_i+ b)}{\delta b} = 2(h_{W,b}(x) - y)f’(\sum_{i=1}^d W_ix_i+ b)\cdot 1. $$

第 $k$ 个分量 $x_k$（$x=(x_1,…,x_d) \in R^d$）或真实标签 $y$ 可通过以下任一方式从梯度中推断出来：

(O1)注意到 $ \eta_k/\eta= x_k$。因此，如果 $ \eta_k $ 和 $ \eta $ 被共享给云服务器，则 $x_k$ 会完全泄露。例如，如果按照 [28] 中建议的方式，将随机选择的 1%的本地梯度共享给服务器，则 $ \eta_k $ 和 $ \eta $ 均被共享的概率为 $(1/100)\times(1/100) = 1/10^4$，这一概率不可忽略。

(O2)注意到梯度 $ \eta_k $ 对所有 $ 1 \leq i \leq d$ 都与输入$x_k$ 成正比。因此，当 $x=(x_1,…,x_d)$ 是一幅图像时，可以利用梯度生成一幅相关的“成比例”图像，然后通过猜测得到真实值 $y$。

示例2（通用神经网络，参见图3(b)）： 上述观察结果（O1）和（O2）同样适用于通用神经网络，包括使用交叉熵和平方误差损失函数的神经网络 [3]。特别是，遵循[3],
$$ \eta_{ik} = {def} \frac{\delta J(W, b, x, y)}{\delta W^{(1)} {ik}} = \xi_i \cdot x_k $$
其中$W^{(1)}_{ik}$是连接第1层输入$x_k$与第2层隐藏节点$i$的权重参数； $\xi_i$是一个实数。

在图3(b)中，我们在[1],上使用神经网络证明了公式 (9)中的梯度确实与原始数据成正比，因为图3(b)仅在数值条上与图3(a)不同。原始数据是一幅20x20图像，被重塑为一个向量$(x_1,…,x_{400}) \in R^{400}$。该向量是一个具有 25个节点的隐藏层的神经网络的输入；输出层包含10个节点。该神经网络中的梯度总数为
$$(400+ 1)\times 25+(25+ 1)\times 10= 10285.$$
在(9)处，我们有 $1 \leq k \leq 400$和 $1 \leq i \leq 25$。然后，我们使用在(9)处梯度的一小部分，即$(\eta_{1k})_{1\leq k\leq 400}$，将其重塑为一个20x20图像，以绘制图3(b)。显然，这部分梯度（即 400/10285 ≈ 3.89%）揭示了原始数据的真实标签0。

示例3（通用神经网络，带正则化，参见图3(c)）：
在带正则化的神经网络中，根据[3]我们有
$$ \eta_{ik} = {def} \frac{\delta J(W, b, x, y)}{\delta W^{(1)} {ik}} = \xi_i \cdot x_k+ \lambda W^{(1)} {ik} $$
$$ \eta_i = {def} \frac{\delta J(W, b, x, y)}{\delta b^{(1)}_i} = \xi_i $$
其中符号与上述示例2中的相同；$b^{(1)}_i$是第2层节点$i$的偏置；而 $\lambda \geq 0$是正则化项。

如观察（O1）所示， $\eta_{ik}$和 $\eta_i$均以不可忽略的概率被服务器所知。此外，在图3(c)中，我们使用了以下观察结果：
$$ \frac{\eta_{ik}}{\eta_i} = x_k+ \frac{\lambda W^{(1)} {ik}}{\xi_i} $$
这是对数据 $x_k$ 的近似。在图3(c)中，我们取 $\lambda= 0.1$，其他细节与上面的示例2相同。由于存在项 $\lambda W^{(1)} {ik}/\xi_i$，图中存在噪声，但仍可看出原始数据的真实值（数字0）。

示例4（添加拉普拉斯噪声，参见图3(d)）： 由于差分隐私和保密性是正交的，添加拉普拉斯向梯度添加噪声可能无法保护这些梯度免受好奇的服务器的保密性。如图3(d)所示，我们在(9)处向梯度 $\eta_{ik}$添加了均值0和标准差 $\sigma= 1/100$的拉普拉斯噪声，即
$$ \eta_{ik}= \xi_i \cdot x_k+ \text{Laplace}(0, 1/100) $$
因此，图像包含噪声，但真实值仍然可见。此外，当参数 $\sigma$ 越大时， $\eta_{ik}$ 可能被噪声主导，导致真实标签难以辨认，但这可能不利于权重变量的更新。

IV. 我们的系统：无准确率下降的隐私保护深度学习

我们的系统如图5所示，由一个通用的云服务器和N（例如 = 10 ∼ 100）个学习参与者组成。

A. 学习参与者

参与方共同为一种加法同态加密方案建立公钥 pk 和私钥 sk。私钥 sk 对云服务器保密，但所有学习参与者均知晓。每个学习参与者建立彼此不同的TLS/SSL安全通道，用于通信并保护同态密文的完整性。

然后，各参与方在本地持有其数据集，并运行基于深度学习的神经网络的副本。用于运行本地神经网络的初始（随机）权重$W_{global}$由参与者1初始化，参与者1还向服务器初始发送$E(W^{(1)} {global})$，…，$E(W^{(npu)} {global})$，其中$W^{(i)} {global}$也是一个构成$W {global}$第$i$部分的向量。梯度向量$G$在每次神经网络执行后被分割为$npu$部分，即$G=(G^{(1)},…, G^{(npu)})$，乘以学习率 $\alpha$，然后使用公钥$pk$进行加密。每个学习参与者生成的加密结果$E(-\alpha \cdot G^{(i)})(\forall 1 \leq i \leq npu)$被发送到服务器的处理单元$PU_i$。还值得注意的是，学习率 $\alpha$可以在每个学习参与者处本地自适应地调整，如[16]所述。

如图5所示，每个参与者 $1 \leq k \leq N$将执行以下步骤：

下载存储在服务器处理单元$PU_j$上所有$j \in I^{(down)} k \subset [1, npu]$的密文$E(W^{(j)} {global})$。通常$I^{(down)}_k = [1, npu]$，即学习参与者将下载全局权重的所有加密部分，但如果学习参与者的下载带宽受限，则可能存在$I^{(down)}_k \subset [1, npu]$的情况。
使用私钥$sk$解密上述密文，得到所有$j \in I^{(down)} k$的$W^{(j)} {global}$，并将这些值替换到$W_{global}=(W^{(1)} {global}, . . . , W^{(npu)} {global})$中对应的位置。
从其本地数据集中获取一个小批量数据。
利用步骤2和步骤3中的$W_{global}$值和数据项，计算关于变量$W=$的梯度$G=(G^{(1)}, . . . , G^{(npu)})$。
加密并回传密文$E(-\alpha \cdot G^{(i)}) \forall i \in I^{(up)}_k \subset [1, npu]$至服务器对应的处理单元$PU_i$。上传的子集$I^{(up)}_k \subset [1, npu]$取决于参与者$k$的选择。对于完整上传，$I^{(up)}_k=[1, npu]$，从而将所有加密梯度上传至服务器。

$W_{global}$的加密部分的下载和上传在两个方面可以是异步的：参与方相互独立；处理单元也相互独立。

B. 云服务器

云服务器是递归更新加密的权重参数的常见场所。具体而言，服务器上的每个处理单元$PU_i$在接收到任何加密 $E(-\alpha \cdot G^{(i)})$后，进行计算
$$ E(W^{(i)} {global}) + E(-\alpha \cdot G^{(i)}) \quad (\text{which is } = E(W^{(i)} {global} - \alpha \cdot G^{(i)})) $$
其中等式由加密的加法同态性质保证。因此，处理单元 $PU_i$处的 $W^{(i)} {global}$被更新为 $W’^{(i)} {global} - \alpha \cdot G^{(i)}$，或记作
$$ W’^{(i)} {global} := W^{(i)} {global} - \alpha \cdot G^{(i)}. $$

定理1（针对云服务器的安全性）： 只要底层的同态加密方案是CPA安全的，那么我们图5中的系统不会向诚实但好奇的云服务器泄露任何关于数据集的信息。

证明： 参与方仅向云服务器发送加密的梯度。因此，如果加密方案是CPA安全的，则参与方数据的任何信息都不会泄露。

定理2 (与异步SGD的准确性等价)： 我们的系统在图5中，当所有密文都被解密且$I^{(up)}_k=I^{(down)}_k=[1,np u] \forall 1 \leq k \leq N$（意味着所有梯度都被上传和下载）时，其功能等同于第二节-B中描述的异步SGD。因此，我们的系统可以达到与异步SGD相同的准确率。

证明： 解密后，权重参数的更新规则变为$W^{(i)} {global} := W^{(i)} {global}-\alpha\cdot G^{(i)}$对于任意 $1 \leq i \leq npu$，其中$G^{(i)}$是由参与者$k$持有的数据样本（以及下载的$W_{global}$）计算出的梯度向量。由于更新规则与(6)相同，并且在移除加密后，我们系统中的每个学习参与者都充当一个副本（如异步SGD中），因此该定理成立。

备注1： 由于学习参与者通过不同的TLS/SSL通道连接到服务器，在假设服务器和任何学习参与者不共谋的情况下，学习参与者只能获取神经网络权重而无法获取梯度。这有助于控制学习参与者之间的信息共享，因为从模型中推导出有关数据的任何信息都会成为一个模型反演问题。

基于加法同态加密的隐私保护深度学习

五、我们系统的实例化

在本节中，我们使用加法同态加密方案来实例化第四节中的我们的系统。我们采用以下两种方案来展示我们系统的两个实例：基于LWE的加密（现代的，可能具有后量子安全性）和Paillier加密（经典的，密钥尺寸较小，不具备后量子安全性）。

A. 使用基于LWE的加密

符号 $ \leftarrow_g $ 表示“从离散高斯分布中随机采样”，因此 $ x \leftarrow_g Z(0,s) $ 表示 $ x $ 出现的概率与 $ \exp(-\pi x^2/s^2) $ 成正比。

1) 基于LWE的加密： 我们使用一种加法同态变体 [9],[11]，该变体来自[21]中的公钥加密方案。该方案的CPA安全在附录A中进行了回顾。

ParamGen($1^\lambda$)：固定 $ q = q(\lambda) \in \mathbb{Z}^+ $ 和 $ l \in \mathbb{Z}^+ $。固定 $ p \in \mathbb{Z}^+ $ 使得 $ \gcd(p, q) = 1 $。返回 $ pp = (q, l, p) $。
KeyGen($1^\lambda$, $pp$)：选取 $ s = s(\lambda, pp) \in \mathbb{R}^+ $ 和 $ n_{lwe} \in \mathbb{Z}^+ $。选取 $ R, S \leftarrow_g Z^{n_{lwe} \times l}(0,s) $，$ A \xleftarrow{\$} Z_q^{n_{lwe} \times n_{lwe}} $。计算 $ P = pR - AS \in Z_q^{n_{lwe} \times l} $。返回公钥 $ pk = (A, P, n_{lwe}, s) $，以及私钥 $ sk = S $。
Enc($pk$, $m \in Z_p^{1 \times l}$)：选取 $ e_1, e_2 \leftarrow_g Z_q^{1 \times n_{lwe}}(0,s) $，$ e_3 \leftarrow_g Z_q^{1 \times l}(0,s) $。计算 $ c_1 = e_1A + pe_2 \in Z_q^{1 \times n_{lwe}} $，$ c_2 = e_1P + pe_3 + m \in Z_q^{1 \times l} $。返回 $ c = (c_1, c_2) $。
Dec($S$, $c = (c_1, c_2)$)：计算 $ m = c_1S + c_2 \in Z_q^{1 \times l} $。返回 $ m = m \mod p $。
加法运算($c, c’$)：对于加法运算，计算并返回 $ c_{add} = c + c’ \in Z_q^{1 \times (n_{lwe} + l)} $。

2) 数据编码与加密： 一个实数 $ a \in \mathbb{R} $ 可以用 $ prec $ 位的精度表示为一个整数 $ a \cdot 2^{prec} \in \mathbb{Z} $。让我们实现图5中所示的加密 $ E(\cdot) $。由于 $ W^{(i)} {global} $ 和 $ \alpha \cdot G^{(i)} $ 均位于空间 $ \mathbb{R}^{L_i} $ 中，其中 $ L_i $ 为分段长度，使得 $ \sum {i=1}^{npu} L_i = ngd $，因此只需描述一个实向量 $ r = (r^{(1)}, …, r^{(L_i)}) \in \mathbb{R}^{L_i} $ 的加密。对于 $ l = L_i $，加密方式如下：
$$
E(r) = \text{lweEnc} {pk}\left( r^{(1)} \cdot 2^{prec} \cdots r^{(L_i)} \cdot 2^{prec} \right). \tag{10}
$$
对于向量 $ r, t \in \mathbb{R}^{L_i} $，的解密
$$
E(r) + E(-t) \in Z_q^{1 \times (n {lwe} + L_i)} \tag{11}
$$
将对所有 $ 1 \leq j \leq L_i $ 产生结果，
$$
r^{(j)} \cdot 2^{prec} - t^{(j)} \cdot 2^{prec} \in \mathbb{Z} p \subset (-p/2, p/2] \tag{12}
$$
因此
$$
u^{(j)} = r^{(j)} \cdot 2^{prec} - t^{(j)} \cdot 2^{prec} \in \mathbb{Z} \tag{13}
$$
如果 $ p/2 $ 足够大（见下文）。减法 $ r^{(j)} - t^{(j)} \in \mathbb{R} $ 通过 $ u^{(j)} / 2^{prec} \in \mathbb{R} $ 计算，因此在解密后最终得到期望的 $ r - t \in \mathbb{R}^{L_i} $。要从 (12) 得到 (13)，只需满足 $ p/2 > 2 \cdot 2^{prec} $，因为通过归一化，我们可以假设 $ -1 < r^{(j)}, t^{(j)} < 1 $。一般来说，为了处理 $ n {gradupd} $ 个加性项而不发生溢出，必须满足 $ p/2 > n_{gradupd} \cdot 2^{prec} $，或者等价地，
$$
p > n_{gradupd} \cdot 2^{prec+1}. \tag{14}
$$
引理1（选择参数）： 当 $ n_{lwe} \geq 3000 $，$ s = 8 $ 时，可以设置
$$
\log_2 q \approx \log_2 p + \log_2 n_{gradupd} + \log_2(167.9\sqrt{n_{lwe}} + 33.9) + 1
$$
其中 $ p $ 满足 (14)，$ n_{gradupd} $ 表示图5中云服务器每个处理单元的梯度更新次数。例如，当 $ n_{lwe} = 3000 $，$ p = 2^{48} + 1 $，$ n_{gradupd} = 2^{15} $ 时，可以设置 $ q = 2^{77} $。

值得注意的是，引理1中的参数非常保守，这是因为在证明中考虑了不太可能出现的大噪声。因此，$ n_{gradupd} $ 可以比所述的更大。实际上，我们通过实验验证了 $ q = 2^{77} $、$ n_{lwe} = 3000 $、$ p = 2^{48} + 1 $ 和 $ s = 8 $，并确认 $ n_{gradupd} $ 可以是引理1中所述值的两倍（即 $ n_{gradupd} = 2 \cdot 2^{15} $），而不会出现任何解密错误。

定理3（基于LWE的通信开销增长因子）： 我们的系统中服务器与参与方之间的通信是
$$
\frac{n_{pu}n_{lwe} \log_2 q}{ngd \cdot prec} + \frac{\log_2 q}{prec}
$$
异步SGD通信时间，其中 $ (n_{lwe}, p, q) $ 是加密方案的参数，$ ngd $ 是以 $ prec $ 位表示的梯度变量数量。

证明： 在异步SGD（第二节-B）中，每个副本在每次迭代时向参数服务器发送 $ ngd = \sum_{i=1}^{npu} L_i $ 个梯度（每个梯度为 $ prec $ 位），因此每次迭代的通信开销（单位为比特）为
$$
\text{PlainBits} = ngd \cdot prec.
$$
在我们的系统中，我们计算每个学习参与者在每次迭代时发送给云端参数服务器的密文长度。根据(10)，发送给处理单元 $ PU_i $ 的密文位于 $ Z_q^{1 \times (n_{lwe} + L_i)} $ 中，因此其位长度为 $ (n_{lwe} + L_i)\log_2 q $。每次交互中，相应学习参与者发送给参数服务器的所有密文的位长度至多为
$$
\text{EncryptedBits} = \sum_{i=1}^{npu} (n_{lwe} + L_i) \log_2 q = n_{pu}n_{lwe} \log_2 q + ngd \log_2 q.
$$
因此，增加的因子是
$$
\frac{\text{EncryptedBits}}{\text{PlainBits}} = \frac{n_{pu}n_{lwe} \log_2 q}{ngd \cdot prec} + \frac{\log_2 q}{prec}
$$
证明结束。

B. 使用Paillier加密

1) Paillier加密： 在公钥 $ pk = n $（一个较大的正整数）下，对整数 $ m \in {0, …, n - 1} $ 的加密为 $ \text{PaiEnc} {pk}(m) = r^n (1+n)^m \mod n^2 $，其中 $ r $ 从 $ {0, …, n - 1} $ 中随机选取。该加密具有加法同态性，因为密文乘积 $ \text{PaiEnc} {pk}(m_1)\text{PaiEnc}_{pk}(m_2) \mod n^2 $ 会成为 $ m_1 + m_2 \mod n $ 的一个加密结果。关于解密和CPA安全，请参见论文[25]。

2) 加密中的数据打包： 由于明文空间具有 $ \log_2 n \geq 2048 $ 位，我们可以将多个非负整数 $ I_1, …, I_t $（每个为 $ prec $ 位）打包到每个Paillier明文中，如下所示。
$$
\text{PaiEnc} {pk}\left( [I_10 {pad}] \cdots [I_t0_{pad}] \right)
$$
其中 $ 0_{pad} $ 是用于防止密文加法运算溢出的填充位的零填充。通常，$ pad \approx \log_2 n_{gradupd} $，因为我们需要进行 $ n_{gradupd} $ 次密文加法运算。此外，由于明文位数必须小于 $ \log_2 n $，因此必须满足 $ t(prec + pad) \leq \log_2 n $。因此，
$$
t = \left\lfloor \frac{\log_2 n}{prec + pad} \right\rfloor
$$
这是将 $ prec $ 位整数打包到一个Paillier明文中的上界。为了处理负整数和正整数，我们可以使用双射 $ z \in [0, 2^{prec} - 1] \mapsto z - \left\lfloor z/2^{prec} \right\rfloor \cdot 2^{prec} $。

由于实数 $ 0 \leq r < 1 $ 可表示为形式为 $ \lfloor r \cdot 2^{prec} \rfloor $ 的整数，上述打包方法可用于在范围 $[0, 1]$ 内以精度 $ prec $ 加密约 $ \lfloor \log_2 n/(prec + pad) \rfloor $ 个实数，并可容忍约 $ 2^{pad} $ 次密文加法运算。为了实现图5中的加密 $ E(\cdot) $，只需描述实向量 $ r = (r^{(1)}, …, r^{(L_i)}) \in \mathbb{R}^{L_i} $ 的加密，因为 $ W^{(i)} {global} $ 和 $ \alpha \cdot G^{(i)} \in \mathbb{R}^{L_i} $ 均满足 $ \sum {i=1}^{npu} L_i = ngd $。加密 $ E(r) $ 大约由 $ \lceil L_i/t \rceil $ 个Paillier密文组成：
$$
\text{PaiEnc} {pk}\left( r^{(1)} \cdot 2^{prec}0 {pad} \cdots r^{(t)} \cdot 2^{prec}0_{pad} \right), …, \text{PaiEnc} {pk}\left( r^{(L_i-t+1)} \cdot 2^{prec}0 {pad} \cdots r^{(L_i)} \cdot 2^{prec}0_{pad} \right).
$$

定理4（通信开销增长因子，基于Paillier）： 我们的系统中服务器与参与者之间的通信是
$$
2\left(1 + \frac{pad}{prec}\right)
$$
通信次数是相应异步随机梯度下降的倍数，其中 $ pad $ 是为容忍 $ 2^{pad} $ 加法运算（等于服务器上的梯度更新次数）而添加的0填充数量，$ prec $ 是数值的比特精度。

证明： 在图5所示的我们的系统中，每个参与者最多需要向服务器加密并发送 $ \sum_{i=1}^{npu} L_i = ngd $ 个梯度，其中 $ L_i $ 是 $ G^{(i)} $ 的长度。因此，采用上述Paillier加密的打包方法后，每个参与者发送的Paillier密文数量约为
$$
\sum_{i=1}^{npu} \frac{L_i}{t} \approx \frac{ngd}{t} \approx \frac{ngd(prec + pad)}{\log_2 n}.
$$
由于每个Paillier密文为 $ 2\log_2 n $ 位，每次通信的比特数约为
$$
\text{EncryptedBits} \approx 2\log_2 n \cdot \frac{ngd}{t} \approx 2ngd(prec + pad).
$$
另一方面，请注意异步SGD中的每个副本需要向服务器发送 $ ngd $ 个 $ prec $ 位的梯度，比特通信开销为 $ \text{PlainBits} = ngd \cdot prec $。因此，增加的因子是
$$
\frac{\text{EncryptedBits}}{\text{PlainBits}} = \frac{2ngd(prec + pad)}{ngd \cdot prec} = 2\left(1 + \frac{pad}{prec}\right)
$$
如所声称的。

对于Paillier加密的情况，我们可以选择填充 $ pad = 15 $，使得通过定理4，通信开销增长因子变为
$$
\frac{\text{EncryptedBits}}{\text{PlainBits}} = 2\left(1 + \frac{pad}{prec}\right) = 2\left(1 + \frac{15}{32}\right) \approx 2.93
$$
与 $ ngd $ 无关。当 $ ngd $ 较大时，如后文评估所示，此通信开销增长因子略大于基于LWE的方案。

VI. 基于LWE加密的具体评估

我们根据引理1选择 $ n_{lwe} = 3000 $、$ s = 8 $、$ p = 2^{48} + 1 $、$ n_{gradupd} = 2^{15} $ 和 $ q = 2^{77} $。这些参数对于 $ (n_{lwe}, s, q) $ 保守地确保LWE假设根据近期攻击至少具有128位安全性[7],[15],[21],[22]。我们将根据梯度数量选择 $ n_{pu} \in {1, 10} $。

A. 通信中增加的因子

让我们考虑多个梯度参数 $ ngd $：

$ ngd = 109386 $：此梯度参数数量用于MNIST数据集[5]。具体而言，考虑一个形式为784（输入）– 128（隐层）– 64（隐层）– 10（输出）的多层感知机。该网络的梯度数量为 $ (784+1)128+(128+1)64+(64+1)10 = 109386 $。我们将考虑实数以32位表示的情况，因此 $ prec = 32 $。定理3告诉我们，我们的系统与相关异步SGD之间的通信开销增长因子为
$$
\frac{n_{pu}n_{lwe} \log_2 q}{ngd \cdot prec} + \frac{\log_2 q}{prec} = \frac{1 \cdot 3000 \cdot 77}{109386 \cdot 32} + \frac{77}{32} \approx 2.47.
$$
$ ngd = 402250 $：这在使用 SVHN 数据集的 [28] 中被采用。通信开销增长因子变为
$$
\frac{n_{pu}n_{lwe} \log_2 q}{ngd \cdot prec} + \frac{\log_2 q}{prec} = \frac{1 \cdot 3000 \cdot 77}{402250 \cdot 32} + \frac{77}{32} \approx 2.42.
$$
$ ngd = 42 \cdot 10^6 $：该梯度参数数量用于语音数据的[16]中。由于梯度数量较大，需考虑 $ n_{pu} = 10 $。通信开销增长因子变为
$$
\frac{n_{pu}n_{lwe} \log_2 q}{ngd \cdot prec} + \frac{\log_2 q}{prec} = \frac{10 \cdot 3000 \cdot 77}{42 \cdot 10^6 \cdot 32} + \frac{77}{32} \approx 2.4.
$$

B. 估算计算成本

为了估算我们系统的运行时间，我们使用以下公式
$$
T^{(i)} {\text{ours, one run}} = T^{(i)} {\text{original, one run}} + T^{(i)} {\text{enc}} + T^{(i)} {\text{dec}} + T^{(i)} {\text{upload}} + T^{(i)} {\text{download}} + T_{\text{add}}, \tag{15}
$$
$$
T_{\text{our system}} = \sum_{i=1}^{N} n^{(i)} {\text{upload/download}} \times T^{(i)} {\text{ours, one run}} \tag{16}
$$
其中，在(15)式中，$ T^{(i)} {\text{ours, one run}} $ 表示参与者 $ i $ 执行以下操作时的运行时间：等待服务器处密文的加法运算（$ T {\text{add}} $）；从服务器下载相加后的密文（$ T^{(i)} {\text{download}} $）；解密下载的密文（$ T^{(i)} {\text{dec}} $）；使用下载的权重进行训练（$ T^{(i)} {\text{original, one run}} $）；加密得到的梯度（$ T^{(i)} {\text{enc}} $），并将该密文发送回服务器（$ T^{(i)} {\text{upload}} $）。我们的系统总运行时间 $ T {\text{our system}} $ 等于所有 $ N $ 个参与方的运行时间之和乘以重复次数 $ n_{\text{repeat}} $，如(16)式所示。

1) 环境： 我们的同态加密代码使用C++编写，基准测试在至强CPU E5-2660 v3@ 2.60GHz服务器上进行。为了估算每个学习参与者与服务器之间的通信速度，我们假设使用1 Gbps网络。为了测量多层感知机的运行时间，我们使用TensorFlow 1.1.0 库[4]在Cuda-8.0和GPU Tesla K40m上进行。

2) 加密、解密和加法运算的时间： 表III给出了加密、解密和加法运算的时间，该时间取决于梯度数量 $ ngd $，使用了 $ n_{lwe} = 3000 $、$ s = 8 $、$ p = 2^{48} + 1 $ 以及 $ q = 2^{77} $。图6描绘了分别使用1个线程和20个线程进行计算时的加密和解密时间。

示意图4

3) 多层感知机（MLP）： 考虑一个结构为784（输入）– 128（隐层）– 64（隐层）– 10（输出）的多层感知机。该网络的梯度数量为 $ (784+1)128+(128+1)64+(64+1)10 = 109386 $。在32位精度下，这些梯度明文大小约为 $ 109386 \times 32/(8 \times 10^6) \approx 0.437 \text{MB} $。根据第六章A节计算，这些梯度的密文大小为 $ 0.437 \times 2.47 \approx 1.0 \text{MB} $，可通过1 Gbps通信信道在约0.008秒（= 8 ms）内传输。该多层感知机在处理一批大小为50（MNIST图像）的数据时的原始运行时间为 $ T^{(i)} {\text{MLP, one run}} \approx 4.6 $（ms）。因此，
$$
T^{(i)} {\text{ours, one run}} = T^{(i)} {\text{MLP, one run}} + T^{(i)} {\text{enc}} + T^{(i)} {\text{dec}} + T^{(i)} {\text{upload}} + T^{(i)} {\text{download}} + T {\text{add}} \approx 4.6 + 188.9 + 196.0 + 8 + 8 + 19.5/10^3 \approx 405.5 \text{(ms)}. \tag{17}
$$
假设所有训练参与者与服务器之间总共进行了 $ 2 \times 10^4 $ 次上传和下载，即 $ \sum_{i=1}^{N} n^{(i)} {\text{upload/download}} = 2 \times 10^4 $。为简便起见，假设 $ T^{(i)} {\text{ours, one run}} $ 对所有 $ 1 \leq i \leq N $ 均相同。在这种情况下，我们的系统的运行时间可以估计为
$$
T_{\text{our system}} = T^{(i)}_{\text{ours, one run}} \times 2 \times 10^4 = 405.5 \times 2 \times 10^4 \text{(ms)} \approx 2.25 \text{(hours)}.
$$
如定理2所示，我们系统的准确率可以与异步SGD相同。因此，只需估算在包含随机打乱的 $ 6 \times 10^4 $ 图像用于训练和 $ 10^4 $ 图像用于测试的MNIST上异步SGD的准确率即可。如前所述，批量大小为50。初始权重从均值0、标准差0.1的正态分布中随机选取（通过TensorFlow的 random_normal函数）。激活函数为TensorFlow中的 relu函数。训练使用Adam优化器（TensorFlow中的 AdamOptimizer），其输入学习率 $ 10^{-4} $，无dropout。经过 $ 2 \times 10^4 $ 次迭代并耗时2分钟，我们的TensorFlow代码在测试集上达到了约97%准确率。

4) 卷积神经网络（CNN）： 得益于定理2，我们在第四节中的系统与异步SGD具有相同的准确率，因此我们可以重新使用[28]中的准确率结果。特别是，让我们考虑用于MNIST的卷积神经网络[28,图 6]，其梯度数量为 $ ngd = 105506 $。当向服务器发送10%或以上（100%）的梯度时，[28,表4、图 8]中报告的相应准确率约为99%。在效率讨论方面，设训练周期数为35；小批量大小为32；学习参与者数量为 $ N = 30 $（均在[28]中使用）。注意，此情况下的梯度数量 $ ngd $ 几乎与多层感知机情况相同，因此加密和解密速度以及通信开销将相同（或略低）。因此，我们可以安全地重新使用(17)，从而
$$
T^{(i)} {\text{ours, one run}} = T^{(i)} {\text{CNN, one run}} + T^{(i)} {\text{enc}} + T^{(i)} {\text{dec}} + T^{(i)} {\text{upload}} + T^{(i)} {\text{download}} + T_{\text{add}} \approx T^{(i)} {\text{CNN, one run}} + 188.9 + 196.0 + 8 + 8 + 19.5/10^3 \approx T^{(i)} {\text{CNN, one run}} + 401 \text{(ms)}
$$
由于训练集中的图像数量为60000，由 $ N = 30 $ 个学习参与者共享，每个参与者将持有 $ 60000/30 = 2000 $ 张图像。小批量数量为32，因此每个参与者在每轮次中大约需要进行 $ 2000/32 $ 次上传和下载。因此，在35个轮次中，30个参与者将总共进行 $ (2000/32) \times 30 \times 35 $ 次上传和下载。我们系统的预计运行时间为
$$
T_{\text{our system}} = T^{(i)} {\text{ours, one run}} \times (2000/32) \times 30 \times 35 \approx (T^{(i)} {\text{CNN, one run}} + 401) \times 65625 \text{(ms)} \approx (T^{(i)} {\text{CNN, one run}} + 401) \times \frac{65625}{36 \times 10^5} \text{(hours)} \approx 0.018 T^{(i)} {\text{CNN, one run}} + 7.3 \text{(hours)}
$$
这大约是MLP情况下的3.3倍。