参考文献：

1. [BV11] Brakerski Z, Vaikuntanathan V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[C]//Annual cryptology conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011: 505-524.
2. [GHS12] Gentry C, Halevi S, Smart N P. Homomorphic evaluation of the AES circuit[C]//Annual Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 850-867.
3. [CP16] Crockett E, Peikert C. Λολ: Functional Lattice Cryptography[C]//Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security. 2016: 993-1005.
4. [BEHZ16] Bajard J C, Eynard J, Hasan M A, et al. A full RNS variant of FV like somewhat homomorphic encryption schemes[C]//International Conference on Selected Areas in Cryptography. Cham: Springer International Publishing, 2016: 423-442.
5. [HPS19] Halevi S, Polyakov Y, Shoup V. An improved RNS variant of the BFV homomorphic encryption scheme[C]//Topics in Cryptology–CT-RSA 2019: The Cryptographers’ Track at the RSA Conference 2019, San Francisco, CA, USA, March 4–8, 2019, Proceedings. Springer International Publishing, 2019: 83-105.
6. [KPZ21] Kim A, Polyakov Y, Zucca V. Revisiting homomorphic encryption schemes for finite fields[C]//Advances in Cryptology–ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part III 27. Springer International Publishing, 2021: 608-639.

RNS Basis Extension

一般地，FHE 需要很大的模数 $Q$，将它写作 $Q={\prod }_{i=1}^L{q}_i$，满足 $q_i=1(\mathrm{mod}2N)$，我们简记 $Q_i=q_1\cdots q_i$，集合 { q i } \{q_i\} {qi​} 称为 RNS basis，它们的大小至多为 $64$ 比特。我们希望 FHE 的全部运算都是单精度的（现代计算机的机器字），也就是全部运算都在 RNS 下完成，而不需要多精度算术。

不同的 RNS 之间的转换，将环元素 $a\in {\mathcal{R}}_Q$ 从模数 $Q=q_1\cdots q_k$ 下的 $[a{]}_Q$ 转换到模数 $P=p_1\cdots p_l$ 下的 $[[a{]}_Q{]}_P$，可以直接在 RNS 下计算：
$$\text{FastBaseExt}(a,Q,P)={\left\{\sum _{i=1}^k{\left[a\cdot {\left(\frac{Q}{q_i}\right)}^{-1}\right]}_{q_i}\cdot \frac{Q}{q_i}(\mathrm{mod}{p}_j)\right\}}_{j=1,\cdots ,l}$$
我们简记 $q_i^{\ast }:=Q/q_i$ 和 ${\tilde{q}}_i:=(Q/q_i{)}^{-1}(\mathrm{mod}{q}_i)$，满足 $q_i^{\ast }\cdot {\tilde{q}}_i\equiv 1(\mathrm{mod}{q}_i)$，那么根据 CRT 合成定理，
$$\sum _i[a\cdot {\tilde{q}}_i{]}_{q_i}\cdot q_i^{\ast }=[a{]}_Q+u\cdot Q\in \mathbb{Z}$$
其中的 $\Vert u{\Vert }_{\infty }\le k/2$ 称为 $Q$-overflow，因此算法 $\text{FastBaseExt}(a,Q,P)$ 输出的只是 $[[a{]}_Q{]}_P$ 的近似值 $[[a{]}_Q+u\cdot Q{]}_P$

在有些实例中，$u$ 的影响几乎可忽略；但是还有一些实例中，$u$ 可能会导致较为显著的噪声增长，需要想办法去除它。

我们滥用符号，$Q,P$ 代表对应的 RNS basis 集合，$[a{]}_Q$ 代表它的 RNS 表示。

$\gamma$-correction technique

BFV 的一个关键计算是
$$\lfloor \frac{P}{Q}[a{]}_Q\rceil =\frac{P\cdot [a{]}_Q-[Pa{]}_Q}{Q}\in {\mathcal{R}}_P$$
因为上述运算是整除法，因此可以用模乘逆元替代，$(P\cdot [a{]}_Q-[Pa{]}_Q)\cdot Q^{-1}(\mathrm{mod}P)$

[BEHZ16] 采取整数指令，额外引入和 $P,Q$ 互素的整数 $\gamma$，假设 $[a{]}_Q=Q/P\cdot m+e+Qr$，将 $[a{]}_Q$ 加倍 $\gamma$，那么
$$\begin{array}{rl}& \text{FastBaseExt}(\gamma Pa,Q,\gamma P)\cdot [-Q^{-1}{]}_P\\ =& [[\gamma Pa{]}_Q+u\cdot Q{]}_{\gamma P}\cdot [-Q^{-1}{]}_{\gamma P}\\ =& \lfloor \frac{\gamma P}{Q}[a{]}_Q\rceil -u\\ =& \gamma \cdot (m+Pr)+\lfloor \frac{\gamma Pe}{Q}\rceil -u\end{array}$$
当 $\gamma$ 满足某条件时（文章中写的我看不懂，它没解释），RNS 的关于 $\gamma$ 的部分，满足
$${\left[\lfloor \frac{\gamma Pe}{Q}\rceil -u\right]}_{\gamma }=\lfloor \frac{\gamma Pe}{Q}\rceil -u\in \mathcal{R}$$
于是，纠错方式为：
$$[m{]}_P=\left({\left[\gamma \cdot (m+Pr)+\lfloor \frac{\gamma Pe}{Q}\rceil -u\right]}_P-{\left[\lfloor \frac{\gamma Pe}{Q}\rceil -u\right]}_{\gamma }\right)\cdot [{\gamma }^{-1}{]}_P$$

不过，[BEHZ16] 的这个方法只能缓解，并没有根本地解决 $Q$-overflow 的问题。而 [HPS19] 的方法可以完全移除它。

Retrieve the Overflow

[HPS19] 采取浮点指令，直接计算 $u$ 的值（精度受限的），
$$\begin{array}{rl}u& =\lfloor \frac{{\sum }_i[a\cdot {\tilde{q}}_i{]}_{q_i}\cdot q_i^{\ast }}{Q}\rceil =\lfloor \sum _{i=1}^k\frac{[a\cdot {\tilde{q}}_i{]}_{q_i}}{q_i}\rceil \end{array}$$
于是 $[a{]}_Q=({\sum }_i[a\cdot {\tilde{q}}_i{]}_{q_i}\cdot q_i^{\ast })-u\cdot Q$，纠错方式为：
$$[[a{]}_Q{]}_P=\text{FastBaseExt}(a,Q,P)-u\cdot [Q{]}_P$$

具体步骤：预计算 $[q_i^{\ast }{]}_{p_j},\forall i\in [k],\forall j\in [l]$，预计算 $[{\tilde{q}}_i{]}_{q_i},\forall i\in [k]$，预计算 $[Q{]}_{p_j},\forall j\in [l]$

1. 输入 $[a{]}_Q$ 的 RNS 表示 $(a_1,\cdots ,a_k)$，其中 $a_i=[a{]}_{q_i}$
2. 使用单精度整数指令，计算 $y_i=[a_i\cdot {\tilde{q}}_i{]}_{q_i}$
3. 使用单精度浮点指令，计算 $z_i=y_i/q_i$
4. 计算出 $u=\lfloor {\sum }_i{z}_i\rceil \in {\mathbb{Z}}_k$
5. 在 $Q$ 的 RNS 下，计算 $x_i=a_i\cdot [{\tilde{q}}_i{]}_{q_i}(\mathrm{mod}{q}_i)$
6. 在 $P$ 的 RNS 下，计算 $A_j^{\prime }={\sum }_i{x}_i\cdot [q_i^{\ast }{]}_{p_j}(\mathrm{mod}{p}_j)$
7. 纠正错误，$A_j=A_j^{\prime }-u\cdot [Q{]}_{p_j}$
8. 输出 [ a ] P = { A 1 , ⋯   , A l } [a]_{P} = \{A_1,\cdots,A_l\} [a]P​={A1​,⋯,Al​}，易知 $[a{]}_Q\cup [a{]}_P=[a{]}_{PQ}$

因为浮点数精度是有限的，因此实际计算出的数值为 $z_i^{\ast }=z_i+{ϵ}_i$，最终得到 $u^{\ast }=\lfloor {\sum }_i{z}_i^{\ast }\rceil$，总噪声是 $ϵ={\sum }_i{ϵ}_i$，使用 IEEE-754 double 那么有 $ϵ<k\cdot 2^{-53}$。我们定义 $\mathbb{Z}+[0.5-ϵ,0.5+ϵ]$ 是 possible-error region，一旦 ${\sum }_i{z}_i^{\ast }$ 落入这个区间，就应当采取高精度算术。不过，即使忽略它也影响不大，仅仅对噪声增长有一个极小的贡献。

Modulus-Switching and Scaling in RNS

Simple Reduction

输入 $x\in {\mathbb{Z}}_{PQ}$ 的 RNS 表示，记为 $(x_1,\cdots ,x_k,x_1^{\prime },\cdots ,x_l^{\prime })$，分别对应到 $Q={\prod }_i{q}_i$ 和 $P={\prod }_j{p}_j$

RNS 下的模约减：为了计算 $x(\mathrm{mod}Q)$，简单删除 $P$ 的分量，输出 $[x{]}_Q=(x_1,\cdots ,x_k)$

RNS 下的整除法：假设 $P|x$（易知 $x_j^{\prime }=0$），为了计算 $x/P$，预计算 $[P{]}_{q_i}$，在线计算 $[x/P{]}_Q=([x_1\cdot P{]}_{q_1},\cdots ,[x_k\cdot P{]}_{q_k})$

注意 RNS 系统不是数位系统（positional system），不能计算 $\mathbb{Z}$ 上的带余除法，也不能执行比较和舍入运算。因此，对于 BGV、BFV 中的某些必要运算（BGV 模切换、BFV 乘法缩放、秘钥切换、解密），需要设计特殊的解决方案。

Modulus-Switching for BGV

[GHS12] 给出了 BGV 的 Double-CRT 实现，对于 $t=2$ 平凡明文模数，因为 $q_i=1(\mathrm{mod}t)$ 导致实现简单。根据数论，

• $a\equiv b(\mathrm{mod}q)\to ka\equiv kb(\mathrm{mod}kq)$
• $a\equiv b(\mathrm{mod}q)\to a/d\equiv b/d(\mathrm{mod}q/d),d=\gcd (a,b,q)$
• $a\equiv b(\mathrm{mod}q),d\mid q\to a\equiv b(\mathrm{mod}d)$
• $a\equiv b(\mathrm{mod}{m}_i)\to a\equiv b(\mathrm{mod}lcm(m_i))$

对于一般的明文模数 $t$，令它是大素数（例如 $t=2^{16}+1$），给定密文 $c\in {\mathcal{R}}_{Q_k}^2$，我们计算特殊的 $c^{†}\in {\mathcal{R}}^2$（系数在 $\mathbb{Z}$ 上），满足

• 解密条件：$c^{†}\equiv c\cdot q_k(\mathrm{mod}t)$，

  LSD编码，因为 $c\cdot s\equiv m+te(\mathrm{mod}{Q}_k)$，假如小噪声 $m+te$ 不回绕 $Q_{k-1}$，从而 $[cs{]}_{Q_k}=[cs{]}_{Q_{k-1}}$ 就是 $m+te\in {\mathbb{Z}}^N$ 的精确值，进而得到 $[[cs{]}_{Q_{k-1}}{]}_t=[m+te{]}_t=[m{]}_t$

  假如噪声 $q_k(m+te)$ 不回绕 $Q_k$，那么 $[[c^{†}s{]}_{Q_k}{]}_t=[q_k(m+te){]}_t=[q_{k}m{]}_t$

• 噪声条件：$\delta =c^{†}-c$ 的范数较小

• 整除条件：$q_k\mid c^{†}$，注意 $\mathbb{Z}$ 上的整除恰好是 ${\mathbb{Z}}_{Q_{k-1}}$ 上的乘以逆元，

  于是 $c^{\prime }=c^{†}/q_k$ 的系数落在 $[-Q_{k-1}/2,Q_{k-1})$ 内，并且满足 $[c^{\prime }s{]}_{Q_{k-1}}=[q_k^{-1}{c}^{†}s{]}_{Q_{k-1}}=[cs{]}_{Q_{k-1}}$，从而 $c^{\prime }$ 是 $m$ 的密文

我们希望先计算出小差距 $\delta \equiv (q_k-1)\cdot c(\mathrm{mod}t)$，然后再求出 $c^{†}$，最后计算出 $c^{\prime }=c^{†}/q_k$，但是输入的 RNS 表示中不存在 $[c{]}_t$，导致 $\delta$ 难以计算。[GHS12] 转而计算密文：
$$\hat{c}=[q_k{]}_t\cdot c(\mathrm{mod}{Q}_k)$$
它加密了扭曲的消息 $[q_k{]}_t\cdot m$（对于 $t=2$ 特殊情况，恰好不扭转），寻找 $c^{†}$ 的条件改变为：

• 解密条件：$c^{†}\equiv \hat{c}(\mathrm{mod}t)$，它使得 $[[c^{†}s{]}_{Q_k}{]}_t=[q_{k}m{]}_t$
• 噪声条件：$\delta =c^{†}-\hat{c}$，注意这儿的变化导致 $\delta \equiv 0(\mathrm{mod}t)$
• 整除条件：$q_k\mid c^{†}$，计算出 $c^{\prime }=c^{†}/q_k$ 它满足 $[[c^{\prime }s{]}_{Q_{k-1}}{]}_t=[q_{k}m{]}_t$（似乎不太对）

此时的 $\delta$ 容易计算，算法如下：

1. 输入 $c(\mathrm{mod}{Q}_k)$ 的 RNS 表示（加密了 $[m{]}_t$）
2. 先计算 $\hat{c}=[q_k{]}_t\cdot c$ 的 RNS 表示，然后计算 $[\hat{c}{]}_{q_k}$ 的系数表示 $\bar{c}$
3. 我们计算差距 $\delta \in [-q_{k}t/2.q_{k}t/2{)}^N$，使得它满足 $\delta \equiv 0(\mathrm{mod}t)$ 以及 $\delta \equiv -\bar{c}(\mathrm{mod}{q}_k)$
4. 计算出 $c^{†}=\hat{c}+\delta$，易知 $c^{†}\equiv \hat{c}(\mathrm{mod}t)$ 以及 $c^{†}\equiv 0(\mathrm{mod}{q}_k)$
5. 最后计算整除 $c^{\prime }=c^{†}/q_k(\mathrm{mod}{Q}_{k-1})$，通过各分量乘以逆元 $[q_k^{-1}{]}_{q_i},\forall i\le k-1$
6. 输出 $c^{\prime }(\mathrm{mod}{Q}_{k-1})$ 的 RNS 表示（加密了 $[q_{k}m{]}_t$）

由于每次模切换都会扭曲消息，因此我们需要实时地追踪它，在同态加法/乘法时也需要调整这个扭曲因子。

Scaling for BFV

[HPS19] 给出了 BFV 的两种缩放程序，前者可用于解密，后者用于 GHS 秘钥切换。

Simple scaling

输入：$x\in {\mathbb{Z}}_Q$ 的 RNS 表示 $(x_1,\cdots ,x_k)$，任意的正整数 $t$（单精度整数）

输出：$y=\lfloor t/Q\cdot x\rceil \in {\mathbb{Z}}_t$

类似 CRT Basis Extension 的思路，将 $[x{]}_Q$ 重建为 $x$，观察提取出可预计算的部分，
$$\begin{array}{rl}y& =\lfloor \frac{t}{Q}\cdot x\rceil =\lfloor \frac{t}{Q}\cdot \sum _{i=1}^k{x}_i\cdot q_i^{\ast }\cdot {\tilde{q}}_i-u\cdot t\rceil \\ & =\lfloor \sum _{i=1}^k{x}_i\cdot \left(\frac{t}{q_i}\cdot {\tilde{q}}_i\right)\rceil -u\cdot t\end{array}$$
我们预计算其中的常数，分为整数和小数两部分，
$$\frac{t{\tilde{q}}_i}{q_i}={\omega }_i+{\theta }_i,{\omega }_i\in {\mathbb{Z}}_t,{\theta }_i\in [-0.5,0.5)$$
缩放步骤为：

1. 使用单精度整数指令，计算 $w=[{\sum }_i{x}_i\cdot {\omega }_i{]}_t$
2. 使用单精度浮点指令，计算 $v=\lfloor {\sum }_i{x}_i\cdot {\theta }_i\rceil \in {\mathbb{Z}}_k$
3. 合并为 $y=[w+v{]}_t$

同样的，实际计算时存在误差 ${\theta }_i^{\ast }={\theta }_i+{ϵ}_i,|{ϵ}_i|<2^{-53}$，累计为 $ϵ={\sum }_i{x}_i{ϵ}_i$，其中 $x_i=[x{]}_{q_i}\in [-q_i,q_i)$，于是 $|{ϵ}_j|<2^{-54}\cdot {\sum }_i{q}_i$，我们应当选取合适的 $k$ 和 $q_i$，使得 $|{ϵ}_j|<1/4$ 保证舍入是正确的。可能 IEEE-754 double 精度不够，需要使用不标准的 C/C++ long double 或者高精度算术。

Complex scaling

输入：$x\in {\mathbb{Z}}_{PQ}$ 的 RNS 表示，某正整数 $t$，满足 $x\in [-PQ/2t,PQ/2t)$ 落在较小范围内

输出：$y=\lfloor t/Q\cdot x\rceil \in {\mathbb{Z}}_Q$

抽象地，这可以分为两步完成，

1. 利用 Simple scaling 过程，设置 $Q^{\prime }=PQ,t^{\prime }=tP$，获得 $y^{\prime }=\lfloor t^{\prime }/Q^{\prime }\cdot x\rceil =\lfloor t/Q\cdot x\rceil \in {\mathbb{Z}}_{tP}$，丢弃 $t$ 的部分（等价于简单取模）获得 $y^{\prime }=\lfloor t/Q\cdot x\rceil \in [-P/2,P/2)$（因为 $x$ 的范围小，$y^{\prime }$ 是不取模的结果）
2. 利用 RNS Basis Extension 过程，从 $[y^{\prime }{]}_P$ 扩展出 $[y^{\prime }{]}_{PQ}$，丢弃 $P$ 的部分，输出 $y=[y^{\prime }{]}_Q$

其中的 step 1 使用的 $t^{\prime }$ 是高精度数字，需要先做 RNS 分解，然后分别执行 Simple scaling 过程，不过我们实际上只需要 $[y^{\prime }{]}_P$ 而非 $[y^{\prime }{]}_{tP}$，并且 $P|\gcd (Q^{\prime },t^{\prime })$，其实存在更快的算法。

简记 $Q_i^{\ast }=Q/q_i=q_i^{\ast }P,P_j=Q/p_j=Q{p}_j^{\ast }$，计算 ${\tilde{Q}}_i=[(Q_i^{\ast }{)}^{-1}{]}_{q_i},{\tilde{P}}_j=[(P_j^{\ast }{)}^{-1}{]}_{p_j}$，简记 $x_i=[x{]}_{q_i},x_j^{\prime }=[x{]}_{p_j}$，那么
$$\begin{array}{rl}{y}^{\prime }& =\lfloor \frac{t^{\prime }}{Q^{\prime }}\cdot x\rceil =\lfloor \frac{t}{Q}\cdot \left(\sum _{i=1}^k{x}_i\cdot Q_i^{\ast }\cdot {\tilde{Q}}_i+\sum _{j=1}^l{x}_j^{\prime }\cdot P_j^{\ast }\cdot {\tilde{P}}_j\right)-u\cdot tP\rceil \\ & =\lfloor \sum _{i=1}^k{x}_i\cdot \left(\frac{t}{q_i}\cdot {\tilde{Q}}_{i}P\right)+\sum _{j=1}^l{x}_j^{\prime }\cdot \left(t\cdot {\tilde{P}}_j{p}_j^{\ast }\right)\rceil -u\cdot tP\end{array}$$
计算 $[y^{\prime }{]}_P$ 的 RNS 表示，
$$[y^{\prime }{]}_{p_j}={\left[\lfloor \sum _{i=1}^k{x}_i\cdot \left(\frac{t}{q_i}\cdot {\tilde{Q}}_{i}P\right)\rceil +x_j^{\prime }\cdot \left(t\cdot {\tilde{P}}_j{p}_j^{\ast }\right)\right]}_{p_j}$$
需要预计算
$$\frac{t{\tilde{Q}}_{i}P}{q_i}={\omega }_i+{\theta }_i,{\omega }_i\in {\mathbb{Z}}_P,{\theta }_i\in [-0.5,0.5)$$
继续将 $w_i$ 分解为单精度整数 $w_{ij}:=[w_i{]}_{p_j},\forall i\in [k],\forall j\in [l]$，另外预计算 ${\lambda }_j:=[t{\tilde{P}}_j{p}_j^{\ast }{]}_{p_j},\forall j\in [l]$

输入 $(x_1,\cdots ,x_k,x_1^{\prime },\cdots ,x_l^{\prime })$，则 step 1 的步骤为：

1. 使用浮点数指令，计算 $v=\lfloor {\sum }_i{x}_i{\theta }_i\rceil \in {\mathbb{Z}}_k$，这个是共用的
2. 使用整数指令，计算 $w_j=[{\sum }_i{x}_i{w}_{ij}+{\lambda }_j{x}_j^{\prime }{]}_{p_j}$，第二项累加被$(\mathrm{mod}{p}_j)$ 基本消除
3. 合并为 $[y^{\prime }{]}_{p_j}=[v+w_j{]}_{p_j}$

Scaling between Arbitrary RNS Bases

[KPZ21] 给出了另一种 Simple scaling 的实现，

输入：$x\in {\mathbb{Z}}_Q$ 的 RNS 表示，与 $Q$ 互素的多精度整数 $P$

输出：$\lfloor P/Q\cdot [x{]}_Q\rceil (\mathrm{mod}P)$

在 [BEHZ16] 中，它将舍入运算可以写作整除法，
$$\lfloor \frac{P}{Q}\cdot [x{]}_Q\rceil =\frac{P\cdot [x{]}_Q-[Px{]}_Q}{Q}$$
因此它等价于在 ${\mathbb{Z}}_P$ 中乘以逆元，
$${\left[\lfloor \frac{P}{Q}\cdot [x{]}_Q\rceil \right]}_P=[-[Px{]}_Q{]}_P\cdot [Q^{-1}{]}_P$$
根据 CRT 组合公式，
$$[Px{]}_Q=\sum _{i=1}^k[Px{]}_{q_i}\cdot [{\tilde{q}}_i{]}_{q_i}\cdot q_i^{\ast }-u\cdot Q$$
因此最终结果的 RNS 表示的计算公式为：
$$[-[Px{]}_Q{]}_{p_j}\cdot [Q^{-1}{]}_{p_j}={\left[u-\sum _{i=1}^k[Px{]}_{q_i}\cdot [{\tilde{q}}_i{]}_{q_i}\cdot q_i^{-1}\right]}_{p_j}$$
其中 $\Vert u{\Vert }_{\infty }\le k/2$，可以使用 [HPS19] 的浮点数算法来精确计算。

Key-Switch in RNS

输入 $s_A$ 加密的密文 $c{t}_A=(c_0,c_1)$，给定 $s_B$ 加密的 $s_A$ 的密文 $k{s}_{A\to B}$，
$$k{s}_{A\to B}:=(k{s}_0=[a\cdot s_B+te+s_A{]}_Q,k{s}_1=[-a{]}_Q)$$
秘钥切换就是同态线性解密，抽象描述为 $c_0+c_1\cdot E(s_A)$，具体地：
$$\begin{array}{rl}c{t}_B& =c_0\cdot (1,0)+c_1\cdot k{s}_{A\to B}\\ & =([c_0+c_1\cdot k{s}_0{]}_Q,[c_1\cdot k{s}_1{]}_Q)\end{array}$$
重现性化是一种特殊的秘钥切换：输入密文 $ct=(c_0,c_1,c_2)$，给定 $s$ 加密的 $s^2$ 的密文 $rlk$，
$$rlk:=(rl{k}_0=[a\cdot s+te+s^2{]}_Q,rl{k}_1=[-a{]}_Q)$$
由于 $(0,1)$ 就是 $s$ 自身的密文，重现性化的抽象描述为 $c_0+c_1\cdot E(s)+c_2\cdot E(s^2)$，具体地：
$$\begin{array}{rl}c{t}^{\prime }& =c_0\cdot (1,0)+c_1\cdot (0,1)+c_2\cdot rlk\\ & =([c_0+c_2\cdot rl{k}_0{]}_Q,[c_1+c_2\cdot rl{k}_1])\end{array}$$
但是 $c_1$ 的规模相对于密文模数 $Q$ 过大，导致秘钥切换中 $k{s}_{A\to B}$ 的噪声被大幅增长。有两种方法来控制噪声，分别是 [BV11] 和 [GHS12]，以及它们的混合。

Brakerski-Vaikuntanathan

[BV11] 采取数字分解技术，选取 radix-$w$，数位是 $l=\lfloor {\log }_{w}Q\rceil +1$

• 分解：$D_{w,Q}(a)=([a{]}_w,[\lfloor a/w\rceil {]}_w,\cdots ,[\lfloor a/w^{l-1}\rceil {]}_w)\in {\mathcal{R}}_w^l$，
• 幂次：$P_{w,Q}(a)=([a{]}_Q,[aw{]}_Q,\cdots ,[a{w}^l{]}_Q)\in {\mathcal{R}}_Q^l$
• 易知 $⟨D(a),P(b)⟩\equiv ab(\mathrm{mod}Q)$

因此，秘钥切换秘钥是：
$$k{s}_{A\to B}^{BV}:=(k{s}_0=[\vec{a}\cdot s_B+t\vec{e}+P_{w,Q}(s_A){]}_Q,k{s}_1=[-\vec{a}{]}_Q)\in {\mathcal{R}}_Q^{l\times 2}$$
秘钥切换程序是：
$$c{t}_B=([c_0+⟨D_{w,Q}(c_1),k{s}_0⟩{]}_Q,[⟨D_{w,Q}(c_1),k{s}_1⟩{]}_Q)$$
然而，RNS 系统不是数位系统，上述的 radix-$w$ 分解无法自然地执行。[BEHZ16] 直接使用 RNS 的各个余数作为元素的分解形式，设 $Q=q_1\cdots q_k$，简记 $q_i^{\ast }=Q/q_i,{\tilde{q}}_i=(q_i^{\ast }{)}^{-1}(\mathrm{mod}{q}_i)$

• 分解：$D_Q(a)=([a{\tilde{q}}_1{]}_{q_1},[a{\tilde{q}}_2{]}_{q_2},\cdots ,[a{\tilde{q}}_k{]}_{q_k})\in {\mathcal{R}}^k$
• 幂次：$P_Q(a)=([a{q}_1^{\ast }{]}_Q,[a{q}_2^{\ast }{]}_Q,\cdots ,[a{q}_k^{\ast }{]}_Q)\in {\mathcal{R}}_Q^k$
• 容易验证，它也满足 $⟨D(a),P(b)⟩\equiv ab(\mathrm{mod}Q)$

在 RNS 下，秘钥切换秘钥是：
$$k{s}_{A\to B}^{RNS-BV}:=(k{s}_0=[\vec{a}\cdot s_B+t\vec{e}+P_Q(s_A){]}_Q,k{s}_1=[-\vec{a}{]}_Q)\in {\mathcal{R}}_Q^{k\times 2}$$
秘钥切换程序是：
$$c{t}_B=([c_0+⟨D_Q(c_1),k{s}_0⟩{]}_Q,[⟨D_Q(c_1),k{s}_1⟩{]}_Q)$$
[HPS19] 进一步优化，修改为

• 分解：$D_Q(a)=([a{]}_{q_1},[a{]}_{q_2},\cdots ,[a{]}_{q_k})\in {\mathcal{R}}^k$
• 幂次：$P_Q(a)=([a{q}_1^{\ast }{\tilde{q}}_1{]}_Q,[a{q}_2^{\ast }{\tilde{q}}_2{]}_Q,\cdots ,[a{q}_k^{\ast }{\tilde{q}}_k{]}_Q)\in {\mathcal{R}}_Q^k$

因此 $[c_1{]}_Q$ 直接就是 $D(c_1)$，于是节约了一些数乘运算。

具体流程，以及对应的复杂度：

Gentry-Halevi-Smart

[GHS12] 使用临时扩展技术，选取足够大的 $P=p_1\cdots p_l\approx Q$

秘钥切换秘钥为：
$$k{s}_{A\to B}^{GHS}:=(k{s}_0=[a\cdot s_B+te+P{s}_A{]}_{PQ},k{s}_1=[-a{]}_{PQ})\in {\mathcal{R}}_{PQ}^2$$
秘钥切换程序是：

1. 先在 $PQ$ 下计算 $c_1\cdot E(s_A)$，
   $$c{t}_B^{\prime }=(c_0^{\prime }=[c_1\cdot k{s}_0{]}_{PQ},c_1^{\prime }=[c_1\cdot k{s}_1{]}_{PQ})$$

2. 然后计算 $c{t}_B^{\prime }$ 整除 $P$ 的差距（满足 $[\delta {]}_t=0$ 和 $[c{t}_B^{\prime }{]}_P=[\delta {]}_P$），
   $$\delta =({\delta }_0=t[-t^{-1}{c}_0^{\prime }{]}_P,{\delta }_1=t[-t^{-1}{c}_1^{\prime }{]}_P)\in {\mathcal{R}}_{PQ}^2$$

3. 将 $c{t}_B^{\prime }+\delta$ 从 $PQ$ 缩放到 $Q$（除以 $P$，而非简单取模），计算出
   $$c{t}_B=\left({\left[c_0+\frac{c_0^{\prime }+{\delta }_0}{P}\right]}_Q,{\left[c_1+\frac{c_1^{\prime }+{\delta }_1}{P}\right]}_Q\right)$$

在 RNS 下执行，

1. 将 $[c_1{]}_Q$ 利用 RNS Basis Extension 扩展到 $[[c_1{]}_Q+uQ{]}_P$，其中的 $\Vert u{\Vert }_{\infty }\le k/2$ 是 CRT 合成时的 $Q$-overflow
2. 计算 $[c_1{]}_{PQ}$ 和 $k{s}_{A\to B}^{GHS}$ 的乘积，得到 $[c{t}_B^{\prime }{]}_{PQ}$
3. 将 $[-t^{-1}c{t}_B^{\prime }{]}_P$ 利用 RNS Basis Extension 扩展到 $[[-t^{-1}c{t}_B^{\prime }{]}_P+u^{\prime }P{]}_Q$，其中 $\Vert u^{\prime }{\Vert }_{\infty }\le l/2$
4. 我们计算出了 $PQ$ 下差距的近似值 ${\delta }^{\prime }=\delta +t{u}^{\prime }P$，再利用 Madulus-Switching / Scaling，计算出 $[c{t}_B{]}_Q$

其中的 $u,u^{\prime }$ 可以通过 [BEHZ16] 和 [HPS19] 的技术来消除，但在这里它们都很小，仅对噪声增长有一个可忽略的贡献。

具体流程，以及对应的复杂度：

Hybrid

BV Key-Switch 的缺点是：密文扩张了 $l$ 倍，需要的 NTT 数量较多。

GHS Key-Switch 的缺点是：模数增大了 $P$ 倍，为了补偿安全损失，要么维度扩大两倍，要么乘法层数减少一半。

一般而言，混合方案的效率和噪声控制是表现更好的。使用一个相对较大的 radix-$w$，使得数位 $l=\lfloor {\log }_{w}Q\rceil +1$ 很小，以及一个较小规模的 $P\approx lw/2$，
$$k{s}_{A\to B}^{Hybrid}=([\vec{a}\cdot s_B+t\vec{e}+P\cdot P_{w,Q}(s_A){]}_{PQ},[-\vec{a}{]}_{PQ})$$
计算流程是：

1. 输入 $c{t}_A=(c_0,c_1)\in {\mathcal{R}}_Q^2$，分解 $c_1$ 为 $D_{w,Q}(c_1)\in {\mathcal{R}}^l$
2. 计算 $c{t}_B^{\prime }=([⟨D_{w,Q}(c_1),k{s}_0⟩{]}_{PQ},[⟨D_{w,Q}(c_1),k{s}_1⟩{]}_{PQ})$
3. 利用模切换将它除以 $P$ 缩放到 $Q$ 上，计算出 $c{t}_B=([c_0+(c_0^{\prime }+{\delta }_0)/P{]}_Q,[c_1+(c_1^{\prime }+{\delta }_1)/P{]}_Q)$

对于 RNS 系统，使用 [BEHZ16] 的类似分解，将 $Q$ 分为 $Q_0,\cdots ,Q_d$，每个 $Q_i$ 包含 $\alpha \approx k/d$ 个小素数，简记 $Q_i^{\ast }=Q/Q_i$，${\tilde{Q}}_i=[(Q_i^{\ast }{)}^{-1}{]}_{Q_i}$

分解函数就是 ${\tilde{D}}_Q(a)=([a{]}_{Q_1},\cdots ,[a{]}_{Q_d})\in {\mathcal{R}}^d$，幂次函数定义为
$${\tilde{P}}_Q(a)=\left({\left[s_B{Q}_i^{\ast }{\tilde{Q}}_i\right]}_Q,\cdots ,{\left[s_B{Q}_i^{\ast }{\tilde{Q}}_i\right]}_Q\right)\in {\mathcal{R}}_Q^d$$
那么，秘钥切换秘钥为：
$$k{s}_{A\to B}^{RNS-Hybrid}=([\vec{a}\cdot s_B+t\vec{e}+P\cdot {\tilde{P}}_Q(s_B){]}_{PQ},[-\vec{a}{]}_{PQ})$$
计算步骤就是 RNS-BV 和 RNS-GHS 的恰当组合，

1. 分解 $c_1$ 为 ${\tilde{D}}_Q(c_1)$，并扩展到 $PQ$
2. 在 $PQ$ 上计算出 $c{t}_B^{\prime }$
3. 缩放到 $Q$，再加上 $c_0$，得到 $c{t}_B$

具体流程，以及对应的复杂度：

Complexities and Size

GHS 选取：BFV 的 $k\approx l$，BGV 的 $k^{\prime }\approx l^{\prime }$

Hybrid 选取：BFV 的 $\alpha \approx k,d\alpha \approx l$，BGV 的 ${\alpha }^{\prime }\approx k^{\prime },d{\alpha }^{\prime }\approx l^{\prime }$

复杂度为：