参考文献：

1. [KDE+23] Kim A, Deryabin M, Eom J, et al. General bootstrapping approach for RLWE-based homomorphic encryption[J]. IEEE Transactions on Computers, 2023.
2. [BCC+22] Bae Y, Cheon J H, Cho W, et al. Meta-bts: Bootstrap** precision beyond the limit[C]//Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security. 2022: 223-234.

BTS for CKKS

目前存在多种 CKKS 自举算法，它们的目标是将密文 $ct(s)=m\in R_q$ 转换为 $c{t}^{\prime }(s)=m^{\prime }\in R_{Q^{\prime }}$，使得 $Q^{\prime }>q$ 以及 $\Vert m-m^{\prime }{\Vert }_{\infty }$ 误差很小。假设 $q|Q$，那么易知 $ct(s)=m+qI\in R_Q$，从而一个关键运算就是同态模约简。注意 CKKS 自举的目标是提升密文模数，而非减小噪声规模；事实上 CKKS 自举会引入额外的噪声，造成一定的精度损失。

• [CHKKS18] 第一次给出了 CKKS 自举算法，它先用三角函数近似模约简，接着再用 Taylor 级数去近似三角函数，框架为：

  1. StC, 将消息从明文槽切换到系数上，为模数提升做准备
  2. ModRaise, 执行模数提升，获得 $m+qI\in R_Q$
  3. CtS, 将消息从系数切换回明文槽，为模约简做准备
  4. EvalMod, 使用多项式近似模约简函数，获得 $m^{\prime }\in R_{Q^{\prime }}$

• [CCS19] 和 [HK20] 采用相同的思路，但是将 Taylor 级数替换为了 Chebyshev 插值，降低了近似多项式的度数，所需的乘法深度降低

• [LLK+21] 和 [JM22] 将三角函数近似替换为 Inverse Sine 以及 Sine 级数，降低了三角函数的近似误差

• [JM20] 和 [LLK+22] 直接对模约简做多项式近似，分别使用 Lagrange 插值以及最小二乘法，消除了中间的三角函数导致的近似误差，从而提高自举的精度

• [BMTH21] 提出了 double-hoisting BSGS 的矩阵乘算法，使得 RNS-CKKS 的 StC 和 CtS 的速度更快

• [KDE+23] 使用 FHEW/TFHE 自举 CKKS，可以获得较高的自举精度。然而 FHEW/TFHE 很难兼容批处理技术，因此对于大规模数据的自举效率很低。

在很多应用场景中，需要计算乘法深度很大的高精度的浮点数运算，因此高精度的 CKKS 自举算法是必要的。然而，为了更高的自举精度，就要减小噪声和模数的比值，出于安全考量就必须提高环的维度。为了达到 100 比特的精度，最先进的 [LLK+22] 需要 $N=2^{17}$，并且明文是稀疏的；[KDE+23] 可以在较小规模的参数下实现较高的自举精度，但是计算性能很差。

Meta-BTS

[BCC+22] 提出可以将 BTS 作为黑盒，首先对输入的密文 $ct(s)=m\in R_q$ 做一次自举来提升模数 $c{t}^{\prime }(s)=m+e\in R_{Q^{\prime }}$，可以计算出 $[c{t}^{\prime }(s){]}_q-ct(s)=e\in R_q$，通过对 Bootstrapping error 再迭代 $k-1$ 次自举以消除它，从而提高自举的精度。在 OpenFHE 中提供了 $k=2$ 的实现，可以将自举精度加倍。

首先我们需要定义 BTS 的精度：令 CKKS 加密的消息 $\vec{m}$ 的范数上界是 $2^r$，假设自举程序的噪声 $\vec{e}$ 的范数上界是 $2^{-n}$，那么这之间的 $r+n$ 比特就是准确值。我们称 $r=0$ 的 BTS 是标准的，也就是 $\vec{m}$ 是范围 $(-1,1)$ 的带符号尾数，自举后的有效位数是 $n$ 比特。指数信息是额外的明文标记，并不是缩放因子 $\Delta >2^n$，后者将有限精度的尾数变成一个大整数。

BTS Standardization：假设某个 BTS 是非标准的，缩放因子 $\Delta$，输入界 $2^r$，自举精度 $r+n$，那么只需要调整为 ${\Delta }^{\prime }=\Delta \cdot 2^r$ 用于消息编码，那么新的 BTS 就是标准的，且自举精度不变。

现在，我们已经有了一个标准 BTS 算法，可以用它构造出更高精度的 BTS，算法如下：

基础的 $BT{S}^{(1)}$ 是标准的，并且它的自举精度 $n$ 是已知的。我们不是输入 $ct(m,q)$，而是输入 Level 更高的密文 $ct(2^{n}m,2^{n}q)$，其中 $\Vert m{\Vert }_{\infty }<1$，然后对缩放 $2^n$ 后的密文执行 BTS 接着乘以 $2^n$ 得到 $c{t}_3$，这些操作使得我们可以获得加密了放大 $2^n$ 倍的自举噪声 $2^{-1}{e}_1$ 的密文 $c{t}_5$，其中压倒性概率 $\Vert e_1{\Vert }_{\infty }<1$，假设舍入噪声很小 $\Vert 2^n{e}_{rs}+e_1{\Vert }_{\infty }<1$，于是我们就可以对 $c{t}_5$ 应用 $BT{S}^{(1)}$ 提升它的模数到和 $c{t}_3$ 相同，从而消除了噪声 $e_1$（但添加了第二次 BTS 的噪声 $2^{-n}{e}_2$）。

算法执行过程中密文的变化：

容易将上述的 BTS 推广到任意的 $k\ge 2$，得到精度为 $kn$ 的自举算法。我们利用 $BT{S}^{(1)}$ 搭建出的 $BT{S}^{(k)}$ 作为黑盒去自举密文，再用 $BT{S}^{(1)}$ 对前者的自举噪声继续自举以消除它，就可以搭建出精度更高的 $BT{S}^{(k+1)}$，

注意到输入密文的模数从 $q$ 提升到了 $2^{kn}\cdot q\le Q_{rem}$，因此固定参数的某个 $BT{S}^{(1)}$ 它的迭代次数 $k$ 存在上界。假设基础的 BTS 性能是 $PER{F}_{BT{S}^{(1)}}=(n,Q_{rem}/q,t)$，那么迭代 $k$ 次之后的性能为：
$$PER{F}_{BT{S}^{(k)}}=\left(kn,\frac{Q_{rem}}{2^{(k-1)n}q},kt\right)$$
迭代次数越多，那么自举精度越高，同时剩余的乘法深度也就越小。当自举后的乘法深度为 $1$ 时就达到最高的自举精度，设置缩放因子为 $\Delta =Q_{rem}/2^{(k-1)n}q$，三元秘密的重量为 $h$，则同态乘法的精度损失为 $\log O(\sqrt{Nh})$，为了在无界运算中保持至少 $kn$ 比特的精度，我们列出如下的不等式：
$$kn\le \Delta -\log \sqrt{Nh}$$
最终可以得到 Meta-BTS 的自举精度上界：

与其他 CKKS-BTS 对比，Meta-BTS 可以将某个固定精度的自举算法转化为更高精度的自举，因此所需的参数规模更小。为达到相同的自举精度 $n$，可以将 $n$ 切分为 $n/k$ 的迭代，执行效率会更高。