Optimized Privacy-Preserving CNN Inference With Fully Homomorphic Encryption

(1) 本文实现了使用多项式来计算卷积运算的同态方案。

Abstract

随着隐私保护问题的出现，研究具有数据隐私保护的机器学习模型具有重大意义。由于FHE可以提供严格的数据隐私保护，因此基于FHE实现的安全模型推理具有显著的实用性。本文针对FHE评估卷积运算提出了一种有效的算法，可以实现无论卷积核大小，该算法的计算代价都保持不变，从而在各种卷积核下将运行时间改善12—46倍。

将该FHE卷积运算算法与CKKS的自举算法结合，可以在CIFAR10/100和ImageNet数据集上实现20层的CNN分类器同态评估，运行时间可以减少18.9%和48.1%。可以看到，该算法对密集型卷积操作评估CNN和探索此类CNN是非常有效的。

1. Introduction

本文对FHE中卷积和卷积层的评估方法进行了一些根本性的改进，具体如下:

(1) 将卷积运算表示为CKKS明文空间$R:=\mathbb{Z}[X]/(X^N+1)$上的多项式算术运算。更准确地说，本文将输入元素打包为环上多项式的系数，这样卷积就可以通过多项式乘法来实现，而不需要任何旋转。

(2) 进一步可以将该算法推广为批处理卷积，然后利用它将尽可能多的卷积输出打包到每个输入密文中。

(3) 进一步修改FHE的自举算法，可以实现卷积运算评估在系数域中，而激活函数评估在槽域中。

2. Preliminaries

A. Notation

$\mathbb{Z},\mathbb{R},\mathbb{C}$分别表示整数环、实数环和复数环。$R:=\mathbb{Z}[X]/(X^N+1)$表示多项式环。

B. CKKS

需要掌握CKKS同态加密的一些基本知识。

(1) Enc/Dec and Addition/Multiplication

(2) Encoding/Decoding and Rotation

(3) Computational Cost of FHE: 对于任意给定的函数，FHE评估的代价主要取决于该函数要求的乘法和旋转的次数。此外，CKKS密文都有一个级别，可以通过降低级别来截断消息的最低有效数字。若要执行L级深度的乘法，则需要L级的密文作为输入，密文大小和运行成本随着密文级别的增加而增加。

(4) Bootstrapping : 为了对0级别的密文继续操作，则需要对密文进行自举运算，然后刷新密文为L级别。

C. Homomorphic Convolution

术语"同态卷积"表示对FHE加密的消息评估卷积运算的方法。

(1) 2D-Convolution:

给定输入$I\in {\mathbb{R}}^{w\times w}$，核$K\in {\mathbb{R}}^{k\times k}$。则2D-卷积$Conv(I,K)\in {\mathbb{R}}^{d\times d}$可以定义为:
$$Conv(I,K{)}_{i,j}:=\sum _{0\le i^{\prime },j^{\prime }\le k}{K}_{i^{\prime },j^{\prime }}\cdot I_{i+i^{\prime },j+j^{\prime }}\text{\hspace{1em}(1)}$$
其中$(i,j)$表示矩阵第$i$行，第$j$列的元素，且$0\le i,j<d:=w-k+1$​。

(2) 批卷积：给定$B{B}^{\prime }$个核，$K^{(B,B^{\prime })}:=(K^{0,0},K^{0,1},...,K^{B-1,B-1})$，B个输入$I^{(B)}=(I^0,I^1,...,I^{B-1})$，其中$K^{i,j}\in {\mathbb{R}}^{k\times k},I^i\in {\mathbb{R}}^{w\times w}$。则批卷积的输出为:
$$Conv(I^{(B)},K^{(B,B^{\prime })}{)}^{b^{\prime }}=\sum _{0\le i<B}Conv(I^i,K^{i,b^{\prime }})\text{\hspace{1em}(2)}$$
其中，$0\le b^{\prime }<B^{\prime }$，$b^{\prime }$表示第$b^{\prime }$个批次，$i$表示第$i$​个批次。

可以看到批输入$I$为$(w,w,B)$，批核$K$为$(k,k,B,B)$。

3. ConvFHE

本文提出算法ConvFHE，该算法新颖的将输入矩阵元素与卷积核元素打包为FHE中明文多项式的系数，下面具体介绍该算法。

A. 消息的系数编码

CKKS的明文空间是$R:=\mathbb{Z}[X]/(X^N+1)$​。不同于CKKS的原来的encoding/decoding算法，本文提出了一种将消息向量直接打包到明文多项式的系数上的encode/decode算法，算法描述如下:
$$CF-Ec{d}_{\Delta }([r_0,r_1,...,r_{N-1}])\to \lfloor \Delta \cdot (r_0+r_{1}X+...+r_{N-1}{X}^{N-1})\rceil$$

$$CF-Dc{d}_{\Delta }(m_0+m_{1}X+...+m_{N-1}{X}^{N-1})\to [m_0/\Delta ,m_1/\Delta ,...,m_{N-1}/\Delta ]$$

该编码算法允许同态计算包含N个实数作为系数的多项式加法/乘法，而通常的CKKS只允许包含N/2个实数的向量之间的运算。

B. 卷积运算的简明表示

我们将证明卷积$Conv(I,K)$可以由$R$上的两个明文多项式的乘积来表示。为了简单起见，我们假设输入$I$和核$K$的大小不会超过环维度N，以确保输入和核可以打包到一个密文中。

(1) Single Convolution

等式(1) 代表的2D-卷积可以表示为$R:=\mathbb{Z}[X]/(X^N+1)$中的两个多项式的乘积。

Theorem 1: 对于输入$I\in {\mathbb{Z}}^{w\times w}$和核$K\in {\mathbb{Z}}^{k\times k}$，其中$max(w^2,k^2)\le N$。令$I(X),K(X)\in R$定义如下:
$$\begin{gathered} I(X):=\sum _{0\le i,j<w}{I}_{i,j}\cdot X^{(i-k)w+j} \\ K(X):=\sum _{0\le i,j<k}{K}_{i,j}\cdot X^{wk-(iw+j)} \end{gathered}$$
其中，当$t<0$时，$X^t$表示$-X^{N+t}$。则$I(X)\cdot K(X)$的第$(iw+j)$个系数为$Conv(I,K{)}_{i,j}$​​。

Corollary 1: 给定输入$I\in {\mathbb{Z}}^{w\times w}$、核$K\in {\mathbb{Z}}^{k\times k}$，正整数$s$，且$(s{w}^2,s{k}^2)=N$。令$I_{sp}(X):=I(X^s)$、$K_{sp}(X):=K(X^s)$，其中$I(X)$和$K(X)$如Theorem 1中描述。则$I_{sp}(X)\cdot K_{sp}(X)$的第$s(iw+j)$个系数为$Conv(I,K{)}_{i,j}$​。

注意，当且仅当$l=0mods$时，$I_{sp}(X)\cdot K_{sp}(X)$的第$l$个系数为0，我们称这种多项式为稀疏打包。

(2) Batch Convolution

回想等式2，批卷积实际上就是一系列单卷积的求和。我们提出的批卷积算法即将批输入和批核编码到一个多项式中。然后通过两个多项式的乘法计算它们的卷积与加和。其关键是对每个单输入$I_{sp}(X)$与核$K_{sp}(X)$均使用稀疏打包，然后每个卷积都被稀疏的计算，进而加和到一起，如图3和算法1所示:

图3分析: 输入$I=(2,2,4)$，核$K=(1,1,4,4)$，这里仅使用核的第i个批次$K^i=(1,1,4)$，即结果为$Conv(I,K^i)=Conv(I_0,K_0^i)+Conv(I_1,K_1^i)+Conv(I_2,K_2^i)+Conv(I_3,K_3^i)$​

表达为多项式的乘积后，结果如下:

发现，实际上这里的$x^3$次项，$x^7$次项，$x^{11}$次项和$x^{1}5$次项的系数正好是第$i$个批次的批卷积结果。

下面分析算法1:

Theorem 1（算法1的正确性）: 对于批输出$I^{(B)}\in {\mathbb{Z}}^{w\times w\times B}$和批核$K^{(B,B)}\in {\mathbb{Z}}^{k\times k\times B\times B}$，假设满足条件$max(w^{2}B,k^{2}B)=N$，令$r_b(X)$为算法1的输出，其中b={0,1,...,B−1}b=\{0,1,...,B-1\}b={0,1,...,B−1}，则有$r_b(X)$的第$B(iw+j)$个系数等于$Conv(I^{(B)},K^{(B,B)}{)}_{i,j}^b$。

注意，算法1输出的是B个批次中的其中一个批次的结果，因此为了获得全部的结果，我们需要遍历b={0,1,...,B−1}b=\{0,1,...,B-1\}b={0,1,...,B−1}，即运行B次算法1。然而，这样的问题是完整的结果由$R$上的B个多项式组成，即分别包含在B个密文中。为了解决该问题，我们可以使用文献[5]中的工作，将这些多项式中我们需要的系数打包到一个多项式中。

---

文献[5]算法描述:

我先去阅读一下这篇文章^.

---