1. 提出背景

1978年，Rivest、Adleman和Dertouzos在文献[1]中就贷款公司数据库的保密问题与计算问题进行了讨论，并首次提出了同态加密的加密方式。后来，随着云计算、大数据、人工智能、机器学习等新兴技术不断兴起，人们越来越发现同态加密对于现阶段信息安全的重要性。2009年，Gentry首次提出自举技术^[2]，实现了第一个全同态加密方案。2010年，Dijk又首次实现了基于整数环上FHE的DGHV方案^[4]。2012年，Kipnis等人给出了基于矩阵和多项式的无噪声FHE方案^[5]。2016年，Jaschke等人通过将有理数近似表示为整数^[6]，实现了明文空间为实数的FHE方案。2017年，Cheon等人实现了可进行浮点数近似计算的层次型FHE方案^[3]（下文称CKKS方案），一年后，Cheon等人又通过自举技术，将CKKS方案扩展为全同态加密方案^[7]，同年，也通过RNS实现了CKKS方案的RNS变体^[8]。

2. 方案原理

同态加密就是在数据仍处于密文的状态下，对密文数据信息进行各种计算，从而使得其结果在变回明文后和对明文进行相应运算时的结果等值。

对于函数$f$，若$f$满足$f(a) + f(b) = f(a+b)$或$f(a) \cdot f(b) = f(a \cdot b)$其一，则称其为半同态，若对于加法与乘法均满足，则称该函数为全同态。我们在这里将加密操作 看作是一个满足同态性质的函数，那么，其密文$Enc(m)$就有

的性质，而且加密函数没有变化，故仍可以用相同的解密函数$Dec()$进行解密，并且解密后的明文与对明文直接进行运算的结果相等：

同理，若加法与乘法均满足，则称该方案为全同态加密方案。

Cheon等人给出的CKKS方案，实现了明文为浮点数的近似计算。该方案首先通过编码技术将明文槽上的$N/2$维复向量变换为$N$次整系数多项式；接着假设其具有循环安全性，引入同态乘密钥$evk$，将同态乘法带来的密文维数扩张加以控制；最后在同态乘法结束后进行“重缩放”，有效地控制噪声对明文的影响。

3. 算法描述

设CKKS方案的安全系数为$\lambda$，明文空间$\mathcal{M} = \mathbb{C}^{N/2}$，映射$\tau$为：

即$m(x) \mapsto \mathbf{m}$，具体关系为$z_j = m(\zeta M ^j)$，其中$\zeta M = \exp(-2\pi i/M)$。方案详细描述如下：

1.$CKKS.KeyGen(1^{\lambda})$

• 选择一个2的方幂的整数$M=M(\lambda,q_L)$, 一个整数$h=h(\lambda,q_L)$, 一个大整数$P = P(\lambda,q_L)$，和一个实数$\sigma=\sigma(\lambda,q_L)$；

• 采样$s \leftarrow HWT(h)$，$a \leftarrow R_{q_L}$，$e \leftarrow DG(\sigma ^2)$，设私钥$sk = (1,s)$，公钥为$pk = (b,a) \in R_{q_L}^2$，其中$b \leftarrow -as + e \ (mod\;q_L)$；

• 采样$a' \leftarrow R_{q_L}$，$e' \leftarrow DG(\sigma ^2)$，设同态乘密钥$evk \leftarrow (b',a') \in R_{P \cdot q_L}^2$，其中$b' = -a's + e' + Ps^2 \; (mod P \cdot q_L)$。

2.$CKKS.Encode(\mathbf{m},\Delta)$

• 对于明文向量$\mathbf{m}$，首先对其等比放大$\left\lfloor \Delta \cdot \mathbf{m} \right\rceil$；

• 接着通过$\tau$映射的逆$\tau^{-1}$将$\left\lfloor \Delta \cdot \mathbf{m} \right\rceil$转化为多项式

  $$m = \left\lfloor \tau ^{-1}(\left\lfloor \Delta \cdot \mathbf{m} \right\rceil) \right\rceil$$

3.$CKKS.Decode(m,\Delta)$

• 对于明文多项式$m$，使用$\tau$映射还原为向量$\mathbf{m}$并等比缩小

  $$\mathbf{m} = \left\lfloor \Delta ^{-1} (\left\lfloor \tau (m) \right\rceil) \right\rceil$$

4.$CKKS.Enc_{pk}(m)$

• 采样$v \leftarrow ZO(0.5)$，$e_0,e_1 \leftarrow DG(\sigma ^2)$，输出密文：

  $$\mathbf{c} = v \cdot pk + (m + e_0,e_1)\;(mod q_L)$$

5.$CKKS.Dec_{sk}(\mathbf{c})$

• 对于$\mathbf{c} = (b,a)$，解密算法为$[\langle \mathbf{c}, \mathbf{sk}\rangle ]q_l$，即

  $$m = b + as\;(mod q_l)$$

  由于CKKS方案在加密时引入了噪声，所以其解密函数生成的明文与原始明文是不同的，但误差的数量级是远远小于明文的，所以该误差是完全可以忽略的。

6.$CKKS.Add(\mathbf{c_1},\mathbf{c_2})$

• 对于$\mathbf{c_1} = (b_1,a_1)$，$\mathbf{c_2} = (b_2,a_2)$，密文的同态加法为相应位直接相加

  $$\mathbf{c_{Add}} = [(b_1 + b_2,a_1 + a_2)]q_l$$

  由于密文的同态乘法会导致密文规模扩大，这将影响到解密算法的执行，从而使得密钥规模随乘法深度的增加而增大。故Cheon等人在方案设计时引入同态乘密钥（$evk$）实现对乘法密文的缩放，使其规模保持在$R_{q_L}^2$中。

7.$CKKS.Mult_{evk}(\mathbf{c_1},\mathbf{c_2})$

• 对于$\mathbf{c_1} = (b_1,a_1)$，$\mathbf{c_2} = (b_2,a_2)$，我们记

  $$(d_0,d_1,d_2) = [(b_1b_2,a_1b_2 + a_2b_1,a_1a_2)]_{q_l}$$

• 则$\mathbf{c_1}$、$\mathbf{c_2}$的同态乘法表示为

  $$\mathbf{c_{Mult}} = (d_0 , d_1) + \left\lfloor P^{-1} \cdot d_2 \cdot evk \right\rceil$$

  但乘法操作会导致噪声增大，从而出现无法正确解密的情况，这时就需要在每次乘法之后进行一个“重缩放”的操作。

8.$CKKS.RS_{l \to l'}(\mathbf{c})$

• 对于密文$\mathbf{c}$，我们对其进行“重缩放”

  $$\mathbf{c'} = \left\lfloor \frac{q'_{l}}{q_l} \mathbf{c} \right\rceil$$

  经“重缩放”后，其密文模数降低为$q_l'$。

4.方案改进

在之后的研究中，人们又对该方案进行了不同程度的改进，如下图：

欧密18^[7]给出了CKKS方案的自举方案，欧密19^[9]对其进行了改进；而SAC18^[8]则是提出了CKKS方案的RNS变体，但是其使用的是欧密18中的自举方案，自举精度远达不到实际需求；故在RSA20^[10]中，又结合欧密19中的自举改进对RNS-CKKS方案的自举进行了改进；21年的欧密会上，又有两个方案被相继提出，一个是在RSA20的基础上对自举精度进行了提升^[11]，另一个则是提出了一种新的自举方案^[12]，相较之前的方案，精度、效率和安全性上都有了明显的提升。

4.1 自举方案

这里只对欧密18中提到的自举方案进行说明。

由于明文槽上的任意线性变换都可表示为$\mathbf{z} \mapsto A \cdot \mathbf{z} + B \cdot \overline{\mathbf{z}}$，即对于任意线性变换，我们都可以使用两个$N/2$维的矩阵表示。故我们在同态计算编解码操作时需要用到$MatMult(\mathbf{ct},A)$函数以实现同态计算矩阵乘法，其中$\mathbf{ct} \in R_q^2$并且$A \in \mathbb{C}^{N/2 \times N/2}$，这个函数相当于对$\mathbf{ct}$加密的向量$\mathbf{m}$进行了如下的操作：

其中，$\odot$为向量按位乘法，$\rho$为循环向左移位。

而对于模运算，Cheon等人首先模运算近似为正弦函数上的运算：

接着，再通过欧拉公式，

将正弦函数上的运算转换到指数函数上的运算：

最后利用文献[4]给出的计算指数函数的算法进行运算即可：

4.2 RNS变体

为了有效地实现多项式运算，Gentry等人基于CRT提出了一种双CRT表示的分圆多项式表示方案[13]。第一层CRT层通过使用RNS将多项式分解成具有较小模的多项式分量。第二层则是通过NTT的方法，将每个小多项式转换为整数向量。在双CRT表示中，任意多项式都可以用由小整数组成的矩阵来识别，并且可以通过执行不同分量的模操作来实现有效的多项式运算。

Cheon等人提出了CKKS方案的RNS变体[9]，实现了在RNS上的近似全同态加密方案，具体算法如下：

1.$RNS.Setup(q,L,\eta )$

• 输入基本整数$q$，深度$L$，比特精度$\eta$；

• 选择一个基$\mathcal{C} = \{q_0,q_1,\cdots,q_L\}$，满足$q/q_l \in (1 - 2^{-\eta},1 + 2^{-\eta})$，并且对于乘法深度为$l$的密文模数$Q_l = \prod_{i = 0}^l q_i$，其相邻模数模数具有相同的比率$Q_l/Q_{l-1} = q_l \approx q$；

• 选择一个$KSGen(s_1,s_2)$算法需要的模数$P = \prod_{i = 0}^{k-1} p_i$；

• 生成基$\mathcal{D} = \{p_0,p_1,\cdots,p_{k-1},q_0,q_1,\cdots,q_{l-1}\}$，$\mathcal{B} = \{p_0,p_1,\cdots,p_{k-1}\}$，$\mathcal{C}_l = \{q_0,q_1,\cdots,q_{l-1}\}$；

• 选择一个2的幂整数$N$，$\mathbb{R}$上的私钥分布$\chi _{key}$，加密参数分布$\chi _{enc}$和误差分布$\chi _{err}$。

2.$RNS.KSGen(s_1,s_2)$

• 采样$(a'_0,a'_1,\cdots,a'_{k + L}) \leftarrow U(\prod_{i = 0}^{k-1}\mathbb{R}_{p_i}\times\prod_{j = 0}^{L}\mathbb{R}_{q_j})$，$e' \leftarrow \chi _{err}$；

• 对于给定的秘密多项式$s_1,s_2 \in \mathbb{R}$，计算：
  当$0 \leqslant i < k$时，

  $$b'_i = -a'_i\cdot s_2 + e' \ mod\;p_i$$

  当$0 \leqslant j \leqslant L$时，

  $$b'_{k+j} = -a'_{k+j}\cdot s_2 + [P]_{q_j} \cdot s_1 + e' \ mod\;q_j$$

• 输出转换密钥$\mathbf{swk}$为：

  $$\mathbf{swk} = (\mathbf{swk}_0,\mathbf{swk}_1,\cdots,\mathbf{swk}_{k+L}) \in \prod_{i = 0}^{k-1}\mathbb{R}_{p_i}^2\times\prod_{j = 0}^{L}\mathbb{R}_{q_j}^2$$

  其中，$\mathbf{swk}_i = (b'_i,a'_i)$。

3.$RNS.KeyGen()$

• 采样$(a'_0,a'_1,\cdots,a'_L) \leftarrow U(\prod_{j = 0}^{L}R_{q_j})$，$e \leftarrow \chi _{err}$，$s \leftarrow \chi _{key}$，并记私钥为$\mathbf{sk} = (1,s)$；

• 计算$b_i = -a_i\cdot s + e \ mod\;q_j$，$0 \leqslant j \leqslant L$；

• 生成同态乘密钥

  $$\mathbf{evk} = KSGen(\mathbf{s}^2,\mathbf{s})$$

4.$RNS.Encode(\mathbf{m},\Delta)$

• 对于明文向量$\mathbf{m}$，首先对其等比放大$\left\lfloor \Delta \cdot \mathbf{m} \right\rceil$；

• 接着通过$\tau$映射的逆$\tau^{-1}$ 将$\left\lfloor \Delta \cdot \mathbf{m} \right\rceil$ 转化为多项式

  $$m = \left\lfloor \tau ^{-1}(\left\lfloor \Delta \cdot \mathbf{m} \right\rceil) \right\rceil$$

5.$RNS.Decode(m,\Delta)$

• 对于明文多项式$m$，使用$\tau$映射还原为向量$\mathbf{m}$并等比缩小

  $$\mathbf{m} = \left\lfloor \Delta ^{-1} (\left\lfloor \tau (m) \right\rceil) \right\rceil$$

6.$RNS.Enc_{\mathbf{pk}}(m)$

• 采样$v \leftarrow \chi _{enc}$，$e0,e_1 \leftarrow \chi _{err}$；

• 输出密文

  $$\mathbf{ct} = (\mathbf{ct}_0,\mathbf{ct}_1,\cdots,\mathbf{ct}_L) \in \prod_{j = 0}^{L}\mathbb{R}_{q_j}^2$$

  其中，$\mathbf{ct}_j = (v \cdot \mathbf{pk}_j + (m + e_0,e_1)) \ mod\;q_j$。

7.$RNS.Dec_{\mathbf{sk}}(\mathbf{ct})$

• 对于密文$\mathbf{ct}$，输出$[\left\langle \mathbf{ct}_0,\mathbf{sk}\right\rangle]_{q_0}$，即

  $$m = b_0 + a_0 \cdot s \ mod\;q_0$$

之后便是运算部分，由于RNS的特性，在该表征系统上的运算均可分解为各个基上的运算，并且相互独立。故RNS上运算的具体算法展示如下：

8.$RNS.Add(\mathbf{ct},\mathbf{ct}')$

• 给定两个密文$\mathbf{ct},\mathbf{ct}' \in \prod_{j = 0}^{l}\mathbb{R}_{q_j}^2$，分别表示为$\mathbf{ct} = (\mathbf{ct}_0,\cdots,\mathbf{ct}_l)$和$\mathbf{ct}' = (\mathbf{ct}'_0,\cdots,\mathbf{ct}'_l)$，RNS上的同态加法是对应位的元素分别相加，即

  $$\mathbf{ct}_{add} = (\mathbf{ct}_{add_1},\mathbf{ct}_{add_2},\cdots,\mathbf{ct}_{add_l},)$$

  其中，$\mathbf{ct}_{add_i} = (\mathbf{ct}_i + \mathbf{ct}'_i) \ mod\;q_i$。

9.$RNS.Mult_{\mathbf{evk}}(\mathbf{ct},\mathbf{ct}')$

• 给定两个密文$\mathbf{ct},\mathbf{ct}' \in \prod_{j = 0}^{l}\mathbb{R}_{q_j}^2$，分别表示为$\mathbf{ct} = (\mathbf{ct}_0,\cdots,\mathbf{ct}_l)$和$\mathbf{ct}' = (\mathbf{ct}'_0,\cdots,\mathbf{ct}'_l)$；

• 计算

  $$\begin{aligned} \mathbf{d}_{i_0} &= \mathbf{ct}_{i_0} \cdot \mathbf{ct}'_{i_0} \ mod\;q_j\\ \mathbf{d}_{i_1} &= \mathbf{ct}_{i_0} \cdot \mathbf{ct}'_{i_1} + \mathbf{ct}_{i_1} \cdot \mathbf{ct}'_{i_0} \ mod\;q_j\\ \mathbf{d}_{i_2} &= \mathbf{ct}_{i_1} \cdot \mathbf{ct}'_{i_1} \ mod\;q_j \end{aligned}$$

• 使用近似模提升，将$\mathbf{d}_{i_2}$的基由$\mathcal{C}_l$提升到$\mathcal{D}_l$

  $$Modup_{\mathcal{C}_l \to \mathcal{D}_l}(\mathbf{d}_{2_0},\cdots,\mathbf{d}_{2_l}) = (\widetilde{\mathbf{d}}_{2_0},\cdots,\widetilde{\mathbf{d}}_{2_{k-1}},\mathbf{d}_{2_0},\cdots,\mathbf{d}_{2_l})$$

• 重线性化

  $$\widetilde{\mathbf{ct}} = (\widetilde{\mathbf{ct}}_0,\widetilde{\mathbf{ct}}_1,\cdots,\widetilde{\mathbf{ct}}_{k+l})$$

  其中

  $$\begin{aligned} \widetilde{\mathbf{ct}}_i &= \widetilde{\mathbf{d}}_{2_i} \cdot \mathbf{evk}_i \ mod\;p_i \ \ \ 0 \leqslant i < k\\ \widetilde{\mathbf{ct}}_{k+j} &= \mathbf{d}_{j} \cdot \mathbf{evk}_{k+j} \ mod\;q_j \ \ \ 0 \leqslant j \leqslant l \end{aligned}$$

• 再通过近似模降低，将$\widetilde{\mathbf{ct}}$的基由$\mathcal{D}_l$降低到$\mathcal{C}_l$

  $$Moddown_{\mathcal{D}_l \to \mathcal{C}_l}(\widetilde{\mathbf{ct}}_0,\cdots,\widetilde{\mathbf{ct}}_{k+l}) = (\widehat{\mathbf{ct}}_0,\cdots,\widehat{\mathbf{ct}}_l )$$

• 输出

  $$\mathbf{ct}_{mult} = (\mathbf{ct}_{mult_0},\mathbf{ct}_{mult_1},\cdots,\mathbf{ct}_{mult_l})$$

  其中，$\mathbf{ct}_{mult_i} = (\widehat{\mathbf{ct}}_{i_0} + \mathbf{d}_{0_i},\widehat{\mathbf{ct}}_{i_1} + \mathbf{d}_{1_i}) \ mod\;q_i$。

11.$RNS.RS(\mathbf{ct})$

• 对于$l$级密文$\mathbf{ct} = (\mathbf{ct}_0,\mathbf{ct}_1,\cdots,\mathbf{ct}_l) \in \prod_{j = 0}^{l}\mathbb{R}_{q_j}^2$，输出

  $$\mathbf{ct}' = (\mathbf{ct}'_0,\mathbf{ct}'_1,\cdots,\mathbf{ct}'_{l-1}) \in \prod_{j = 0}^{l-1}\mathbb{R}_{q_j}^2$$

  其中，$\mathbf{ct}'_j = (q_l^{-1} \cdot (c_{0_j} - c_{0_l}),q_l^{-1} \cdot (c_{1_j} - c_{1_l})) \ mod\;q_j$。

参考文献

[1] Rivest R L , Adleman L M , Dertouzos M L . On Data Banks and Privacy Homomorphisms[J]. Foundations of Secure Compuation, 1978.

[2] Gentry C . Fully homomorphic encryption using ideal lattices[J]. Stoc, 2009.

[3] Cheon J H , Kim A , Kim M , et al. Homomorphic Encryption for Arithmetic of Approximate Numbers[C]// International Conference on the Theory and Application of Cryptology and Information Security. Springer, Cham, 2017.-1

[4] Dijk M V , Gentry C , Halevi S , et al. Fully Homomorphic Encryption over the Integers[C]// International Conference on Theory & Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2010.

[5] Aviad Kipnis E H . 1 Efficient Methods for Practical Fully-Homomorphic Symmetric-key Encryption, Randomization, and Verification[J]. Urban Research & Practice, 2012, 7(3):255-257.

[6] Jschke A , Armknecht F . Accelerating Homomorphic Computations on Rational Numbers[J]. Springer, Cham, 2016.

[7] Cheon J H , Han K , Kim A , et al. Bootstrapping for Approximate Homomorphic Encryption[J]. Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2018.-2

[8] Cheon J H , Han K , Kim A , et al. A Full RNS Variant of Approximate Homomorphic Encryption[J]. Selected areas in cryptography :. annual international workshop, SAC. proceedings. SAC (Conference), 11349:347-368.-2

[9] Chen H , Chillotti I , Song Y . Improved Bootstrapping for Approximate Homomorphic Encryption[C]// International Conference on the Theory & Applications of Cryptographic Techniques. Springer, Cham, 2019.-3

[10] Han K , D Ki. Better Bootstrapping for Approximate Homomorphic Encryption[C]// Cryptographers’ Track at the RSA Conference. Springer, Cham, 2020.-4

[11] Lee J W , Lee E , Lee Y , et al. High-Precision Bootstrapping of RNS-CKKS Homomorphic Encryption Using Optimal Minimax Polynomial Approximation and Inverse Sine Function[M]. 2021.-5

[12] Bossuat J P , Mouchet C , Troncoso-Pastoriza J , et al. Efficient Bootstrapping for Approximate Homomorphic Encryption with Non-sparse Keys[M]. 2021.-5

[13] Gentry C , Halevi S , Smart N P . Homomorphic Evaluation of the AES Circuit[C]// Annual Cryptology Conference. Springer, Berlin, Heidelberg, 2012.