目录

论文笔记:GALA - Greedy ComputAtion for Linear Algebra in Privacy-Preserved Neural Networks

NDSS 2021

Qiao Zhang, Chunsheng Xin, and Hongyi Wu

系统描述

本文提出的GALA系统用于简化隐私保护神经网络模型中的线性计算(即矩阵-向量乘法和卷积)。基于HE的线性计算包括三个基本运算:同态加法(ADD)乘法(MULT)置换(PERM)。本研究表明,线性计算在总的计算开销中占主导地位,而基于HEs的线性计算中最耗时的部分是一系列更详细的PERM运算来实现点积和卷积。Gala的目标是最大限度地减少PERM操作,从而大大减少总体计算时间。我们把基于HE的线性计算看作是一系列的加法、乘法和PERM运算。线性计算的两个输入是来自客户端的加密向量(或通道)和来自服务器的明文权重矩阵(或核)。输出是加密的点积(或卷积)。每一步的目标是按照ADD、MULT和PERM的降序优先级选择最有效的操作。因此,GALA可以有效地减少基于HE域的线性计算的开销。最近的隐私保护神经网络框架可以将Gala集成为即插即用模块,以进一步提高它们的效率。我们还分析了GALA的(更好的)噪声管理和(保证的)系统安全性。

Row-encoding-share-RaS Matrix-Vector Multiplication

首先是矩阵-向量乘法,这里考虑的场景是服务器拥有明文参数矩阵,要与来自客户端的加密向量相乘。

朴素方法

假设现在有明文矩阵 $\boldsymbol{w}$​​ 和密文向量 $[\boldsymbol{x}]_c$​,矩阵维度为 $n_o \times n_i$,向量长度为 $n_i$。

https://images.yingwai.top/picgo/20210808224256.png

  1. 首先将矩阵拆分成 $n_o$ 个行向量;
  2. 然后分别计算这 $n_o$ 个行向量与 $[\boldsymbol{x}]_c$​​ 的内积,得到 $n_o$ 个向量 $[\boldsymbol{u}_0]_c, \ \dots$;
  3. 对上一步得到的每个向量,都通过 $\log_2n_i$​​ 个 RaS 操作进行计算:
    • 将向量的副本中的每个元素往前移动 $\frac{n_i}{2}$ 个位置,再把移动后的向量副本与原副本相加;
    • 将向量的副本中的每个元素往前移动 $\frac{n_i}{4}$​​ 个位置,再把移动后的向量副本与原副本相加;
    • 重复上述操作直到移动的位数为0。

最后可以得到 $n_o$ 个向量,每个向量中第一个位置的值即为 $\boldsymbol{w}$ 中对应行与 $[\boldsymbol{x}]_c$​ 进行向量乘法的结果。​

各操作次数:

ScMult Perm Add
$n_o$ $n_o \log_2 n_i$ $n_o \log_2 n_i$

这种方法对密文空间利用率很低,导致线性计算效率非常低。

混合计算(GAZELLE)

为了充分利用密文中的 $n$​​ 个时隙并进一步降低复杂度,最先进的方案是通过利用在FC(全连接)层中 $n_o$ 通常远小于 $n_i$​ 的性质来组合对角编码和RaS。这种混合方法表明,昂贵的PERM操作的数量是关于 $n_i$​ 的函数而不是关于 $n_o$​ 的函数,因此加速了FC层的计算。

https://images.yingwai.top/picgo/20210726162750.png

  1. 先把 $\boldsymbol{w}$ 用对角线编码的方式进行编码,如上图的 Step(a);
  2. 再将 $[\boldsymbol{x}]_c$ 旋转 $n_o - 1$​ 次,加上原向量得到 $n_o$ 个向量;
  3. 将编码后的矩阵中得 $n_o$​ 个行向量与旋转得到的 $n_o$​​ 个向量分别作向量内积;
  4. 把上一步中得到的两个内积结果向量相加,再通过RaS操作即可获得最终结果。

各操作次数:

ScMult HstPerm Perm Add
$\frac{n_i n_o}{n}$​ $\frac{n_i n_o}{n} - 1$ $\log_2 \frac{n}{n_o}$ $\frac{n_i n_o}{n} + \log_2 \frac{n}{n_o} - 1$​

只有一个输出密文,与朴素方法相比,有效地提高了时隙利用率。

行编码-共享-RAS乘法(GALA)

本文提出的GALA框架是基于对混合方法的两个观察结果。首先,混合方法在PERM和HstPerm操作之间进行了权衡,其中PERM的数量(这是最昂贵的HE操作)与密文中的槽数量成正比。

https://images.yingwai.top/picgo/20210727153511.png

  1. 类似地对 $\boldsymbol{w}$ 进行编码,但这次仅仅是隔列把两个行向量进行一次交换;
  2. 将编码后的各个行向量分别与 $[\boldsymbol{x}]_c$ 作内积;
  3. 将得到的第二个向量旋转 $n_o-1$ 个位置,再与第一个向量相加;
  4. 转换为明文下的Ras操作:
    • 服务器生成一个随机向量,并用上一步得到的结果减去这个随机向量的密文;
    • 服务器将得到的差发送给客户端;
    • 客户端解密得到的向量,并在明文下进行RaS操作;
    • 服务器对随机向量在明文下进行RaS操作。

各操作次数:

ScMult Perm Add
$\frac{n_i n_o}{n}$ $\frac{n_i n_o}{n} - 1$ $\frac{n_i n_o}{n} - 1$

三者对比

方法 Perm HstPerm ScMult Add
朴素 $n_o \log_2 n_i$ $0$ $n_o$ $n_o \log_2 n_i$
GAZELLE $\log_2 \frac{n}{n_o}$ $\frac{n_i n_o}{n} - 1$ $\frac{n_i n_o}{n}$ $\frac{n_i n_o}{n} + \log_2 \frac{n}{n_o} - 1$
GALA $\frac{n_i n_o}{n} - 1$ $0$ $\frac{n_i n_o}{n}$ $\frac{n_i n_o}{n} - 1$

Kernel Grouping Based Convolution

接着是卷积,跟矩阵-向量乘法一样,先从单输入单输出(SISO)的基本卷积开始,再到本文之前最新的、以及本文的多输入多输出(MIMO)方案。

假设服务器有维度为 $k_w \times k_h \times c_i$​ 的卷积核,并且客户端将维度为 $u_w \times u_h$ 的加密数据发送给服务器,服务器需要计算卷积核与加密数据的同态卷积。

基础的 SISO 卷积

SISO是MIMO的一个特殊情况:$c_i = c_o = 1$,如下图,加密数据 $[\boldsymbol{x}]_c$ 维度为 $u_w \times u_h$,卷积核 $\mathsf{K}$ 维度为 $k_w \times k_h$。

https://images.yingwai.top/picgo/20210727161835.png

卷积过程可以可视化为将 $\mathsf{K}$ 放在输入数据 $[\boldsymbol{x}]_c$ 的不同位置,然后在每个位置计算卷积核与窗口内的相应数据值之间的元素乘积之和。如上图,首先是将 F5 放在 M1 的位置,然后一直移动 $\mathsf{K}$​,把 F5 放在 M2 到 M9 的位置去计算不同窗口的卷积。

卷积通过以下步骤获得:

  1. 根据相应位置处的部分和形成核系数 $\mathsf{f_j}$,如上图 Step(b);
  2. 用相应的核系数与9个旋转后的 $\mathsf{π_j}$​ 作内积;
  3. 最后把上一步的9个内积结果相加起来。

对第一步的理解:

  • 核系数 $\mathsf{f_j}$ 的生成是根据对应元素能影响到数据中的元素位置决定的:具体就是会对哪个元素产生影响,对应的位置就不为0。比如上图中的 F7,它在运算过程中能对 M2、M3、M5、M6 产生影响,因此对应的核系数就是这四个位置有值;
  • $\mathsf{π_j}$​​​​ 是根据核系数对应元素要与谁运算来生成的:具体就是根据对应的核系数的元素要与哪些元素作乘法,就把这些元素通过旋转移动到对应的位置。比如上图中要与 F7 进行计算的元素是 M4、M5、M7、M8,那么就是通过旋转操作将他们推到右上角。

各操作次数:

HstPerm ScMult Add
$k_wk_h - 1$ $k_wk_h$ $k_wk_h - 1$

基于输出旋转的 MIMO 卷积(GAZELLE)

现在考虑更一般的情况即MIMO,其中 $c_i$​​ 或 $c_o$​​​ 不为1。简单的方法就是把 $c_i$​​ 个输入频道加密成 $c_i$​​ 个密文,$c_o$​​ 个卷积核每个都包括 $c_i$​​​ 个滤波器。通过 SISO 将每个密文与每个滤波器作卷积,再把 $c_i$​ 个结果相加得到卷积。因此,朴素方法的各操作次数为:

HstPerm ScMult Add
$c_i(k_wk_h - 1)$​ $c_ic_ok_wk_h$​ $c_o(c_ik_wk_h - 1)$​

假设密文中的时隙 $n$ 的数量通常大于信道大小 $u_wu_h$​,则共同输出密文中的密文利用率(输出期望结果的有意义的时隙)很低。

为了提高 MIMO 卷积的密文利用率和计算效率,现有的方法(输出旋转[38])首先将 $c_n$​​ 通道的输入数据打包成一个密文,从而得到 $\frac{c_i}{c_n}$​​ 个输入密文(如下图,其中四个输入通道形成两个密文,每个密文包括两个通道)。同时,将 $c_o$​​ 个卷积核看作是 $c_o \times c_i$​​ 块,块的每一行包括一个卷积核的 $c_i$​​ 个2D滤波器。然后,将MIMO卷积视为矩阵向量乘法,其中元素乘法被卷积取代。由于每个密文有 $c_n$​​ 个通道,所以内核块被分成 $\frac{c_oc_i}{c^2_n}$​​ 个块(如下图中的 Step(a),其中卷积核块被分成 $\mathsf{K1}$​​ 到 $\mathsf{K4}$​)。

https://images.yingwai.top/picgo/20210729155903.png

因为是想要利用类似上面提到的混合计算方法来计算,所以 Step(a) 中也按着混合计算中的方法,根据输入向量的维度,把矩阵分成了多个块。

这样每个输入密文可以通过 SISO 直接与每个划分块中的向量卷积,并且每个划分块的卷积是通过将卷积向量旋转到与对角线向量相同的核阶数并求和来获得的(见 Step(b))。

最后通过 Perm 和 Add 操作得到了最终的 $\frac{c_o}{c_n}$ 个输出密文。在这个过程中,对于 $\frac{c_oc_i}{c^2_n}$ 个块中的每一个,一共有 $c_n$​​ 个类似 SISO 的卷积操作。根据上面对 SISO 的分析以及图中的步骤,每个块需要

  • $c_nk_wk_h$​ 个 ScMult 操作
  • $c_n - 1$​ 个 Perm 操作
  • $c_n(k_wk_h-1)+c_n - 1 = c_nk_wk_h - 1$​ 个 Add 操作

然后根据卷积核的分块方式,同一个卷积核中的不同滤波器被分到了 $\frac{c_i}{c_n}$​​​​​ 个块中,因此他们还需要进行相加来获得对应卷积核最终的计算结果,同一个卷积核中的不同滤波器需要相加 $\frac{c_i}{c_n} - 1$​​​ 次,而不同的卷积核被分进了 $\frac{c_o}{c_n}$​​​ ​个块中,因此这个部分需要的相加次数为 $(\frac{c_i}{c_n} - 1) \frac{c_o}{c_n}$​​,加上每个块所需的相加次数,总的相加次数为:

$$ \begin{align} \frac{c_oc_i}{c^2_n}(c_nk_wk_h - 1) + (\frac{c_i}{c_n} - 1) \frac{c_o}{c_n} = \frac{c_o}{c_n}(c_ik_wk_h - 1) \end{align} $$

而根据朴素方法的 HstPerm 次数为 $c_i(k_wk_h - 1)$​​,因此本方法的 HstPerm 次数为 $\frac{c_i(k_wk_h - 1)}{c_n}$​​​。

各操作次数:

Perm HstPerm ScMult Add
$\frac{c_ic_o}{c^2_n}(c_n-1)$ $\frac{c_i}{c_n}(k_wk_h - 1)$​ $k_wk_h \frac{c_ic_o}{c_n}$ $\frac{c_o}{c_n}(c_ik_wk_h - 1)$​

基于核分组的 MIMO 卷积(GALA)

对于上面的 MIMO 卷积的一个关键观察是,$\frac{c_oc_i}{c^2_n}$ 个块中的每一个需要 $c_n-1$ 个昂贵的PERM运算来获得该块的卷积,然而实际上不需要得到每个块的卷积。由于我们的目标是获得每个卷积核的卷积,因此在我们提出的 first-Add-second-Perm 方法(内核分组)中组合与相同内核相关联的块,以降低 PERM 成本。具体地说,在下图的 Step(a) 中,整个内核块被分成两个块 $\mathsf{K1}$ 和 $\mathsf{K2}$,使得每个块是对应于相同核(即 $\mathsf{K1}$ 中的第一、第二个卷积核以及 $\mathsf{K2}$​ 中的第三和第四个卷积核)的 $\frac{c_i}{c_n} $​ 个被划分为含有 $c_n$ 个元素的块的组合。

https://images.yingwai.top/picgo/20210730164000.png

对于每个新形成的块,所有向量首先通过类 SISO 卷积与相应的输入密文卷积。然后将与同一个卷积核相关联的卷积向量相加在一起(见上图 Step(b) 中旋转之前的卷积向量相加)。最后,将这些相加的向量旋转到相同的核阶数并求和,以获得卷积结果(见上图 Step(b) 中每个块的旋转和最终相加)。

核分组计算需要对 $\frac{c_o}{c_n}$​ 个块中的每个进行 $c_n - 1$​​ 次 Perm 操作,比 GAZELLE 减少了 $\frac{c_i}{c_n}$​ 倍。因为对于最先进的神经网络,$\frac{c_i}{c_n}$ 可以达到 256,因此这种效率提升是可观的。

与上面讨论的基于输出旋转的 MIMO 卷积方案类似,该方案中有两个输出密文。对于每一个新形成的块,都有 $c_i$​​ 个类 SISO 卷积。然后,对于每一个 $c_n$​​ 核阶,都有 $\frac{c_i}{c_n}$​​ 个卷积需要求和,这里需要 $c_n$​​ 个 Add 操作。这些相加的卷积被进一步旋转到相同的核阶数,并相加以得到最终的卷积。因此所提出的 MIMO 卷积总共需要 $\frac{c_o}{c_n}(c_n-1)$​​ 个 Perm 操作、$\frac{c_i}{c_n}(k_wk_h - 1)$​​ 个 HstPerm 操作、$k_wk_h \frac{c_ic_o}{c_n}$​​ 个 ScMult 操作和 $\frac{c_o}{c_n}(c_ik_wk_h - 1)$​​ 个 Add 操作。

各操作次数:

Perm HstPerm ScMult Add
$\frac{c_o}{c_n}(c_n-1)$​ $\frac{c_i}{c_n}(k_wk_h - 1)$​ $k_wk_h \frac{c_ic_o}{c_n}$ $\frac{c_o}{c_n}(c_ik_wk_h - 1)$​

两者对比

方法 Perm HstPerm ScMult Add
GAZELLE $\frac{c_ic_o}{c^2_n}(c_n-1)$​ $\frac{c_i}{c_n}(k_wk_h - 1)$ $k_wk_h \frac{c_ic_o}{c_n}$ $\frac{c_o}{c_n}(c_ik_wk_h - 1)$
GALA $\frac{c_o}{c_n}(c_n-1)$ $\frac{c_i}{c_n}(k_wk_h - 1)$ $k_wk_h \frac{c_ic_o}{c_n}$ $\frac{c_o}{c_n}(c_ik_wk_h - 1)$

噪音管理

矩阵-向量乘法

方法 计算后的噪音 密文数量
朴素 $n_i \eta_0 \eta_{mult}+(n_i-1)\eta_{rot}$ $n_o$
GAZELLE $n_i\eta_0\eta_{mult} + [\frac{n_in_o-n}{n_o}\eta_{mult}+\frac{n-n_o}{n_o}]\eta_{rot}$​ $1$
GALA $\frac{n_in_o}{n}\eta_0\eta_{mult} + (\frac{n_in_o}{n}-1)\eta_{rot}$ $1$

卷积

方法 计算后的噪音 密文数量
GAZELLE $c_i \eta_\Delta+\frac{c_i}{c_n}(n_i-1)\eta_{rot}$ $\frac{c_o}{c_n}$​
GALA $c_i \eta_\Delta+\eta_{rot}$ $\frac{c_o}{c_n}$

其中 $\eta_\Delta = k_wk_h\eta_{mult}\eta_0 + (k_wk_h-1)\eta_{rot}\eta_{mult}$​。