GALA：隐私保护神经 络中线性代数的贪婪计算

引用

[1] Zhang Q , Xin C , Wu H . GALA: Greedy ComputAtion for Linear Algebra in Privacy-Preserved Neural Networks[C]// Network and Distributed System Security Symposium. 2021.

摘要

机器学习即服务(MLaaS)使终端设备上的各种智能应用成为可能。然而，隐私仍然是一个基本挑战。利用基于同态加密(HE)的线性计算和基于乱码电路(GC)的非线性计算的方案已经证明了实现隐私保护 MLaaS 的卓越性能。尽管如此，计算速度仍然存在显着差距。调查发现，基于 HE 的线性计算在最先进的深度神经 络的总计算时间中占主导地位，其中最耗时的部分是一系列置换(Perm)操作，这些操作对于隐私保护 MLaaS 中的点积和卷积必不可少。这项工作侧重于对基于 HE 的线性计算进行深度优化，以最大限度地减少 Perm 操作，从而大大减少整体计算时间。为此，我们提出 GALA，将基于 HE 的线性计算视为一系列同态 Add、Mult 和 Perm 操作，并在每个线性计算步骤中选择成本最低的操作以降低整体成本。GALA 做出了以下贡献：(1)引入了行权重矩阵编码，并结合了基于 GC 的非线性计算所需的份额生成，以减少点积的 Perm 操作；(2)设计了 firstAdd-second-Perm 方法（称为 kernelgrouping）来减少卷积的 Perm 操作。凭借对基于 HE 的线性计算的深度优化，GALA 可以是集成到这些系统中的即插即用模块，以进一步提高它们的效率。实验表明，它在不同数据维度下使点积计算加速了 700 倍，卷积计算加速了 14 倍。

1. 介绍

深度学习(DL)正变得普遍和普遍，特别是，卷积神经 络(CNN)在计算机视觉方面表现出卓越的性能。云提供商开始提供机器学习即服务(MLaaS)，其中专有的 DL 模型在云上进行训练和托管。客户可以通过简单地向云发送查询（推理）并通过 Web 门户接收结果来利用该服务。

尽管端到端的通信可以很容易地得到保护，但隐私仍然是一个基本挑战。一方面，客户必须将他们的数据提交到云端进行推理，但他们希望数据隐私得到很好的保护，防止好奇的云提供商或有权访问云的攻击者挖掘有价值的信息。另一方面，云提供商不希望用户能够提取他们已经用大量资源和努力训练过的专有模型。此外，经过训练的模型包含有关训练数据集的私人信息，可能会被恶意用户利用。为此，迫切需要制定有效且高效的方案，以确保在 MLaaS 中，云服务器无法访问用户的数据，用户无法学习服务器的模型。

现有基于 HE、基于 GC、利用秘密共享(SS)的几种加密技术。其中，基于 HE 的线性计算和基于 GC 的非线性计算的方案（以下称为 HE-GC 神经 络框架）表现出优越的性能，但在计算速度上仍然存在显着差距。线性计算在深度神经 络中占据了大部分计算时间，而在基于 HE 的计算中包括三个基本操作：同态加法（Add）、乘法（Mult）和置换（Perm）。研究表明，基于 HE 的计算中最耗时的部分是一系列 Perm 操作，这些操作对于实现点积和卷积至关重要，如表 1 所示。

我们将基于 HE 的线性计算视为一系列同态 Add、Mult 和 Perm 操作。两个输入是来自客户端的加密向量（或通道）和来自服务器的明文权重矩阵（或内核）。输出是加密的点积（或卷积）。每个步骤的目标是在 Add、Mult 和 Perm 的优先级降序中选择最有效的操作。为此，我们设计了一种具有组合共享生成的行权重矩阵编码以减少点积中的 Perm 操作并且提出了一种 first-Add-second-Perm 方法来减少卷积中的 Perm 操作。

2. 准备工作

本节介绍总体系统架构和威胁模型以及 GALA 中使用的加密工具。

A.系统模型

考虑图 1 所示的 MLaaS 系统，客户端拥有私有数据，服务器位于云端，并具有训练有素的深度学习模型，可根据接收到的客户端数据提供推理服务。

B.威胁模型

采用半诚实模型，客户端和服务器将遵循协议，但想要学习模型参数并尝试学习客户的数据。请注意，许多应用程序都建立在众所周知的深度 络结构上，因此，专注于模型参数的保护。在实现的结构是专有的并且必须受到保护的情况下，服务器可以引入冗余层和内核来隐藏真实结构，但需要付出一定的计算代价。因此，首要目标是让服务器忘记来自客户端的私有数据，并防止客户端学习服务器的模型参数。GAZELLE 根据理想/真实安全的密码标准证明了 HE-GC 神经 络框架的安全性，本工作采用相同的安全框架。GALA 侧重于在推理过程中保护输入数据和模型参数，神经 络模型的输出返回给客户端，客户端解密结果并得到明文预测。

C.加密工具

在 PHE 中，加密算法将明文加密,将来自 Zn 的消息向量 x 转换为具有 n 个插槽的密文[x]。我们将[x]C 和[x]S 分别表示为客户端和服务器加密的密文。解密算法输出来自密文[x]的明文向量 x。可以对密文进行计算。一般来说，评估算法输入几个密文[x1],[x2],…,输出密文[x’]=f([x1],[x2],…)。函数 f 由同态加法（Add）、乘法(Mult)和排列(Perm)构成。具体来说，Add([x],[y])输出一个密文[x+y]，它加密 x 和 y 的元素和。Mult([x],s)输出一个密文[x⊙s]，它对 x 和明文 s 的元素乘法进行加密。GALA 旨在要求标量乘法，使用 ScMult 来表示标量乘法。Perm([x])将[x]中的 n 个元素排列成另一个密文[xπ]，其中 xπ=(x(π0),x(π1),…)，πi 是{0,1,,,n-1}的排列。此外，在相同密文上一系列 Perm 操作的计算成本可以通过先对密文进行一次 Perm 分解（DecPerm）然后进行相应的一系列提升 Perm（HstPerm）操作来优化。由于只涉及一个 DecPerm，它可以分摊总置换时间。Add 和 ScMult 的运行时间明显低于 Perm。根据我们的实验，Perm 操作比 Add 操作慢 56 倍，比 ScMult 操作慢 34 倍。这一观察激发了所提出的线性优化，旨在最小化 Perm 操作的数量，从而大大减少整体计算时间。

同时，PHE 在密文中引入了噪声，理论上隐藏了原始消息。假设[x]和[y]的噪声分别为η0 和 η1，那么 Add 操作大约是η0+η1。ScMult 运算是ηmultη0，其中ηmult是 SIMD 标量乘法运算的乘法噪声增长。Perm 操作后的噪声为η0+ηrot，其中ηrot 是置换操作的加性噪声增长。粗略地说，我们有ηrot>ηmult>>η0>>1。如果噪声超过某个级别，则解密将失败。因此对密文进行良好的噪声管理也很重要。

(2)秘密共享 在秘密共享协议中，两方共享一个值，因此将两个秘密组合在一起产生真正的价值。为了添加共享一个秘密m，随机数r被选中，并创建两个共享为< m >0=r和< m >1=m-r。在这里，m可以是普通文本或密码。想要共享秘密的一方将其中一份分享发送给另一方。要重建秘密，一方只需要添加m=< m >0+< m >1。

虽然秘密共享（SS）的总体理念是直截了当的，但往往需要创造性的设计才能使其在实践中得到有效应用。具体来说，在 HE-GC 神经 络框架中，点积或卷积的线性结果在服务器端进行加密，需要与客户共享，以便实现后续基于 GC 的非线性计算。假设m是服务器线性计算的结果密码，然后 GAZELLE 生成共享< m >0=r并发送< m >1=m-r给客户端。这两种共享充当基于 GC 的非线性计算的输入。在这里，m的计算涉及一系列 Perm 操作，这很费时。我们开发的点积共享 RAS（RotateandSum）计算不是直接生成共享< m >0=r，而是允许服务器为不完整的m、m’生成间接共享r’，而真正的r很容易从r’中提取，真正的< m >1=m-r很容易从m’-r’中提取。

(3)遗忘转移(OT) 在 1-out-of-k 遗忘转移中，发送方的输入是 k 个字符串，m0，m1,…mk-1∈{0,1}l，接收方的输入是一个值 i 属于{0,1,…,k-1}。在 OT 执行结束时，接收方从函数中获得 mi 并且发送方没有收到任何输出。在这里，OT 协议保证接收者对 mj,j≠i 一无所知，而且发送者对 i 一无所知。实际中有一种特殊的扩展 OT，1-out-of-2 的 COT 可以用于线性计算，其中发送方的每个 OT 的两个输入不是独立的，是一个随机值 S0 和 S1=f(S0)。发送方选择相关函数 f，接收器根据 b 获得 S0 或者 S1 作为输出。

3.系统描述

A.行编码共享RaS矩阵向量乘法

首先关注矩阵向量乘法（点积），它将服务器端的明文矩阵与来自客户端的加密向量相乘。首先讨论一种朴素的方法，然后是最先进的框架中采用的机制，然后介绍所提出的 GALA 优化，该优化显着提高了矩阵向量乘法的效率。

1.朴素方法矩阵向量乘法的朴素算法如图 3 所示，其中 w 是服务器上的 no×ni 明文矩阵，[x]C 是客户端经 HE 加密过的向量。服务器将 w 的每一行编码成一个单独的明文向量，每个向量长度为 n，详细步骤分别如图中 a,b,c 所示。

2.混合计算为了充分利用密文中的 n 个槽并进一步降低复杂度，先进的方案是结合对角线编码和 RaS，这种混合方法展现了高代价的 Perm 操作数量是 n0 的函数而不是 ni，因此加速了 FC 层的计算，基本思想如图 4 所示。

表 II 比较了朴素方法、混合方法和提出的行编码共享 RaS 矩阵向量乘法(GALA)之间的复杂度。可以看到，所提出的方法完全消除了 HstPerm 操作并显着减少了 Perm 操作。

B.基于卷积的内核分组

本节首先从单输入单输出（SISO）的基本卷积开始，然后是多输入多输出（MIMO）的最新方案，最后是 first-Add-second-Perm（内核分组）实现更高效卷积计算的方案。

（1）基本 SISO 卷积如图 6 所示，SISO 卷积一共需要(kwkh-1)次 HstPerm 操作，kwkh 次 Scmult 操作以及(kwkh-1)次 Add 操作。输出是包含卷积结果的一个密文。

（2）基于 MIOM 卷积的输出旋转如图 7 所示，最终 MIMO 卷积需要一共 cico(cn-1)/cn2 次 Perm 操作，ci(kwkh-1)/cn 次 HstPerm 操作，kwkhcico/cn 次 ScMult 和 co(cikwkh-1)/cn 次 Add 操作。

（3）基于 MIMO 卷积的内核分组我们实际上不需要得到每个块的卷积。由于我们的目标是获得每个内核的卷积，因此在我们提出的 first-Add-second-Perm 方法（内核分组）中组合与同一内核关联的块，以降低 Perm 成本。具体来说，整个内核块被分为两个块 K1 和 K2，这样每个块都是词 cn×cn 个分割块的组合，它们对应于相同的内核（即 K1 中的第一个和第二个内核以及第三个内核和 K2 中的第四个内核）。对于每个新形成的块，所有向量首先通过像 SISO 那样与相应的输入密文进行卷积。然后将与相同核顺序相关联的卷积向量首先相加，最后，这些相加的向量被旋转到相同的核顺序并相加得到卷积结果。如图 8 所示，最后该方法一共需要 co(cn-1)/cn 次 Perm 操作，ci(kwkh-1)/cn 次 HstPerm 操作，kwkhcico/cn 次 ScMult 和 co(cikwkh-1)/cn 次 Add 操作。

表 III 比较了几种卷积计算的复杂度，GALA 的方法减少了 Perm 操作中的 ci/co 的同时没有增加其他操作。

C.噪声管理

打包的 HE 在密文中引入了噪声，理论上隐藏了原始消息。然而，噪声管理对于在一系列 HE 操作后正确解密密文至关重要。我们将证明 GALA 与 GAZELLE 相比具有更好的噪声管理。基于矩阵向量乘法和卷积的计算复杂度，以及如第 2 节所述的 HE 操作的噪声变化。表 IV 显示了不同方案的噪声增长。对于矩阵向量乘法，GALA 具有较低的噪声增长，同时保持输出密文的数量少至一个。对于卷积计算，GALA 降低了噪声与旋转因子相关的项。

D.系统安全

GALA 基于与 GAZELL 相同的安全框架，GALA 中线性计算的安全性完全受到 HE 安全性的保护。非线性计算受到 GC 或其替代方案的保护。TASTY 和 MP2ML 已经证明了基于 GC 的非线性计算的安全性。

4.实验评估

我们在 LAN 和 WAN 设置中进行实验。LAN 设置是在我们实验室的两个工作站之间的千兆以太 上实现的，分别作为客户端和服务器。两台机器都运行 Ubuntu，并配备 Inteli7-87003.2GHzCPU、12 个线程和 16GBRAM。WAN 设置基于本地 PC 和 AmazonAWS 服务器之间的连接，平均带宽为 200Mbps，往返时间约为 13 毫秒。我们已经下载了 GAZELLE(704)、DELPHI(705)和 Cryplow2(706)发布的代码，并在相同的硬件设备和 络设置上运行所有实验。我们在各种神经 络架构下进行了一系列实验。在每个实验中，我们首先运行基线算法（即 GAZELLE、DELPHI 或 Cryplow2）得到基线总运行时间（包括在线运行时间和离线运行时间），然后用 GALA 代替基线算法的线性计算得到一个新的总运行时间，然后用于计算加速比。

虽然 GAZELLE、DELPHI 和 CrypTFlow2 的代码以不同的方式实现，但我们专注于 GALA 在每个方面的加速他们。我们也设置与 GAZELLE 一致的密码参数：1)选择 HE 和 GC 方案的参数用于 128 位安全级别。2)20 位的明文模数 p 足以存储 络中的所有中间值计算。3）密文模数 q 选择为一个 60 位伪梅森素数，略小于 64 位机器上的本地机器字，以启用惰性模块化缩减。4）槽数的选择是允许 128 位安全性的 2 的最小幂，在我们的例子中是 n=2048。

A.微基准测试

在本节中，我们将 GALA 的线性优化的运行时间与最先进的方法进行基准测试和比较后发现，与 GAZELLE 具有相同的通信成本和推理精度，并提高了计算效率。1)矩阵向量乘法：表 V 比较了 GALA 矩阵向量优化与 GAZELLE 和其他两种优化方案和扩展法的计算复杂度。可以看到，GALA 在很大程度上将昂贵的 Perm 操作减少到零。另一方面，与其他三种优化相比，GALA 还为 HE 乘法/加法保持了较少的开销。矩阵向量乘法的运行时间结果总结在表 VI 中，从表中可以看出，GALA 的优化由于使用行编码共享 RaS 模块而获得了很大的加速，它减少了一系列 RaS 计算的代价高昂的 Perm、Mult 和 Add 操作。2）卷积计算：我们将 GALA 与 GAZELLE、DELPHI 和 CrypTFlow2 的计算复杂度和运行时间进行基准测试和比较以进行卷积计算。详情见表 VII 和 VIII。至于计算复杂度，我们将 GALA 与 GAZELLE 进行了比较，GAZELLE 对 HE 的隐私保护卷积计算是当前文献中最优化的方法之一。在不引入额外的 HE 乘法/加法的同时，对于输入大小为 16×16@2048 且内核大小为 1×1@512 的情况，GALA 将最昂贵的 Perm，即 DecPerm 和 HstPerm 减少了 59。这个具有大通道和小内核大小的块在 ResNets 等最先进的神经 络中具有特色，这使得 GALA 适合提升现代 络。

B.经典 络的表现

在本节中，我们在 4 层多层感知器（MLP）上对 GALA 性能进行了基准测试，表 IX 显示了所提出的 GALA 与 GAZELLE 相比的计算复杂度。这种加速的根本基础在于 GALA 对基于 HE 的线性计算的深度优化。我们还注意到 GALA 实现了有限的 MLP 中的 Perm 减少。这是由于密文中的槽数与每层中的输出维度之间的比例很小，这限制了性能增益。在表 X 中也观察到了有限的增益。值得指出的是，MLP 络在实际场景中并未被广泛采用。另一方面，由于最先进的深度神经 络利用大通道和小尺寸内核来捕获数据特征，而特征图的尺寸很大，因此 GALA 对于加速这种模型特别有效。表 XI 显示了 GAZELLE、DELPHI 和 CrypTFlow2 的运行时间，以及 GALA 的加速比。

接下来，我们检查这六个最先进 络的不同层的运行时间分解，如图 9 所示。为了 HE 操作，这里的层索引与原始明文模型略有不同。图中每个子图的 x 轴显示了线性和构成每个 络模型的非线性层。y 轴绘制到一个层的累积运行时间，以及在每一层中，GALA 比 GAZELLE 的加速。

GALA 只专注于优化基于 HE 的线性操作，可以集成到基线模型中。所提出的方法不引入近似，因此，与基线隐私保护模型相比，它不会导致任何准确性损失。此外，与原始明文模型相比，GALA 中唯一可能的精度损失来自 HE 操作中浮点数到定点数的量化。这种量化在包括 CryptFlow2 在内的所有基于 HE 的框架中都是必不可少的。从我们的实验来看，由于量化造成的模型精度损失可以忽略不计，如表 XIII 所示。

5 结论和进一步研究

值得指出的是，即使近年来在隐私保护机器学习方面取得了重大进展，但明文系统（一般低于一秒）和隐私保护系统（范围从秒到数百秒）之间仍然存在着巨大的差距。尽管如此，实现隐私保护机器学习的长期目标仍然是有希望的。首先，隐私保护机器学习系统将部署在具有丰富计算能力的云上。因此，即使在相同的本地硬件上比明文系统花费更多的时间，在具有并行计算基础设施的云上运行它也可以显着减少差距。其次，对隐私保护计算的深入优化的研究工作进一步有助于缩小运行时差距。先进算法和云计算资源的结合可能使隐私保护系统在不久的将来能够达到合适的响应时间来满足某些实际应用的要求。

致谢