Amortized bootstrapping via Automorphisms

参考文献：

1. [MS18] Micciancio D, Sorrell J. Ring packing and amortized FHEW bootstrapping. ICALP 2018: 100:1-100:14.
2. [GPV23] Guimarães A, Pereira H V L, Van Leeuwen B. Amortized bootstrapping revisited: Simpler, asymptotically-faster, implemented. ASIACRYPT 2023 (6): 3-35.
3. [DKM+24] De Micheli G, Kim D, Micciancio D, et al. Faster amortized FHEW bootstrapping using ring automorphisms. Public Key Cryptography 2024 (4): 322-353.
4. Amortized FHEW bootstrapping：Nussbaumer Transform & Ring Packing

[GPV23] 和 [DKM+24] 都遵照 [MS18] 的思路：

1. packing：将 $n$ 个 LWE 密文打包成单个 RLWE 密文，系数编码，形如 $(b,a)\in R_{q,n}^2$，私钥 $s\in R_n$
2. decryption：把 $s_i$ 加密在 RGSW 密文中作为自举密钥，将多项式 $a,b$ 的 DFT-form 加密在 RGSW 密文的指数上（$q$ 阶乘法循环群），利用 RGSW 同态乘法（指数上的加法）计算常数 $NTT(a)$ 和密文 $NTT(s)$ 的 Hadamard-product，然后做同态 IDFT 获得 $a\cdot s+b$ 各个系数的 RGSW 密文。
3. msbExtract：最后把各个系数的 MSB 从 RGSW 密文中提出成为 LWE 密文。

[MS18] 使用二的幂次分圆环对应的 RGSW 密文（模数 $q=2N$），将它搭建成支持模 $q$ 加法的寄存器。使用数字分解和枚举技术，使得这个寄存器也支持模 $q$ 数乘。为了快速计算 IDFT，[MS18] 使用 Nussbaumer Transform $R_{q,n}\cong R_{q,n/m}[X]/(X^m-Y)\to R_{q,n/m}[X]/(X^{km}-1)$，其中 $n\ge k{m}^2$ 并且 $n,m,k$ 都是同一个素数的幂次，这就构造出了合适的 $km$ 次本原单位根 $Y=X^m\in R_{q,n/m}$，并且和 $Y$ 的数乘就只是在 $R_{q,n/m}$ 环元素的系数旋转（重排 RGSW 寄存器）。

[MS18] 的均摊开销是 $\tilde{O}(n^{ϵ})$，然而隐藏常数 $O(2^{1/ϵ})$ 过大，导致并不实用。[GPV23] 和 [DKM+24] 都使用 Galois 自同构来实现数乘，并且直接用 Incomplete NTT 而非 Nussbaumer Transform。区别在于：[GPV23] 使用了素数次卷积环的 RGSW 寄存器，[DKM+24] 使用了素数次分圆环的 RLWE 寄存器，后者的计算效率会高一些。

RNS-GSW

由于均摊 FHEW/TFHE 自举的噪声比盲旋转大得多，这导致寄存器的密文模数可能会超过机器字。[GPV23] 提出了 GSW 的 Double-CRT 变体，以提高计算效率。

[GPV23] 使用卷积环 $\tilde{R}:=\mathbb{Z}[X]/(X^p-1)$，其中 $p$ 是素数，称为 CLWE 问题。有文章指出它和素数次分圆环的 RLWE 一样难。对于 $R:=\mathbb{Z}[X]/({\Phi }_p(X))$，其中 ${\Phi }_p(X)=1+X+X^2+\cdots +X^{p-1}$，定义投影函数 $L:R\to \tilde{R}$（疑问：系数 $a_{p-1}$ 不该存在吧）：
$$L_Q:\sum _{i=0}^{p-1}{a}_i{X}^i\to \sum _{i=0}^{p-1}{a}_i{X}^i-\left([p^{-1}{]}_Q\cdot \sum _{i=0}^{p-1}{a}_i\right)\cdot \sum _{i=0}^{p-1}{X}^i(\mathrm{mod}Q)$$
给定 RLWE 样本 $(a^{\prime },b^{\prime })\in R_Q^2$，将它转换为 CLWE 样本 $(a:=L_Q(a^{\prime }),b:=L_Q((1-X)\cdot b^{\prime }))\in {\tilde{R}}_Q^2$

素数次卷积环的 RNS-GSW 如下，

在 RLWE 假设下，对于形如 $X^k$ 的消息是 CPA-IND 安全的。

Shrinking

对于 Digit 分解，Approximate Gadget Decomposition 可以减少分解数量，并且基本不增加噪声。但是对于 RNS 分解，由于不存在确切的 LSD，因此并不兼容。[GPV23] 提出了 Shrinking 技术，用于 RNS 的近似分解。

模数 $Q={\prod }_{i=1}^l{q}_i$，令 $d\mid l$ 是整数，定义 CRT Digit 为 $D_i={\prod }_{j=(i-1)k+1}^{ik}{q}_j,1\le i\le d$（就是分区 $d$ 块），令 D = max ⁡ { D i } D = \max\{D_i\} D=max{Di​} 是上界。定义 $Q_i=Q/D_i$ 和 ${\hat{Q}}_i=[Q_i^{-1}{]}_{D_i}$，那么令 $g=(Q_1{\hat{Q}}_1,\cdots ,Q_d{\hat{Q}}_d)\in {\mathbb{Z}}^d$ 是 gadget vector，对应的分解 $g^{-1}(a)$ 就是 $\{[a{]}_{D_i}{\}}_{1\le i\le d}$，满足 $⟨g^{-1}(a),g⟩=a$

给定缩放因子 $\alpha \in {\mathbb{Z}}_Q$，对应的 RNS 表示是 ${\alpha }_i=[\alpha {]}_{D_i}$，然后定义 $g_{\alpha }=(Q_1{\hat{Q}}_1{\alpha }_1,\cdots ,Q_d{\hat{Q}}_d{\alpha }_d)$，将它称为 scaled gadget vector。对于任意的 $a\in R_Q$，容易证明它满足 $⟨g^{-1}({\alpha }^{-1}a),g_{\alpha }⟩=a$

Shrinking 就是删除一部分 CRT Digit，做模切换，并相应的调整缩放因子

1. 给定 scaled gadget 分解 $a_i=[a{]}_{D_i},1\le i\le d$，它的缩放因子是 $\alpha$
2. 给定 $1\le k<d$，定义 $D^{(k)}={\prod }_{i=1}^k{D}_i$ 和 $Q^{\prime }=Q/D^{(k)}$
3. 对于 $k+1\le i\le d$，计算 $a_{i-k}^{\prime }=a_i\cdot [D^{(k)}{]}_{D_i}$
4. 输出 $a_j^{\prime },1\le j\le d-k$，它的缩放因子是 ${\alpha }^{\prime }=\alpha \cdot [(D^{(k)}{)}^{-1}{]}_{Q^{\prime }}$

如果 RNS-GSW 密文加密了 $\alpha \cdot m$，噪声 $E$，私钥分布是 $S$ 亚高斯。那么执行 Shrinking 之后，加密 ${\alpha }^{\prime }\cdot m$，噪声 $O(E/D^{(k)}+\sqrt{p}\cdot S)$，其中 $p$ 是 CLWE 中的素数次。

Amortized Bootstrapping

由于 [GPV23] 和 [DKM+24] 的整体思路是相同的，仅仅是使用的寄存器不同。现在只看看 [DKM+24] 是怎么工作的。

RLWE‘ to RGSW

[DKM+24] 使用 RLWE’ 寄存器，但是在计算同态乘法时需要 RGSW 密文。因此，需要把 RLWE’ 提升到 RGSW

使用 $RLW{E}_{sk}^{\prime }(s{k}^2)$ 作为提示（称为 evaluation key），那么给定 $(b,a)=RLW{E}_{sk}(v_{i}m)$，可以计算
$$(0,b)+a\odot RLW{E}_{sk}^{\prime }(s{k}^2)=RLW{E}_{sk}(v_{i}m\cdot sk+e\cdot sk)$$
把它们重排为 RGSW 密文即可。

Prime Cyclotomic Rings

[DKM+24] 使用 $R_{reg}={\mathbb{Z}}_Q[X]/({\Phi }_q(X))$ 作为寄存器的空间，其中 $q$ 是素数。对于整数 $m\in {\mathbb{Z}}_q$，将它编码为 $X^m\in R_{reg}$ 加密为 RLWE’ 或者 RGSW 密文。

需要重新考虑这种 RGSW 密文上外积的噪声增长情况，

对于二的幂次分圆环，噪声为 ${\sigma }_{\odot }^2=B^2{d}_{B}N{\sigma }_{input}^2/12$，因此素数次分圆环上的噪声仅增长了 $2$ 因子，可以接受。

Decryption

[DKM+24] 使用 [MS18] 的框架，主要的区别就是在同态解密步骤使用了素数次分圆环，利用 Galois 自同构实现数乘，利用 Incomplete NTT 实现 IDFT。

令 $d$ 是二的幂次，定义 $R_{in}={\mathbb{Z}}_q[X]/({\Phi }_d(X))$，作为打包密文的空间。给定 $\varphi (d)$ 个 LWE 密文，使用 Ring Packing（就是 column method Pub-KS）将它们转化为系数打包的 RLWE 密文 $(b,a)\in R_{in}^2$，私钥是 $z\in R_{in}$

对于卷积环，将它的 FFT/NTT 称为 standard/cyclic FFT。对于分圆环，将它的 FFT/NTT 称为 primitive/cyclotomic FFT。

• 对于寄存器本身，基本运算是在 $R_{reg}$ 上执行的，需要把 ${\mathbb{Z}}_Q[X]/(1+X+X^2+\cdots +X^{q-1})$ 做 primitive FFT，不过我们直接将寄存器视为一个黑盒，可以不关心这个的实现。
• 对于打包密文，基本运算是在 $R_{in}$ 上执行的，需要对反卷积环 ${\mathbb{Z}}_q[X]/(X^{\varphi (d)}+1)$ 做 primitive FFT，可以先执行相同长度的 cyclic FFT，然后乘以一些 twist factor 即可。这些运算是利用大量的寄存器完成的。

为了快速计算 $b+a\cdot z\in R_{in}$，[DKM+24] 采用了 partial primitive FFT（PFT），因为噪声增长是和递归分解的深度呈指数的，只能做常数深度的分解。分解是：
$${\mathbb{Z}}_q[X]/(X^{\varphi (d)}+1)\cong \prod _{i=0}^{\varphi (d)/k-1}{\mathbb{Z}}_q[X]/(X^k-{\zeta }_i)$$
其中 ${\zeta }_i$ 是所有的 $d/k$ 次本原单位根。由于 DFT 和 IDFT 的表达式之间有个缩放因子，自举过程中 DFT 是明文下的，IDFT 是密文下的。为了减少同态开销，[DKM+24] 将这个缩放因子从 IDFT 移动到了 DFT。于是，给定环元素 $a\in R_{in}$，执行 PFT 获得：
$${\tilde{a}}_i=[(\varphi (d)/k{)}^{-1}{]}_q\cdot a(\mathrm{mod}{X}^k-{\zeta }_i)$$
对于私钥 $z\in R_{in}$，也将它做 PFT 获得 $\varphi (d)/k$ 个多项式 { z ~ i } \{\tilde z_i\} {z~i​}，将它们的系数 ${\tilde{z}}_i^{(j)}\in {\mathbb{Z}}_q$ 加密为：
$$RGSW(X^{{\tilde{z}}_i^{(j)}}),0\le i<\varphi (d)/k,0\le j<k$$
对于某个小环 ${\mathbb{Z}}_q[X]/(X^k-{\zeta }_i)$，按照 Schoolbook 方式计算 $v={\tilde{a}}_i\cdot {\tilde{z}}_i$，
$$\begin{array}{r}{v}_j=\sum _{l=0}^j{\tilde{z}}_i^{(l)}{\tilde{a}}_i^{(j-l)}+{\zeta }_i\cdot \sum _{l=j+1}^{l-1}{\tilde{z}}_i^{(l)}{\tilde{a}}_i^{(k+j-l)}\end{array}$$
由于 ${\tilde{a}}_i$ 是明文，因此可以把 $v_j$ 视为密文向量 $\vec{z}=({\tilde{z}}_i^{(0)},\cdots ,{\tilde{z}}_i^{(k-1)})$ 和明文向量 $\vec{c}=({\tilde{a}}_i^{(j)},{\tilde{a}}_i^{(j-1)},\cdots ,{\tilde{a}}_i^{(0)},{\zeta }_i{\tilde{a}}_i^{(k-1)},{\zeta }_i{\tilde{a}}_i^{(k-2)},\cdots ,{\zeta }_i{\tilde{a}}_i^{(j+1)})$ 的内积。毕竟密文上的数乘是相对明文数乘更贵的。[DKM+24] 使用 RLWE’ 寄存器（编码在指数上，线性同态），同态数乘使用 Galois 自同构（输入输出都是 RLWE’ 密文），同态加法使用 RGSW 外积（输入 RGSW 和 RLWE’ 密文，输出 RLWE’ 密文）。为了减少 RLWE’ to RGSW 转换，可以使用如下的方式计算 $\vec{z},\vec{c}$ 的内积（假设 $c_i\in {\mathbb{Z}}_q$ 全都非零、可逆，如果是零则简单删除）：
$$v_j=((\cdots (z_0{c}_0{c}_1^{-1}+z_1)c_1{c}_2^{-1}+\cdots )z_{k-2}{z}_{k-1}^{-1}+z_{k-1})c_{k-1}$$
这样整个过程都只需要 RLWE’ 寄存器，并不需要转换到 RGSW 密文。

算法是：

现在，我们计算出了 ${\tilde{v}}_i={\tilde{a}}_i\cdot {\tilde{z}}_i\in {\mathbb{Z}}_q[X]/(X^k-{\zeta }_i)$，它的系数加密在 $k$ 个 RLWE’ 寄存器内。重复 $\varphi (d)/k$ 次，计算出所有的 { v ~ i } \{\tilde v_i\} {v~i​}，接下来需要执行 Homomorphic IPFT 恢复出 $v=a\cdot s$ 的各个系数。

INTT

这个过程的思想很简单，就是直接用 RLWE’ 寄存器的线性同态，执行 Inverse PFT 即可。

根据环同构：
$$\begin{array}{rl}{\mathbb{Z}}_q[X]/(X^{\varphi (d)}+1)& \cong ({\mathbb{Z}}_q[Y]/(Y^{\varphi (d)/k}+1))[X]/(X^k-Y)\\ & \cong {\mathbb{Z}}_q^{\varphi (d)/k}[X]/(X^k-Y)\end{array}$$
其中 ${\mathbb{Z}}_q^{\varphi (d)/k}$ 是以 coeff-wise 方式运算的。Incomplete cyclotomic NTT 可以写成多个 Complete cyclotomic NTT 的并行。

根据环同构：
$${\mathbb{Z}}_q[Y]/(Y^{\varphi (d)/k}+1)\cong {\mathbb{Z}}_q[Z]/(Z^N-1)$$
其中 $Y=Z\zeta$，这里 $\zeta$ 是 $d/k$ 次本原单位根，而 $Z$ 是 $N=\varphi (d)/k$ 次本原单位根。Complete cyclotomic NTT 可以写成 Complete cyclic NTT，然后再扭曲。

根据环同构：
$${\mathbb{Z}}_q[Z]/(Z^R-{\zeta }_N^j)\cong \prod _{i=0}^{r-1}{\mathbb{Z}}_q[Z]/(Z^{R/r}-{\zeta }_N^{j{r}^{-1}+iN/r})$$
以及映射 $Z^{R/r}\to {\zeta }_N^{j{r}^{-1}+iN/r}$，
$$\sum _{k=0}^{R-1}{a}_k{Z}^k\to \sum _{l=0}^{R/r-1}\left(\sum _{k=0}^{r-1}{a}_{l+kR/r}({\zeta }_N^{j{r}^{-1}+iN/r}{)}^k\right)\cdot Z^l$$
其中 ${\zeta }_N^{j{r}^{-1}+iN/r}$ 是所有的 ${\zeta }_N^j$ 的 $r$ 次根，这里 $r\mid R\mid N$ 是当前层的 radix 设置。Complete cyclic NTT 的每一层分解都是若干个关于某些单位根的多项式求值。

其中的 { r i } 0 ≤ i < l \{r_i\}_{0 \le i < l} {ri​}0≤i<l​ 是每一层分解的 radix，递归深度 $l$ 是常数。由于自举的最终结果是单个 RLWE 密文，因此它的各个系数只需要被加密在单个 RLWE 寄存器里，所以最后一层使用外积 $Q/4\odot c{t}_i$ 把寄存器 $RLW{E}^{\prime }(X^v)$ 转化为 $RLWE(Q/4\cdot X^v)$ 密文，这里的 $4$ 是原始 FHEW 的明文模数。

依次执行 ${\tilde{v}}_i={\tilde{a}}_i\cdot {\tilde{s}}_i$ 以及上述的 P F T − 1 ( { v ~ i } ) PFT^{-1}(\{\tilde v_i\}) PFT−1({v~i​})，最终获得各个系数的密文 $RLWE(Q/4\cdot X^{(a\cdot s{)}_j})$，然后再分别乘以 $X^{b_j}$ 得到 $\varphi (d)$ 个密文 $RLWE(Q/4\cdot X^{(b+a\cdot s{)}_j})$

msbExtract

现在 $(b,a)\in R_{in}^2$ 相位的各个系数 $c=(b+a\cdot s{)}_i\in {\mathbb{Z}}_q$ 分别加密在 RLWE 密文 $(\hat{b},\hat{a})\in R_{reg}^2$ 相位的指数上，简记为 $m(X)=Q/4\cdot X^c\in R_{reg}$，私钥是 $\hat{s}\in R_{reg}$

由于 ${\Phi }_q(X)=1+X+\cdots +X^{q-1}$，因此有 $X^{q-1}\equiv -1-X-\cdots -X^{q-2}$ 以及 $X^q=1$，那么
$$\begin{array}{rl}{m}_i+e_i& ={\hat{b}}_i+\sum _{j=0}^i{\hat{a}}_{i-j}{\hat{s}}_j+\sum _{j=i+2}^{q-2}{\hat{a}}_{q+i-j}{\hat{s}}_j-\sum _{j=1}^{q-2}{\hat{a}}_{q-1-j}{\hat{s}}_j\\ & ={\hat{b}}_i+⟨({\hat{a}}_i,{\hat{a}}_{i-1}-{\hat{a}}_{q-2},{\hat{a}}_{i-2}-{\hat{a}}_{q-3},\cdots ,\\ & {\hat{a}}_0-{\hat{a}}_{q-i-1},0-{\hat{a}}_{q-i-2},{\hat{a}}_{q-2}-{\hat{a}}_{q-i-3},\cdots ,{\hat{a}}_{i+2}-{\hat{a}}_1),({\hat{s}}_0,\cdots ,{\hat{s}}_{q-2})⟩\end{array}$$
因此 $(b_i,{\vec{a}}_i:=({\hat{a}}_i,{\hat{a}}_{i-1}-{\hat{a}}_{q-2},{\hat{a}}_{i-2}-{\hat{a}}_{q-3},\cdots ,{\hat{a}}_0-{\hat{a}}_{q-i-1},0-{\hat{a}}_{q-i-2},{\hat{a}}_{q-2}-{\hat{a}}_{q-i-3},\cdots ,{\hat{a}}_{i+2}-{\hat{a}}_1))\in {\mathbb{Z}}_Q^q$ 就是 $m(X)$ 系数 $m_i$ 的密文，私钥是 $\vec{s}:=({\hat{s}}_0,\cdots ,{\hat{s}}_{q-2})$，噪声是 $e_i$

• 如果 $c=i$，那么 $m_i=Q/4$
• 如果 $c=q-1$，那么 $m_i=-Q/4$
• 对于其他的 $c$，都是 $m_i=0$

为了提取出系数 $c=q/2\cdot \mu +e$ 所编码的消息 μ ∈ { 0 , 1 } \mu \in \{0,1\} μ∈{0,1}，由于噪声范围 $[-q/4,q/4)$，因此 $\mu =1⟺c\in (q/4,3q/4)$，那么把这个区间的 LWE 密文加起来即可（注意 $m(X)$ 恰是 one-hot 向量）。

Counting

以外积为单位，各个步骤的复杂度是：

各个步骤的噪声增长是：

安全强度 $\lambda =O(n)$，模数 $Q=poly(n)$，打包数量 $\varphi (d)=O(n)$，Gadget 分解长度 $d_B={\log }_{B}Q$。由于环元素和 RLWE’ 密文外积的噪声是 ${\sigma }_{\odot }^2=B^2{d}_{B}q{\sigma }_{input}^2/6=O(n)\cdot {\sigma }_{input}^2$，上述的 ${\sigma }_{\odot ,aut}^2,{\sigma }_{\odot ,eval}^2,{\sigma }_{\odot ,RGSW}^2$ 分别是 RLWE’ 自同构密钥、RLWE‘ to RGSW 切换密钥、RGSW 自举密钥的方差取代 ${\sigma }_{input}^2$ 之后的值。假如 PFT 的迭代深度是 $l$ 层，那么最终的方差是 $O(n^l)\cdot {\sigma }_{aut,eval,RGSW}^2$，是关于 $l$ 指数级的。由于 $Q$ 是多项式规模的，因此 $l$ 必须是较小的常数。

对于常数深度 $l$，设置 $k=r=\varphi (d{)}^{1/l}$，这里 $k$ 是分解后的小多项式长度，$r$ 是各层分解的 radix 大小。那么，总的复杂度是 $O(l{n}^{1+1/l}\log n)$ 次环元素和 RLWE’ 的外积，均摊复杂度是 $O(l{n}^{1/l}\log n)$ 次外积。