FDFB with smaller noise

参考文献：

[CZB+22] Clet P E, Zuber M, Boudguiga A, et al. Putting up the swiss army knife of homomorphic calculations by means of TFHE functional bootstrapping[J]. Cryptology ePrint Archive, 2022.
[MHW+23] Ma S, Huang T, Wang A, et al. Fast and accurate: efficient full-domain functional bootstrap and digit decomposition for homomorphic computation[J]. Cryptology ePrint Archive, 2023.
消除 TFHE 的限制：WoP-GenPBS-CSDN博客
Large-Precision Sign using PBS-CSDN博客
Full Domain PBS - CSDN博客

文章目录

Types of FDFB
FDFB
- FDFB-Compress
- FDFB-CancelSign
- FDFB-Select
- FDFB-SelectAlt
- WoP-PBS1-Refine
- FDFB-BFVMult
Homomorghic Decomposition
- HomDecomp-Reduce
- HomDecomp-FDFB
Analysis

Types of FDFB

[MHW+23] 将已有的 Full Domain Functional Bootstrap 分为了三类，

Type-SelectMSB
- 思路是使用 MSB 去挑选两个反循环的 LUT，组合为任意函数
- [CLOT21] 使用 BFV-Mul 构建 CMux Gate，挑选两个 LUT 执行 PBS 的结果
- [KS22] 使用 Power-of-Base Scale-Mul 构建 ACC-Builder，从两个公开的 LUT 中挑选出一个去执行 PBS
Type-HalfRange
- 思路是将消息限制到一半的空间，使用反循环的 LUT 去计算
- [CLOT21] 强行提升密文模数，使用 BFV-Mul 消除随机 MSB 的影响
- [LMP22] 强行提升密文模数，使用 PBS 消除随机的 MSB
Type-Split
- 思路是将任意函数拆分为两个函数的加和，每个函数分别用反循环 LUT 计算
- [CZB+22] 提出了 pseudo-odd, pseudo-even 函数，它们都可以用两个反循环 LUT 迭代计算，而任意函数可以表示为 $\frac{f(x)+f(-x-1)}{2} + \frac{f(x)-f(-x-1)}{2}$ ，前者是伪偶的，后者是伪奇的

一些符号，

多种密文： $L W E, R L W E, R L W E^{'}, RGS W$ ，其中 $R L W E^{'}$ 是强线性的
模数变换： $M o d Do w n, M o d U p, M o d Sw i t c h$ ，其中 $Do w n, U p$ 要求整除性
自举过程： $B oo t, B oo tR a w$ ，后者表示新鲜提取的 LWE 密文（没有执行 KS 和 MS）
不同噪声： $e_{rnd}, e_{ms}, e_{ks}, e_{mult}, e_{acc}, e_{boot}, e_{com}$ ，分别代表了 MSB 编码/解码、模切换、密钥切换/密文打包、FV乘积、盲旋转、完整自举、自举提取出的 LWE 密文做 KS 和 MS 的噪声，对应的标准差是 $\sigma_{X}$
自举噪声的启发式上界：计算 $bnd=\sqrt{2}\cdot \text{erfc}^{-1}(2^{-{32}}) \approx 6.338$ ，设置 $\beta=bnd \cdot \sigma_{boot}$
LWE 密文模数 $q = 2 N$ ，明文模数 $p$ ，相位 $\cdot m'+e$ ，保证 $∣ e ∣ < q /2 p$ ，任何运算之前总是 $c t + (0, q /2 p)$ 保证噪声的范围 $[0, q / p)$ ，并且假设所有算法输入的 LWE 密文噪声上界是 $\beta$

FDFB

[MHW+23] 提出了多种 FDFB 算法，主要是改进了噪声增长。虽然 PBS 的调用次数不变甚至增多，但是数字分解可以更粗糙，总体的计算效率略有提升。

FDFB-Compress

此算法遵循 Type-HalfRange 策略，不再是强行提升模数，而是使用 PBS 将范围 $[- q /2, q /2)$ 的原始 coded message 压缩到范围 $[- q /4, q /4)$ ，从而再用一次 PBS 计算任意函数。

用到的反循环函数是：

在这里插入图片描述

算法为：

在这里插入图片描述

需要注意，执行 $f_C$ 需要自举噪声的规模 $2\beta$ 不超过 $q /2 p$

FDFB-CancelSign

此算法遵循 Type-SelectMSB 策略，先强行提升模数，出现随机的 $\beta$ 最高位，直接 PBS 的结果中存在随机 $(-1)^{\beta}$ 影响。不是使用 BFV-Mult 去消除，而是将 LWE 密文转化为 ACC，再使用 PBS 消除这个因子。

用到的反循环函数是：

在这里插入图片描述

算法为：

在这里插入图片描述

这里的输入 LWE 的密文模数是 $q /2$ ，因此也要求 $2\beta<q/2p$

FDFB-Select

此算法遵循 Type-SelectMSB 策略，不再提升密文模数，它将消息 $\cdot m'+e$ 的最高比特视为 $\beta$ ，把任意函数按照 $\beta$ 分割为两个 sub-LUTs，分别执行 PBS 之后将计算结果打包为新的 ACC。接着 PBS 提取出 $\beta$ ，再次执行 PBS 挑选出最终结果。

用到的反循环函数是：

在这里插入图片描述

算法为：

在这里插入图片描述

前三次 PBS 都是对于同一个 $c t$ 执行的，因此可以使用 [CIM19] 的 Mult-Output PBS 合并计算，代价是 ACC 乘以 TV 导致噪声增长。共计 $4$ 个 PBS，合并为 $2$ 个。

FDFB-SelectAlt

此算法遵循 Type-SelectMSB 策略，不是直接对 $f_{pos}$ 和 $f_{neg}$ 执行 PBS，而是对 $f_{sum}=(f_{neg}+f_{pos})/2$ 以及 $f_{diff}=(f_{neg}-f_{pos})/2$ 自举，然后根据 $\beta$ 对 $f_{diff}$ 的自举结果形成的 ACC 执行 PBS，从而确定两者是相加还是作差。

算法为：

在这里插入图片描述

前两个 PBS 可以合并，最后一个 PBS 依赖于它们的结果。合并后是 $2$ 个 PBS。

WoP-PBS1-Refine

此算法遵循 Type-SelectMSB 策略，先强行提升模数，再使用 BFV-Mult 消除随机因子 $(-1)^\beta$ 的影响。这实际就是 [CLOT21] 的第一种 WoP-PBS 算法，只不过将 LWE 密文转化为 RLWE 密文再计算 BFV-Mult 的时候，其相位的非常数项都只是很小的噪声，因此 [MHW+23] 给出了一个更紧的噪声估计，方差缩小了 $N$ 因子。

用到的反循环函数是：

在这里插入图片描述

算法为：

在这里插入图片描述

使用 Mult-Output PBS 加速，这里的 $2$ 个 PBS 被合并为 $1$ 个。

FDFB-BFVMult

此算法遵循 Type-SelectMSB 策略，将任意函数拆分为 $f_{pos} + \beta(f_{neg}-f_{pos})$ ，自举出两部分多项式的结果后，使用 BFV-Mult 将它们组合起来。这是对 [CLOT21] 第二种 WoP-PBS 算法中的 $(1-\beta)f_{pos} + \beta f_{neg}$ 的改良。

用到的反循环函数是：

在这里插入图片描述

算法为：

在这里插入图片描述

使用 Mult-Output PBS 加速，这 $3$ 个 PBS 也被合并成 $1$ 个。由于只需要一次 BFV-Mult，它的噪声比 [CLOT21] 的更低。

Homomorghic Decomposition

[MHW+23] 也给出了两个同态数字分解算法，两者都支持 CKKS 密文的分解。而 [LMP22] 的第一种 Floor 算法要求输入 LWE 密文的消息和噪声之间存在 gap（不兼容 CKKS 密文），从而密文作差时的噪声不会影响高位数据；第二种 Floor 算法需要额外的一次 PBS 去消除这个约束，但是要求自举噪声具有更小的规模。[MHW+23] 的算法消除了这些限制。