Amortized Bootstrapping of LWE：使用 BFV 打包处理

参考文献：

1. [AP13] Alperin-Sheriff J, Peikert C. Practical bootstrapping in quasilinear time[C]//Annual Cryptology Conference. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013: 1-20.
2. [MS18] Micciancio D, Sorrell J. Ring packing and amortized FHEW bootstrapping[J]. Cryptology ePrint Archive, 2018.
3. [CHKKS19] Cheon J H, Han K, Kim A, et al. A full RNS variant of approximate homomorphic encryption[C]//Selected Areas in Cryptography–SAC 2018: 25th International Conference, Calgary, AB, Canada, August 15–17, 2018, Revised Selected Papers 25. Springer International Publishing, 2019: 347-368.
4. [CDKS21] Chen H, Dai W, Kim M, et al. Efficient homomorphic conversion between (ring) LWE ciphertexts[C]//International Conference on Applied Cryptography and Network Security. Cham: Springer International Publishing, 2021: 460-479.
5. [INZ21] Iliashenko I, Negre C, Zucca V. Integer functions suitable for homomorphic encryption over finite fields[C]//Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography. 2021: 1-10.
6. [LW23] Liu Z, Wang Y. Amortized Functional Bootstrapping in less than 7ms, with $\tilde {O}(1) $ polynomial multiplications[J]. Cryptology ePrint Archive, 2023.
7. Amortized FHEW bootstrapping
8. Chimera：混合的 RLWE-FHE 方案
9. Pegasus：CKKS 和 TFHE 的混合

Interpolation over finite fields

对于 $p$ 次插值多项式，使用通用的 Paterson-Stockmeyer 多项式求值算法，复杂度为 $\sqrt{2p}+O(\log p)$

[INZ21] 利用素域的性质，给出了某些特殊函数的更高效的插值多项式：取模、判断幂次、汉明重量、模二、比较。

Lemma

奇素数 $p\ge 3$，素域 ${\mathbb{Z}}_p$，

• 对于任意的 $e\in [0,p?2]$，都有
  $$\sum _{a\in GF(p)}{a}^e=0(\mathrm{mod}p)$$

• 对于任意的 $a,b\in {\mathbb{Z}}_p$，都有
  $$(a?b{)}^{p?1}=\sum _{i=0}^{p?1}{a}^i{b}^{p?1?i}(\mathrm{mod}p)$$

• 根据 Fermat Little Theorem，等性检测的二元多项式：
  $$EQ(x,y)=1?(x?y{)}^{p?1}$$

• 任意的函数 $f:{\mathbb{Z}}_p^n\to {\mathbb{Z}}_p$ 都可以唯一表示为多元多项式 $P_f(X_1,?,X_n)$，各个变元的次数不超过 $p?1$，具体的插值多项式为
  $$P_f(X_1,?,X_n)=\sum _{\vec{a}\in {\mathbb{Z}}_p^n}f(\vec{a})\prod _{i=1}^n(1?(X_i?a_i{)}^{p?1})$$

Unary functions

设置 $n=1$，那么任意的 $f:{\mathbb{Z}}_p\to {\mathbb{Z}}_p$ 可以插值为：
$$\begin{array}{rl}{P}_f(X)& =\sum _{i=0}^{p?1}f(a)?(1?(X?a{)}^{p?1})\\ & =f(0)?\sum _{i=1}^{p?1}\left(\sum _{a=0}^{p?1}f(a)a^{p?1?i}\right)?X^i\end{array}$$
我们希望 $P_f(X)$ 越稀疏越好。[INZ21] 观察到，假设 ${\zeta }_k$ 是本原单位根，满足 $k\mid p?1$，将 ${\mathbb{Z}}_p^{?}$ 分为 $k$ 个子集 { S 0 , ? ? , S k ? 1 } \{S_0,\cdots,S_{k-1}\} {S0?,?,Sk?1?} 的不交并，
$$S_j={\zeta }_k^j{S}_0,?0\le j<k$$
那么，

• 对于那些 $k\mid i$ 的系数索引，
  $$\sum _{a\in S_0}{a}^{p?1?i}=0$$

• 假如 $f$ 在每个 $S_j$ 上都是常数，
  $$f(a)=c_j,?a\in S_j$$
  那么 $P_f(X)$ 的所有 $X^i,k\mid i$ 的系数都为零

Batched LWE ciphertext bootstrapping

[MS18] 最先给出了 FHEW 的批处理自举，均摊成本 $O(3^{?}?n^{1/?}),??>0$，然而结构复杂，没有给出具体实现。之后有若干工作，也给出了批处理的 LWE 自举算法。

[LW23] 直接使用 BFV 的 SIMD 性质（并非 ACC + LUT）来批量自举 LWE 密文。简单来说：

1. 输入若干 LWE 密文，堆叠为矩阵形式 $(A,b)$
2. 采取 Pegasus 的同态线性变换，在 BFV 的明文槽中解密出 $\vec{\mu }=b?As$
3. 将函数 $f$ 插值为多项式，同态计算出 $f(\vec{\mu })$，这是 Slot-Packing 打包的
4. 采取 Slot-to-Coeff 技术同态解码，此时 BFV 加密 $f(\vec{\mu })$ 的 Coeff-Packing
5. 使用 Extract 提取出 LWE 密文

最终，均摊成本是 $\tilde{O}(1)$ 多项式乘法。他们选取的参数下，均摊运行时间小于 $7$ 毫秒。

LWE 方案（MSD 编码）：

• 维度 $n$：要求整除 $N$
• 密文模数 $q$
• 明文模数 $p$
• 私钥 $sk$：自重复打包在 BFV 密文中，简记 $bfvc{t}_{sk}=BF{V}_s(Ecd(sk\Vert ?\Vert sk,\Delta ))$

BFV 方案（MSD 编码）：

• 维度 $N$：二的幂次
• 密文模数 $Q$：满足 RNS 系统
• 明文模数 $t$：设置为 $t=q$，自动取模
• 私钥 $s{k}_{BFV}=s(x)$
• 公钥 $pk$，重线性化密钥 $evk$（同态乘法），旋转密钥 $rtk$（同态旋转）
• 秘钥切换密钥 $K_{s\to sk}$：运算完成之后从 BFV 切换回 LWE

在算法中，使用了 Pegaus 的同态线性变换：

NAND Gate

回顾下 FHEW 怎么计算 NAND Gate，

1. 将 ${\mathbb{Z}}_2$ 提升到 ${\mathbb{Z}}_4$，算术加法 ${\mu }^{\prime }={\mu }_1+{\mu }_2(\mathrm{mod}4)$
2. 使用 LUT，如果 ${\mu }^{\prime }=2$ 查表出 $\mu \leftarrow 1\in {\mathbb{Z}}_2$（存放在 ${\mathbb{Z}}_4$ 中），否则查表出 $\mu \leftarrow 0$

当然，这个 LUT 的 domain 和 range 都应当缩放为它们在 ${\mathbb{Z}}_q$ 上的编码值，并且旋转一定的角度使得它成为 Negacyclic 函数。

[LW23] 采用了 $p=3$（而不是 $p=4$），那么
$$b_i??a_i,sk?=?q/3??{\mu }_i+e_i$$
我们要求 $|e_i|<?q/12?$，从而 $|e_1+e_2|<?q/6?$ 解密正确。方便起见，[LW23] 将 $c_i=(a_i,b_i)$ 的相位旋转 $q/6$ 使得噪声是非负数，得到 $c_i^{\prime }=(a_i,b_i+?q/6?)$

那么，给定 $c=c_1+c_2$，
$$b??a,sk?\in ?\begin{array}{rlrl}0+e_1+e_2& \in [0,?q/3?),& & {\mu }_1={\mu }_2=0\\ ?q/3?+e_1+e_2& \in [?q/3?,2?q/3?),& & otherwise\\ 2?q/3?+e_1+e_2& \in [2?q/3?,q)& & {\mu }_1={\mu }_2=1\end{array}$$
因此，我们定义 NAND Gate 对应的 LUT：
$$f(x)=\{\begin{array}{rlr}0,& & x\in [2?q/3?,q)\\ ?q/3?,& & otherwise\end{array}$$
[LW21] 将它称为 DRaM（Division, Rounding, and Mapping）。我们将它在素域 ${\mathbb{Z}}_q$ 上插值为多项式：
$$P_f(x)=f(0)?\sum _{i=1}^{q?1}\left(\sum _{a=0}^{q?1}f(a)a^{q?1?i}\right)?X^i$$
注意，BFV 可以计算任意的多项式，并没有 Negacyclic 的约束。

现在的计算任务就是：
$$c\in {\mathbb{Z}}_q^{n+1}?P_f([b??a,sk?{]}_q)\in {\mathbb{Z}}_q$$
内积运算采取 Pegasus 的同态下线性变换，多项式求值运算采取 Paterson-Stockmeyer 算法。这些运算都是在 BFV Slots 上执行的，最后需要使用 [CHKKS18] 的同态解码算法（可以直接使用 Pegasus 的同态下线性变换，但存在更快的 FFT-style 算法 [HHC19]）。

我们设置 BFV 明文空间 $t=q$ 使得它自动模掉 LWE 的密文模数，批处理 $N$ 个 LWE 密文（占满 BFV Slots），LWE 的私钥 $sk\in {\mathbb{Z}}_q^n$ 被重复打包 $N/n$ 次。具体算法如下：

Optimizations

1. 如果某函数形如：
   $$f(x)=\{\begin{array}{rlr}0,& & ?x\in (?r,r)\\ c,& & otherwise\end{array}$$
   其中 $r\in [2,?q/2?],c\in {\mathbb{Z}}_q$ 都是常数，那么它对应的 $P_f$ 的系数有大约一半是零。因此，我们扭曲 NAND LUT 相位 $+?q/6?$，对应的扭曲 LWE 密文为 $(a,b?2?q/3???q/6?)$

2. 在 Pegaus 的同态线性变换中，采取了 BSGS 技巧，需要使用 $bfvc{t}_{sk}$ 分别旋转 $i?\sqrt{n},?i\in [\sqrt{n}]$ 个位置，这个可以被 KeyGen 时预计算（空间换时间）

3. 计算 DRaM 花费了较深的电路，我们直降将 $bfvc{t}_3$ 模切换到更低的模数 $Q^{\prime }?Q$ 上，然后再执行后续的 S2C（需要额外计算 $Q^{\prime }$ 下的旋转密钥 $rt{k}^{\prime }$）

4. 不再各个 LWE 密文分别 Key-Switch，我们可以在 $bfvc{t}_5$ 上执行 RLWE-KS，目标 $s\to s^{\prime }$ 是关于 $sk$ 的（使得 Extract 恰好是 $sk$ 加密的）

Other Binary Gates

一个重要的观察是 BFV 是以 SIMD 范式执行的，因此全部的槽都执行同一个 DRaM 多项式：它将 $x\in [2?q/3?,q)$ 映射到 $0$，其余的都映射到 $?q/3?$

虽然 NAND 是完备的，但是只用 NAND 搭建电路，其规模会较大。为了使得不同的槽可以执行任意的 Binary Gates，[LW23] 的思路是 “预处理+后处理”，使得全部的 Gates 都共用这个 DRaM 函数。

算法如下：

这个预处理和后处理的速度都是非常快的（仅仅是 $b\in {\mathbb{Z}}_q$ 上的加减法），其开销可以忽略。

Arbitrary Functions

对于更高精度的函数 $f:{\mathbb{Z}}_p\to {\mathbb{Z}}_q$，其中的 $p\ge 3$ 是任意素数，依旧可以采用上述的算法。唯一的修改就是我们在线构造 $P_f$ 多项式，并要求 LWE 密文噪声满足 $|e|\le ?q/2p?$ 从而解密正确。

算法如下：

Scheme Switching

易知：

• LWE 是 MSD 编码的，采用 [AP13] 的技术可以实现 BFV to/from BGV 的方案切换
• Pegasus 的同态线性变换就是 FHEW/TFHE to BFV/BGV 的方案切换
• [CHKKS18] 的 S2C 就是 BFV/BGV to FHEW/TFHE 的方案切换

Evaluation

参数：

效率：