Pegasus：CKKS 和 TFHE 的混合

参考文献：

1. [GHS12] Gentry C, Halevi S, Smart N P. Better bootstrapping in fully homomorphic encryption[C]//International Workshop on Public Key Cryptography. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012: 1-16.
2. [HS14] Halevi S, Shoup V. Algorithms in helib[C]//Advances in Cryptology–CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2014, Proceedings, Part I 34. Springer Berlin Heidelberg, 2014: 554-571.
3. [HS15] Halevi S, Shoup V. Bootstrapping for HElib[J]. Journal of Cryptology, 2021, 34(1): 7.
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. [MS18] Micciancio D, Sorrell J. Ring packing and amortized FHEW bootstrapping[J]. Cryptology ePrint Archive, 2018.
6. [HS18] Halevi S, Shoup V. Faster homomorphic linear transformations in HElib[C]//Annual International Cryptology Conference. Cham: Springer International Publishing, 2018: 93-120.
7. [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.
8. [HHC19] Han K, Hhan M, Cheon J H. Improved homomorphic discrete fourier transforms and FHE bootstrapping[J]. IEEE Access, 2019, 7: 57361-57370.
9. [LHH+21] Lu W, Huang Z, Hong C, et al. PEGASUS: bridging polynomial and non-polynomial evaluations in homomorphic encryption[C]//2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021: 1057-1073.
10. [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.
11. [MP21] Micciancio D, Polyakov Y. Bootstrapping in FHEW-like cryptosystems[C]//Proceedings of the 9th on Workshop on Encrypted Computing & Applied Homomorphic Cryptography. 2021: 17-28.
12. [LHH+21] Lu W, Huang Z, Hong C, et al. PEGASUS: bridging polynomial and non-polynomial evaluations in homomorphic encryption[C]//2021 IEEE Symposium on Security and Privacy (SP). IEEE, 2021: 1057-1073.
13. 源码：https://github.com/Alibaba-Gemini-Lab/OpenPEGASUS
14. Full-RNS BGV/BFV
15. Homomorphic DFT
16. CKKS 同态模约简
17. Chimera：混合的 RLWE-FHE 方案
18. Amortized FHEW bootstrapping
19. FHEW 和 TFHE 的统一框架
20. 分园域的一些结论
21. 有限域的结构(3): 迹, 范数与基
22. 数论–数域的扩张

[MS18] 为了实现均摊 FHEW 自举，提出了 Ring packing 技术：将多个 LWE 密文（行矢）堆叠为 $(A,b)$，然后按列转化为多项式，使用 Key-Switch 执行同态线性解密 $A?E(s)+b$（私钥被加密在系数上），最终获得打包了 $\mu ={\sum }_j{\mu }_j{x}^j$ 的单个 RLWE 密文。虽然它是 Coeff Packing 的，但是同态 InvDFT 目的是加速同态的多项式乘法（线性解密部分），而非 SIMD 并行。但是其中的 SwK 是对于 LWE 私钥的各个分量分别用 RLWE 加密的 $RLW{E}_{s^{\prime }}(s_i?g_j)$，规模大、速度慢。

[LHH+21] 提出的 Chimera 也使用类似的堆叠技术，将 TLWE 打包转换到 RLWE 密文上。不过它将堆叠出的矩阵 $C=(A,b)$ 直接乘以 InvDFT，于是 $(InvDFT?C)?s=InvDFT(\mu (x))$，这就将各个 ${\mu }_j$ 编码到了明文槽。它的 SwK 也是各个私钥分量分别被加密在系数上 $RGS{W}_{s^{\prime }}(s_i)$，规模很大（GB 级别）

[CDKS21] 提出了新的 Key-Switch 技术（后文简记 KS），将 LWE 密文嵌入到 RLWE 密文上，对应的 SwK 将LWE 私钥作为单个多项式做 RLWE 加密 $RLW{E}_{s^{\prime }}(s(x)?g_j)$，从而极大的提高了 KS 的速度。需要使用分圆域的自同构的某些特殊性质，消除一些杂项。推广这个 KS 过程，可以获得 LWE 打包到 RLWE 的过程，不过它也是 Coeff Packing 的，还应该使用 Coeff-to-Slot 过程（基本就是同态 InvDFT）将它们编码到明文槽，从而适配 SIMD 技术。

之后的 Pegasus 也使用密文堆叠技术，对于私钥 $s$ 的密文做线性变换，来实现 LWE-to-RLWE 过程。同态线性变换过程中，采取对角线乘法（旋转+阿达玛），LWE 私钥作为一个整体被加密在明文槽上 $RLW{E}_{s^{\prime }}(Ecd(s,\Delta ))$，规模大大减小（MB 级别），同态解密的结果直接在明文槽上。

Conversion Between (R)LWE

Tower of Cyclotomic

令 $m=2^{L+1}$ 是二的幂，$N=?(m)=2^L$ 也是二的幂，分圆域 $K=\mathbb{Q}({\zeta }_m)?\mathbb{Q}[X]/(X^N+1)$，分圆整数环 $R=\mathbb{Z}[{\zeta }_m]?\mathbb{Z}[X]/(X^N+1)$，为了区分不同维度我们记为 $K_N,R_N$

根据代数理论，域扩张 $K/\mathbb{Q}$ 都是 Galois 扩张，Galois 群 G a l ( K / Q ) ? Z m ? = { 1 , 3 , ? ? , 2 N ? 1 } Gal(K/\mathbb Q) \cong \mathbb Z_m^*=\{1,3,\cdots,2N-1\} Gal(K/Q)?Zm??={1,3,?,2N?1}，自同构：
$${\tau }_d:{\zeta }_m\to {\zeta }_m^d,?d\in {\mathbb{Z}}_m^{?}$$
域的迹：
$$T{r}_{K/\mathbb{Q}}:a\in K?\sum _{\tau \in Gal(K/\mathbb{Q})}\tau (a)\in \mathbb{Q}$$
根据代数知识，$T{r}_{K/\mathbb{Q}}$ 是 $\mathbb{Q}$-线性映射，并且满足

• $T{r}_{K/\mathbb{Q}}(1)=[K:\mathbb{Q}]=N$
• $T{r}_{K/\mathbb{Q}}(X^i)=0,?i\ne 0$

对于分圆塔：
$$K=K_N\ge K_{N/2}\ge ?\ge K_1=\mathbb{Q}$$
其中 $K_n,n=2^l$ 可以作为 $K_N$ 的子域（$R_n\le R_N$ 类似），设置 $Y=X^{N/n}$，
$$K_n=?\sum _{i\in [n]}{a}_i{Y}^i:a_i\in \mathbb{Q}??K_N$$
基于分圆塔，可以将迹分解：
$$T{r}_{K/\mathbb{Q}}=T{r}_{K_2/K_1}°?°T_{K_N/K_{N/2}}$$
易知，相邻的域扩张的次数为 $2$，仅包含一个非凡自同构（另一个是恒等映射）：
G a l ( K 2 l / K 2 l ? 1 ) = { τ 1 ∣ K 2 l , ?? τ 2 l + 1 ∣ K 2 l } , ?? 1 ≤ l ≤ L Gal(K_{2^l}/K_{2^{l-1}}) = \{\tau_1|_{K_{2^l}},\,\, \tau_{2^l+1}|_{K_{2^l}}\},\,\, 1 \le l \le L Gal(K2l?/K2l?1?)={τ1?∣K2l??,τ2l+1?∣K2l??},1≤l≤L
其中的 ${\tau }_{2^l+1}{|}_{K_{2^l}}$ 是自同构映射 ${\tau }_{2^l+1}\in Gal(K/\mathbb{Q})$ 限制在 $K_{2^l}?K_N$ 上，容易验证它是 $K_{2^l}$ 的 $K_{2^{l?1}}$-自同构。进一步的，简记 $n=2^l$，$Y=X^{N/n}$ 是 $K_n/\mathbb{Q}$ 的扩张元，那么有：
$$T{r}_{K_n/K_{n/2}}(Y^i)=\{\begin{array}{rlr}2Y^i,& & ?2\mid i\\ 0,& & ?2?i\end{array}$$
因此，映射 $\mu \in K_n?T{r}_{K_n/K_{n/2}}(\mu )\in K_{n/2}$，记号 $a\Vert b$ 表示 “恰好整除”，

1. 将系数 $\mu [i],(2N/n)\Vert i$，加倍
2. 将系数 $\mu [i],(N/n)\Vert i$，清零
3. 元素 $\mu \in K_n?K_N$ 的其他系数本来就是零，保持

我们定义 [ N ] = { 0 , 1 , ? ? , N ? 1 } [N]=\{0,1,\cdots,N-1\} [N]={0,1,?,N?1} 的一组划分（子域的系数索引），
I k : = { i ∈ [ N ] : 2 k ∥ i } , ?? 0 ≤ k < L I_k := \{ i \in [N]: 2^k\|i \},\,\, 0 \le k< L Ik?:={i∈[N]:2k∥i},0≤k<L
特别地设置 I L = { 0 } I_L=\{0\} IL?={0}，容易验证 $[N]={?}_k{I}_k$

对于 $d=2^l+1,1\le l\le L$，简记 $i=2^{k}j\in I_k$，其中 $j$ 是奇数，
$$i?d=2^{k+l}j+2^{k}j=?\begin{array}{ll}{2}^k(2^{l}j+j)\in I_k& ?0\le k\le L\\ 2^{k}j=i(\mathrm{mod}2N),& ?k>L?l\\ 2^L+2^{k}j=N+i(\mathrm{mod}2N),& k=L?l\end{array}$$
因此，${\tau }_d:{\zeta }^i\to {\zeta }^{i?d}$ 是对各个索引 $I_k$ 做了符号置换（signed permutation），$?i\in I_k,?r\in I_k,{\tau }_d(X^i)=\pm X^r$。特别地对于 $k\ge L?l$ 的那些 $I_k$，
$${\tau }_d(X^i)=?\begin{array}{rlr}{X}^i,& & ?i\in \underset{k>L?l}{?}{I}_k\\ ?X^i,& & ?i\in I_{L?l}\\ ...& & otherwise\end{array}$$
因此，映射 $\mu \in K_N?\mu +{\tau }_d(\mu )\in K_N$，

1. 将系数 $\mu [i],2^{L?l+1}|i$，加倍
2. 将系数 $\mu [i],i\in I_{L?l}$，清零
3. 其他系数的变化较为复杂

LWE-to-LWE

LWE 密文 $(b,a)\in {\mathbb{Z}}_q^{1+N}$，私钥 $s\in {\mathbb{Z}}^N$，线性解密获得相位（不考虑纠错），
$${\mu }_0=b+?a,s?(\mathrm{mod}q)$$
执行 KS 时，抽象思路是 K = { L W E s ′ ( s i ) } K=\{LWE_{s'}(s_i)\} K={LWEs′?(si?)}，然后同态解密获得 $LW{E}_{s^{\prime }}({\mu }_0)$，但是这么做的复杂度太高了。[CDKS21] 提出了一种新的 KS 过程：

1. 将 $a$ 转化为多项式 $a(x)=\iota (a)\in R_{N,q}$，其中的映射 $\iota :{\mathbb{Z}}^N\to R_N$ 是将向量作为多项式系数
2. 将 $s$ 转化为多项式 $s(x)={\tau }_{?1}°\iota (s)\in R_N$，其中的 ${\tau }_{?1}$ 是因为多项式乘积是向量反卷积

那么，获得的 $(b,a(x))\in R_{N,q}^2$ 可以视为 $s(x)$ 加密的 RLWE 密文，容易验证 $\mu (x)=b+a(x)s(x)\in R_{N,q}$，它的常数项 $\mu [0]$ 恰好就是 ${\mu }_0$ 了。

因此我们可以使用 K = { R L W E s ′ ( s ( x ) ? g i ) } K=\{RLWE_{s'}(s(x) \cdot g_i)\} K={RLWEs′?(s(x)?gi?)} 作为 SwK，执行 RLWE 的秘钥切换，最后提取出常数项对应的 LWE 密文。其中的 $g=(g_1,?,g_d)$ 是 Gadget Vector，可使用 [BGV12] 的 Base decomposition 或者 [BEHZ16] 的 Prime decomposition（用于兼容 RNS 系统）。

具体算法为：

LWE Key-Switch 的噪声为 $e_{ks}=?g^{?1}(c_1),e?$，其中 $e\leftarrow {\chi }_{\sigma }$ 是 SwK 的噪声。为了兼容 RNS 系统，我们使用素数分解 $g^{?1}:a?\{[a{]}_{q_i}\in R_{N,q_i}\}$，那么可以计算出 $e_{ks}$ 各个系数的方差
$$V_{ks}\le \frac{1}{12}N{\sigma }^2?\sum _i{q}_i^2$$
易知 LWE-to-LWE 的噪声就是 Key-Switch 的噪声。

LWE-to-RLWE

上述的 LWE-to-LWE 过程中，产生的 $c{t}^{\prime }$ 并非是有效 RLWE 密文（相位只有常数项是有意义的，其他位置都是无效数据）。[CDKS21] 使用迹 $T{r}_{K/\mathbb{Q}}$ 来消除 $X^i,i\ne 0$ 的系数，只保留常数项（缩放因子 $N$）。

直接计算 $T{r}_{K/\mathbb{Q}}$ 需要分别计算各个 ${\tau }_d,d\in {\mathbb{Z}}_m^{?}$，共计需要 $N$ 个自同构映射（每一次都需要做 KS 过程）。因此，借助分圆塔将 $T{r}_{K/\mathbb{Q}}$ 分解，成为 $L=\log N$ 个相邻分圆域的迹 $T{r}_{K_{2^l}/K_{2^{l?1}}}$ 的组合，这样就只需要计算 $\log N$ 个非凡自同构。

具体算法为：

为了消除 $N$ 缩放因子，可以预先对输入的 LWE 密文缩放 $[N^{?1}{]}_q$ 因子，从而上述算法的输出自然地消除了它们。

因为自同构 ${\tau }_d$ 是保长的，因此不会导致噪声过度膨胀。同态迹的噪声是
$$Var\le \frac{1}{3}((\frac{N}{n}{)}^2?1)?V_{ks}$$
选取 $n=1$，LWE-to-RLWE 的噪声就是 $Var\le \frac{1}{3}(N^2?1)?V_{ks}$

LWEs-to-RLWE

假如我们希望将相位是 ${\mu }_j,j\in [n]$ 的多个 LWE 密文打包到单个 RLWE 密文中：直接使用上述的转换得到 $c{t}_j$，然后计算 $c{t}^{\prime }={\sum }_{j\in [n]}c{t}_j?Y^j,Y=X^{N/n}$，那么它的相位就是：
$${\mu }^{\prime }=N?\sum _{j\in [n]}{\mu }_j{Y}^j\in R_n?R_N$$
然而上述算法的计算效率和噪声增长都不算好。[CDKS21] 提出了 FFT-style 递归算法：假设 $n=2^l$，为了计算 ${\mu }^{\prime }$，可以将 ${\mu }_j$ 分为大小 $2^{l?1}$ 的两组，分别计算出
$$\begin{array}{rl}{\mu }_{even}^{\prime }& =N/2?\sum _{j\in [n/2]}{\mu }_{2j}{Y}^{2j}\in R_{n/2}\\ {\mu }_{odd}^{\prime }& =N/2?\sum _{j\in [n/2]}{\mu }_{2j+1}{Y}^{2j}\in R_{n/2}\end{array}$$
但是实际上我们只需要计算出 ${\mu }_{even},{\mu }_{odd}\in R_N$，使得它们的 $Y^{2j}$ 系数组成了 ${\mu }_{even}^{\prime },{\mu }_{odd}^{\prime }\in R_{n/2}$，然后将 ${\mu }_{odd}$ 旋转 $Y$ 加到 ${\mu }_{even}$ 上，并使用自同构 ${\tau }_d,d=2^l+1$ 来消除 ${\mu }_{odd}$ 那些恰好被旋转到 ${\mu }_{even}^{\prime }$ 位置上的杂项：
$$\mu =({\mu }_{even}+Y?{\mu }_{odd})+{\tau }_d({\mu }_{even}?Y?{\mu }_{odd})$$
由于 $?Y?{\mu }_{odd}$ 的有效系数 $?{\mu }_{2j+1}$ 是在 $Y^{2j+1}$ 上，因此 ${\tau }_d$ 将它们取反为 ${\mu }_{2j+1}$ ，而那些被旋转到 $Y^{2j}$ 的杂项 $?e$ 则保持不变，正好和 $Y?{\mu }_{odd}$ 添加到 ${\mu }_{even}$ 上的杂项 $e$ 相互消除。最终，相位 $\mu \in R_N$ 的那些 $Y^j$ 的系数恰好是 $N?{\mu }_j$，只要再消除其他的杂项就可以得到 ${\mu }^{\prime }\in R_n$，这里可以使用 $T{r}_{K_N/K_n}$ 来消除它们。

具体算法为：

注意到 ${\mu }_j$ 是打包在系数上的，一般 FHE 可能需要使得消息是打包在明文槽里的，这可以使用 [GHS12] [HS15] [HHC19] 的 Coeff-to-Slot 技术进行转换。[CDKS21] 说这些转换的速度特别快（真的么？），因此主要开销还是在 LWEs-to-RLWE 上面。

可以证明 LWEs-to-RLWE 的噪声也是 $Var\le \frac{1}{3}(N^2?1)?V_{ks}$

Lightweight Communication

三种转换的效率和噪声：

优势：

• 原始的 KS 过程，对于前两个参数，执行时间为 $203$、$1628$ 毫秒，因此嵌入到 RLWE 后的效率提升了 $2$ 个数量级（例如 $1.03$ 毫秒）
• 噪声仅为 $O(\log N)$-bit，因此可以使用 LWE 密文，留出足够的噪声空间， $b\in {\mathbb{Z}}_q$ 的大部分空间都可用于存储消息（例如 $389?23$ 比特）

对于云计算场景，我们使用对称版本的 LWE 加密方案，那么多个密文的 $a_j\in {\mathbb{Z}}_q^N$ 完全可以被替代为随机种子，$a_j=PRF(seed,j)$，这导致了 Rate 高达 $1?o(1)$ 的对称加密。在同态运算之前，需要同态解密，因为 LWE-based 是 FHE 友好的（只需要部分的同态解密，不必纠错），直接使用上述的 LWEs-to-RLWE 就可以转化为合适的 FHE 密文（这三种转换都是保护相位的，通用于任意的 FHE 方案）

PEGASUS

Pegasus 是阿里团队 [LHH+21] 提出的一种混合方案：使用 CKKS 计算多项式（word-wise），使用 TFHE 计算非多项式（bit-wise）。他们使用了 [CHKKS19] 的 Full RNS CKKS（效率更高），[MP21] 的三元秘密 TFHE（更加安全）

MP-FFT 和 RNS-NTT 的效率对比：

Pegasus 使用了四种核心算法：

• 秘钥切换算法直接使用 [CDKS21] 的，同态取模算法直接使用 [HK20] 的
• [MP21] 的 LUT 算法只能处理较小的模数，Pegasus 使用缩放技术（近似的），从而支持很大的模数
• [HS18] 的同态线性算法更适合处理方阵，Pegasus 使用瓷砖技术，将 “长矩阵”、“矮矩阵” 都转化为方阵

Pegasus 的基本计算逻辑是：

1. 输入 CKKS 密文，消息被自重复打包在明文槽内，即 $Ecd(v\Vert v\Vert ?\Vert v,\Delta ),v\in {\mathbb{R}}^l,l\mid \overline{n}$
2. 使用 Slot-to-Coeff 算法（[HHC19] 的 FFT-style 算法）将消息从明文槽移动到系数上，再使用 Ectract 算法提取出 $\Delta v_i$ 的 LWE 密文（维度 $\overline{n}$）
3. 使用 KS 过程（[CDKS21] 的 LWE-to-LWE 算法）将维度缩减到 $\underline{n}<\overline{n}$ 的 LWE 密文（这是加法同态的，不支持乘法同态）
4. 使用 LUT 计算非线性函数，用到的累加器的维度是 $\underline{n}<n<\overline{n}$，得到 $\Delta T(v_i)$ 的 LWE 密文（维度 $n$）
5. 使用 KS 过程（[CDKS21] 的 LWE-to-LWE 算法）将维度缩减到 $\underline{n}<n$ 的 LWE 密文（这是加法同态的，不支持乘法同态）
6. 使用 LT 算法（并非是 Coeff-to-Slot）将这些 LWE 密文重新打包成单个 RLWE 密文（维度 $\overline{n}$），它加密了 $Ecd(As+b\in {\mathbb{Z}}^l,{\Delta }^{\prime })$ 作为明文槽的内容（还没有取模）
7. 利用 mod 算法对各个槽同态取模，最终获得加密了 $Ecd(T(v),\Delta )$ 的 CKKS 密文

LUT for Larger Domain

[MP21] 的 LUT 算法仅支持很小的域，需要限制 $q\mid 2n$，但是 $|\Delta v_i|\le 2^{10}$ 对于 CKKS 方案是远远不够的。Pegasus 采用缩放技术，执行 LUT 获得近似结果。

使用 TFHE/FHEW 自举时，它只能计算模 $2n$（累加器的维度 $n$），但是往往模数 $q?2n$，给定 LWE 密文 $(b,a)\in {\mathbb{Z}}_q^{1+\underline{n}}$，Pegasus 将密文缩放为：
$$\tilde{b}=?\frac{2n}{q}?b?\in {\mathbb{Z}}_{2n},\tilde{a}=?\frac{2n}{q}?a?\in {\mathbb{Z}}_{2n}^{\underline{n}}$$
（缩放的）线性解密可以如下计算：
$$\tilde{b}+?\tilde{a},\underline{s}?(\mathrm{mod}2n)\approx ?\frac{2n}{q}?\mu ?\in \mathbb{Z}$$

Pegasus 丢弃了一半的相位空间（文中没有任何解释，烦啊），以换取函数 $T$ 不必是反循环的。为了正确计算函数 $T(\mu ),\mu \in [?q/4,q/4)$，我们应当对函数进行恰当缩放，
$$\tilde{T}(x)=T\left(\frac{q}{2n}x\right),x\in [?n/2,n/2)\cap \mathbb{Z}$$
假如 $T(\mu )$ 在区间 $[?q/4,q/4)$ 上是 $\kappa$-Lipschitz 的，那么近似误差 $\Vert T(\mu )?\tilde{T}(?2n/q?\mu ?)\Vert \le \kappa q/4n$，只要 $T$ 足够平滑，那么这个误差影响不大。

我们要求输入的 LWE 密文，它所加密的相位满足 $\mu =\Delta m+e\in [?q/4,q/4)$（注意不是 ${\mathbb{Z}}_q$ 整个空间，只有一半），给定 $m\in \mathbb{R}$ 的函数 $T:\mathbb{R}\to \mathbb{R}$，希望输出的 LWE 密文对 $\Delta T(m)$ 加密，令 $k=?2n/q?\mu ?\in [?n/2,n/2)$，因此我们构造 LUT 如下：
$$t_k=\Delta T\left(\frac{q}{2n\Delta }k\right),k=?n/2,?,0,?,n/2?1$$
将这 $n$ 个数值写到多项式 $f\in R_n$ 的系数上（注意反序和符号）：$f_{?k}=t_k,?k\le 0$ 以及 $f_{n?k}=?t_k,?k>0$

使用 [MP21] 的三元秘密的 TFHE 变体，完整的 LUT 算法为：

哎！论文写的令人迷惑，也很少给出合理的解释。我感觉到处是错误，难道是我理解错了？
主要的思路挺好，它的细节就不要钻研了。。。

Repacking via Linear Transform

Chimera 使用的同态线性运算需要几百 GB 的公钥，计算效率极低。Pegasus 给出了新的算法，它只需要几十 MB 的公钥。

Chimera 试图将 $l$ 个 LWE 密文打包到单个 RLWE 密文的明文槽中，它采取了 [MS18] 的 LWE 密文（行矢）堆叠的方案，$a_j$ 组成的矩阵 $A$ 的形状为 $l\times \underline{n}$，我们称 $l>\underline{n}$ 是 “高”，称 $l<\underline{n}$ 是 “矮”。接下来，我们将 $s$ 编码加密在明文槽上 $Ecd(s,\Delta )$，对它做同态线性变换 $\mu =As+b(\mathrm{mod}q)$，同态解密出相位的编码 $Ecd(\mu ,\Delta )$

[HS14] 提出了矩阵-向量乘法的对角线算法，它更加适合方阵的计算。Chimera 使用瓷砖技术（tiling），将 “高矩阵”、“短矩阵” 都抽象地排列为方阵（实际算法中不需要真的构造出方阵），然后采取 [HS18] 的对角线乘法和 BSGS 算法，计算明文槽的任意线性变换。

具体地，我们要求 $l,\underline{n}<\overline{n}$ 都是二的幂次，给定矩阵 $M\in {\mathbb{R}}^{l\times \underline{n}}$，给定 $z\in {\mathbb{Z}}^{\underline{n}}$ 的重复码 $Ecd(z\Vert ?\Vert z,\Delta )$ 的 RLWE 加密，其中的 $z$ 恰好重复了 $\overline{n}/\underline{n}$ 次（没有Padding，这保持同态移位的正确性），

• 方矩阵：$l=\underline{n}$，对角线 $M_j$ 的长度为 $n^{\prime }:=l$，共有 $n^{\prime \prime }:=l$ 条线。不使用 BSGS 技巧，共计需要 $n^{\prime \prime }$ 次秘密 $z$ 的同态移位，分别和 $M_j$ 做阿达玛乘积之后，累加起来就是 $Ecd(Mz)$ 了，其中的 $Mz$ 被重复 $\overline{n}/l$ 次。
• 高矩阵：$l\ge 2\underline{n}$，对角线 $M_j$ 的长度为 $n^{\prime }:=l$，共有 $n^{\prime \prime }:=\underline{n}$ 条线。因为长度为 $\underline{n}$ 的 $z$ 是重复编码的，我们把长度 $l$ 的 $M_j$ 也重复编码（视为$l/\underline{n}$ 个长度 $\underline{n}$ 的瓷砖的拼接的重复），可以观察到 $Ecd(z)\odot Ecd(M_j)$ 恰好就是我们需要的阿达玛积。最后将它们累加起来即可。
• 矮矩阵：$2l\le \underline{n}$，对角线 $M_j$ 的长度为 $n^{\prime }:=\underline{n}$，共有 $n^{\prime \prime }:=l$ 条线。每条对角线 $M_j$ 和 $z?j$ 做阿达玛乘积，再累加起来，其结果是长度 $\underline{n}$ 的向量。可以观察到，每间隔 $l$ 的元素应该做继续累加，获得最终的长度 $l$ 的结果 $Mz$ 的编码。我们采用 “快速广播” 类似的技术，迭代 “旋转 $1,2,4,?$ 个位置，并加到自身” 多次，可将长度 $\underline{n}$ 的中间结果的重复码 归并为 长度 $l$ 的最终结果的重复码。
• 综上所述，$n^{\prime }=\max (l,\underline{n})$，$n^{\prime \prime }=\min (l,\underline{n})$，共需要 $n^{\prime \prime }+\log (\underline{n}/l)$ 次同态移位。如果是高矩阵 $l>\underline{n}$，那么复杂度仅为 $n^{\prime \prime }=\underline{n}$，它和 $l$ 无关（数量越多的 LWE 密文打包，甚至不需要更多代价）。可以采取 BSGS 技巧，将项 $n^{\prime \prime }$ 降低为 $\sqrt{n^{\prime \prime }}$

明文槽的同态线性变换，算法如下：

Framework

综合上述的技术，Pegasus 的整体协议是：

其中的 $g_{digit}[i]=B^i$ 是 [BGV12] 数字分解，$g_{rns}[i]=q^{\prime }q/q_i?[(q/q_i{)}^{?1}{]}_{q_i}$ 是 [BEHZ16] 素数分解。它们都是 Gadget Vector，前者用于 LWE-to-LWE，后者用于 LUT 自举（文中也没解释这么选的原因）。

进一步的优化：

1. step 5, step 6 作为一个 LUT 计算块，可以执行一个 LUT 序列的非线性函数（不必立即回到 CKKS 上）
2. step 4, step 6 获得的 LWE 是线性同态的（不支持同态乘法），可以执行算术加法
3. step 8 中的 $A,b$ 是 LWE 的堆叠，它的次序可以任意排布，从而实现明文槽置换
4. 调整 RK 的模数，可以调节最终输出的 CKKS 层级 $L^{\prime }$

Applications

计算非多项式函数：

1. sigmoid, ReLU
2. min, max
3. max-pool, average-pool
4. min-index, max-index, sorting

机器学习：

1. 决策树
2. 聚类

参数设置以及效率测试：