全同态加密：TFHE

参考文献：

1. Cheon J H, Stehlé D. Fully homomophic encryption over the integers revisited[C]//Advances in Cryptology–EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015: 513-536.
2. Chillotti I, Gama N, Georgieva M, et al. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[C]//Advances in Cryptology–ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, December 4-8, 2016, Proceedings, Part I 22. Springer Berlin Heidelberg, 2016: 3-33.
3. Chillotti I, Gama N, Georgieva M, et al. TFHE: fast fully homomorphic encryption over the torus[J]. Journal of Cryptology, 2020, 33(1): 34-91.
4. TFHE：环面上全同态加密方案学习笔记

TFHE 是 FHEW 的改进，主要的优化思路是：使用 LWE 与 GSW 的"外积"，取代 GSW 与 GSW 的“内积”，从而使得计算复杂度降低了一个多项式因子。

Real Torus

令 $(R,+,\times )$ 是一个交换环，一个集合 $M$ 叫做 $R$ - (左) 模，如果 $(M,+)$ 是一个阿贝尔群，并且存在一个bi-distributive（双分布？）、homogeneous（齐次）的 external operation (product)，$\cdot :R\times M\to M$，即：对于任意的 $r,s\in R$ 和 $x,y\in M$，都有，

• $1_R\cdot x=x$
• $(r+s)\cdot x=r\cdot x+s\cdot x$
• $r\cdot (x+y)=r\cdot x+r\cdot y$
• $(r\times s)\cdot x=r\cdot (s\cdot x)$

令 $\mathbb{T}:=\mathbb{R}/\mathbb{Z}$ 是集合 {r(mod1):r∈R}\{r \pmod 1: r \in \mathbb R\}{r(mod1):r∈R}，这叫做实数环面（real Torus）。由于 mod 1 projection 与 real product 不兼容（例如，$0_{\mathbb{T}}\times 0.5_{\mathbb{T}}$ 是未定义的，容易验证 $0\times 0.5\ne 1\times 0.5$），因此 Torus 不是 Ring。不过，容易发现 $\mathbb{T}$ 是个 $\mathbb{Z}$-模（比如，$0_{\mathbb{Z}}\cdot 0.5_{\mathbb{T}}=0_{\mathbb{T}}$ 是 well define 的）。

简记 ${\mathbb{T}}_N[X]:=\mathbb{R}[X]/(X^N+1,1)$，${\mathbb{Z}}_N[X]:=\mathbb{Z}[X]/(X^N+1)$，易知 $({\mathbb{T}}_N[X{]}^k,+,\cdot )$ 是一个 ${\mathbb{Z}}_N[X]$-模。

同时，如果 $M$ 是个 $R$-模，那么它的向量或矩阵 ${\mathcal{M}}_{n,m}(M)$ 也是 $R$-模。因此，${\mathcal{M}}_{n,m}(\mathbb{T})$ 是 $\mathbb{Z}$-模，${\mathcal{M}}_{n,m}({\mathbb{T}}_N[X{]}^k)$ 是 ${\mathbb{Z}}_N[X]$-模。

令 B:={0,1}⊂Z\mathbb B := \{0,1\} \subset \mathbb ZB:={0,1}⊂Z，简记 ${\mathbb{B}}_N[X]:=\mathbb{B}[X]/(X^N+1)\subset {\mathbb{Z}}_N[X]$

一般来说， distributions over the torus do not have expectation nor variance（例如，均匀分布）。但是，如果分布 $\chi$ 是集中的（concentrated，它的 support 包含在 $\mathbb{T}$ 上的某个半径 $\frac{1}{4}$ 的球内），那么还是可以定义期望和方差的：

• $Var(\chi ):={\min }_{\bar{x}\in \mathbb{T}}\sum \chi |x-\bar{x}{|}^2$
• $E(\chi ):=\arg {\min }_{\bar{x}\in \mathbb{T}}\sum \chi |x-\bar{x}{|}^2$

我们说 ${\mathbb{T}}^n$ 或者 ${\mathbb{T}}_N[X{]}^k$ 上的分布 ${\chi }^{\prime }$ 是集中的，当今当它的每一个系数都是独立的集中的分布。类似于实数域上的性质，对于 $e_1,e_2\in \mathbb{Z}$，集中分布的线性组合 $\chi =e_1\cdot {\chi }_1+e_2\cdot {\chi }_2$，它也是集中的，并且

1. $E(\chi )=e_1\cdot E({\chi }_1)+e_2\cdot E({\chi }_2)$
2. $Var(\chi )\le e_1^2\cdot Var({\chi }_1)+e_2^2\cdot Var({\chi }_2)$

对于 ${\mathbb{T}}^k$ 上的向量 $x$，我们定义
$$\Vert x{\Vert }_p:=\underset{u\in x+{\mathbb{Z}}^k}{\min }(\Vert u{\Vert }_p)$$

满足三角不等式，但它不是范数：${\mathbb{T}}^k$ 不是向量空间，且 $\Vert \cdot {\Vert }_p$ 不是齐次的。不过 $\Vert \cdot {\Vert }_p$ 是 sub-homogeneous 的，$\Vert m\cdot x{\Vert }_p\le |m|\Vert x{\Vert }_p,\forall m\in \mathbb{Z}$。对于多项式 $P\in {\mathbb{T}}_N[X]$，定义 $\Vert P{\Vert }_p:=\Vert \vec{P}{\Vert }_p$，其中 $\vec{P}\in [-0.5,0.5{]}^N$ 是它的系数表示。

对于矩阵 $A\in {\mathcal{M}}_{p,q}({\mathbb{T}}_N[X])$，我们定义
$$\Vert A{\Vert }_{\infty }:=\underset{i,j}{\max }\Vert a_{i,j}{\Vert }_{\infty }$$

Lipschitz function：我们说函数 $f:{\mathbb{T}}^m\to {\mathbb{T}}^n$ 是 $\kappa$-Lipschitz 的，如果满足
$$\Vert f(x)-f(y){\Vert }_{\infty }\le \kappa \Vert x-y{\Vert }_{\infty },\forall x,y$$

即任意两点间的连线斜率是“一致有界”的，上界 $\kappa$ 叫做 Lipschitz 常数。

Scale-Invariant LWE

FHEW 采用了 Cheon 等人提出的 Scale-Invariant LWE 变体（回顾下 BFV 中的除以模数）：令秘密 $s\in {\mathbb{Z}}^n$，令 $\xi$ 是实数域 $\mathbb{R}$ 上的错误分布，定义 $LW{E}_{s,\xi }$ 是 ${\mathbb{T}}^n\times \mathbb{T}$ 上的分布，样本形如 $(a,b)$，其中 $a\in {\mathbb{T}}^n$ 是均匀随机的，错误 $e\leftarrow \xi$，计算 $b:=s\cdot a+e$（先是环作用，然后是群加法）。类似一般的 LWE 问题，这个变体也分为 Search 和 Decision 两个版本。

我们称 phase（相位）是一个关于秘密 $s$ 的线性函数 ${\varphi }_s:{\mathbb{T}}^n\times \mathbb{T}\to \mathbb{T}$，定义为 ${\varphi }_s(a,b):=b-s\cdot a$，容易看出 $LW{E}_{s,\xi }$ 就是 ${\varphi }_s$ 的 kernel 的近似 ${\varphi }_s(LW{E}_{s,\xi })=e\approx 0$

由于 ${\varphi }_s(a,b)=\mu$ 的一个 trivial preimage 是 $(0^n,\mu )$，根据线性关系，
$${\varphi }_s(LW{E}_{s,\xi }+(0^n,\mu ))=e+\mu \approx \mu \in \mathbb{T}$$

因此，我们可以构造一个 symmetric-key variant Regev’s encryption scheme，定义明文空间为离散集合 $M\in \mathbb{T}$（例如 {0,0.5}\{0,0.5\}{0,0.5}），加密为 $En{c}_s(\mu \in M):=LW{E}_{s,\xi }+(0^n,\mu )$，解密为 $De{c}_s(c\in {\mathbb{T}}^{n+1}):=round({\varphi }_s(c),M)$。只要 $\xi$ 的高斯参数 $\alpha =O(R/\sqrt{p})$（对应的标准差为 $\sigma =\alpha \sqrt{2\pi }$），则解密正确的概率是压倒性的 $1-2^{-p}$，其中 $R$ 是 $M$ 的 packing radius。

如果想要得到 asymmetric variant 的方案，只需要将公钥 $pk$ 定义为随机 $LW{E}_{s,\xi }$ 的样本列表，加密算法中的 $LW{E}_{s,\xi }$ 简单地修改为 small random subset sum ${\sum }_{i\in I}p{k}_i$，而解密算法不变。

TLWE

TFHE 定义了一个抽象的 Scale-Invariant Generalization LWE over the Torus，它可以被实例化为多种问题：LWE、RLWE、MLWE 以及 Approx-GCD、NTRU。

Abstract TLWE problems：令 $I\subseteq \mathbb{Z}[X]$ 是一个理想，定义 $\mathfrak{R}:=\mathbb{Z}[X]/I$，${\mathbb{T}}_I[X]:=\mathbb{T}[X]/I$，函数 phase 是一族 Lipschitz morphism（态射）{ϕs:RM→TI[X]}S\{\phi_s:{}_\mathfrak R M \to \mathbb T_I[X]\}_S{ϕs​:R​M→TI​[X]}S​。我们说 general TLWE problem 是由 ${}_{\mathfrak{R}}M$ 上的错误分布 $\xi$、一族由秘密 $s$ 索引的态射 {ϕs}S\{\phi_s\}_S{ϕs​}S​ 所指定的。我们定义 homogeneous TLWE distribution 为 ${\mathcal{U}}_{\ker ({\varphi }_s)}+\xi$，并可定义 Search 和 Decision 两个版本的问题。

1. 如果设置 $I=(X+1)$，那么 $\mathfrak{R}=\mathbb{Z},{\mathbb{T}}_I[X]=\mathbb{T}$，
   1. 设置 $M={\mathbb{T}}^{n+1}$ 以及 ${\varphi }_s(a,b)=b-s\cdot a$​，其中 $S\subseteq {\mathbb{Z}}^n$，那么这是 scale-invariant LWE
   2. 设置 $M={\mathbb{Z}}_q^{n+1}$ 以及 ${\varphi }_s(a,b)=(b-s\cdot a)/q$，其中 $S\subseteq {\mathbb{Z}}_q^n$，那么这是 LWE mod q
   3. 设置 $M=\mathbb{T}$ 以及 ${\varphi }_p(x)=p\cdot x$，其中 $S\subseteq \mathbb{Z}$，那么这是 (dual) approx-GCD problem
2. 如果设置 $I=(X^N+1)$，那么 $\mathfrak{R}={\mathbb{Z}}_N[X],{\mathbb{T}}_I[X]={\mathbb{T}}_N[X]$，
   1. 设置 $M={\mathbb{T}}_N[X{]}^2$ 以及 ${\varphi }_s(a,b)=b-s\cdot a$，其中 $S\subseteq {\mathbb{Z}}_N[X]$，那么这是 Ring LWE
   2. 设置 $M={\mathbb{T}}_N[X{]}^{k\times (k+1)}$ 以及 ${\varphi }_s(a,b)=b-s\cdot a$，其中 $S\subseteq {\mathbb{Z}}_N[X{]}^k$，那么这是 Module LWE
   3. 设置 $M={\mathbb{T}}_N[X{]}^2$ 以及 ${\varphi }_{f,g}(x,y)=fx-gy$，其中 $S\subseteq {\mathbb{Z}}_N[X{]}^2$，那么这是 scale invariant NTRU

接下来，TFHE 定义了一个典范的 TLWE。

Canonical T®LWE problem：令 $k\ge 1$ 是正整数，$N\in {\mathbb{Z}}^{+}$ 是 $2$ 的幂次，$\alpha \in {\mathbb{R}}_{\ge 0}$ 是标准差。密钥空间 $S={\mathbb{B}}_N[X{]}^k$，其中的 $s$ 是 $n\approx kN$ 比特均匀随机数。相位 ${\varphi }_s$ 是定义在 $M={\mathbb{T}}_N[X{]}^k\times {\mathbb{T}}_N[X]$ 上的 $n$-Lipschitz 函数 ${\varphi }_s(a,b)=b-s\cdot a$，错误分布为 $\xi =(0^k,D_{{\mathbb{T}}_N[X],\alpha })$，那么一个齐次 TLWE 样本就形如 $(a,s\cdot a+e)\in M$，其中的 mask 取自 $a\leftarrow {\mathcal{U}}_{{\mathbb{T}}_N[X{]}^k}$，error 取自 $e\leftarrow D_{{\mathbb{T}}_N[X],\alpha }$

• 我们说一个样本是 trivial 的，如果 $a=0$，此时的样本形如 $(0^k,e)$

• 我们说一个样本是 noiseless 的，如果 $\alpha =0$，此时的样本形如 $(a,s\cdot a)$

现在，Regev’s cryptosystem 可以被抽象为：

1. 秘钥空间为 ${\varphi }_s$ 的 index $\mathfrak{R}:=\mathbb{Z}[X]/I$
2. 消息空间为 ${\varphi }_s$ 的 image ${\mathbb{T}}_I[X]:=\mathbb{T}[X]/I$
3. 密文空间为 ${\varphi }_s$ 的 domain ${}_{\mathfrak{R}}M$
4. 消息 $\mu$ 的密文是 random preimage 的近似 ${\mathcal{U}}_{{\varphi }_s^{-1}(\mu )}+\xi$，对于 Canonical Form 来说就是 ${\mathcal{U}}_{\ker ({\varphi }_s)}+\xi +(0^k,\mu )$
5. 密文 $c$ 的（近似的）明文是它的 image ${\varphi }_s(c)$

由于上述方案的解密结果是带噪的，适合于浮点数计算或者差分隐私（differential privacy）。如果需要精确值，有两种选择：

1. 第一种，限制消息空间为 discrete subset，并使得 packing radius 大于 $\xi$ 的振幅，从而可以使用园整运算获得精确值。但是，这使得非线性运算的正确性分析较为复杂，并且离散后的阿贝尔群的空间太小了。
2. 第二种，限制噪声期望为 $E(\xi )=0$，从而明文就是期望值 $E({\varphi }_s(c))$。这使得噪声分析变得简单，同时可以支持无限精度的连续明文空间。

TFHE 使用第一种方案来评估 worst case 的噪声，使用第二种方案来评估 average case 的噪声。首先需要定义一个概率空间 $\Omega$，并将 TLWE 样本视为一个随机分布，而非某个数值。我们说 $c\in {\mathbb{T}}_N[X{]}^{k+1}$ 是一个 valid TLWE sample，当仅当 ${\varphi }_s(c)$ 在 $\Omega$ 上是集中分布的。接下来定义，

• 消息 $msg(c):=E({\varphi }_s(c))$
• 噪声 $Err(c):={\varphi }_s(c)-msg(c)$
• 方差 $Var(Err(c)):=Var({\varphi }_s(c))$
• 振幅 $\Vert Err(c){\Vert }_{\infty }$ 定义为满足 $Pr[Err(c)\ge B]=negl(\lambda )$ 的最大振幅（maximum amplitude）

根据相位的线性关系，对应组合系数 $e_i\in \mathfrak{R}$，密文 $c={\sum }_I{e}_i\cdot c_i$ 满足以下关系：

1. $msg(c)={\sum }_I{e}_i\cdot msg(c_i)$，
2. $Var(Err(c))\le {\sum }_I\Vert e_i{\Vert }_2^2\cdot Var(Err(c_i))$
3. $\Vert Err(c){\Vert }_{\infty }\le {\sum }_I\Vert e_i{\Vert }_1\cdot \Vert Err(c_i){\Vert }_{\infty }$

TGSW

由于 LWE 密文适合线性运算，但对于非线性运算似乎少了些属性（when it comes to non linear operations on the samples, TLWE seems to miss some properties）。最知名的两种解决方案是：BGV constructions 和 GSW constructions，TFHE 关注 GSW 的一个 Torus 上的 generalized scale invariant version 的变体。

为了控制噪声增长，TFHE 给出了一个 approximate decomposition（实数的有限精度的近似分解）。首先给出一个抽象概念，之后再给出一个典范。

Abstract Gadget Decomposition：令 $M$ 是一个 $\mathfrak{R}$-模，分解算法是一个有效的算法 $De{c}_{H,\beta ,ϵ}(v)$，其中 $H\in M^{l^{\prime }}$ 是 gadget，$\beta \in {\mathbb{R}}_{>0}$ 是 quality，$ϵ\in {\mathbb{R}}_{>0}$ 是 precision，它将任意的 TLWE 样本 $v\in M$ 分解为一个（随机的） small 向量 $u\in {\mathfrak{R}}^{l^{\prime }}$，使得 $\Vert u{\Vert }_{\infty }\le \beta$ 以及 $\Vert u\cdot H-v{\Vert }_{\infty }\le ϵ$，并且期望 $E_v(u\cdot H-v)=0$

分解算法本应是随机的，但是根据 Independence Heuristic，可以近似地认为各个系数服从独立随机的集中分布，因此也可以直接使用确定性的算法。

Canonical Gadget Decomposition：对于 Canonical TLWE 样本，我们设置 $M={\mathbb{T}}_N[X{]}^{k+1}$，令 $l,B_g$ 是正整数，并设置 $l^{\prime }=(k+1)l$，那么 Gadget $H\in M^{l^{\prime }}={\mathcal{M}}_{l^{\prime },k+1}({\mathbb{T}}_N[X])$ 定义为
$$H=\left[\begin{array}{ccccc}{B}_g^{-1}& 0& \cdots & 0& 0\\ B_g^{-2}& & \cdots & & 0\\ ⋮& & ⋮& & ⋮\\ B_g^{-l}& 0& \cdots & 0& 0\\ ⋮& & \ddots & & ⋮\\ 0& 0& \cdots & 0& B_g^{-1}\\ 0& & \cdots & & B_g^{-2}\\ ⋮& & ⋮& & ⋮\\ 0& 0& \cdots & 0& B_g^{-l}\end{array}\right]\in M^{(k+1)l}$$

它包含 $l^{\prime }=(k+1)l$ 个 ${}_{\mathfrak{R}}M$ 中的元素，乘以系数 $u\in {\mathfrak{R}}^{l^{\prime }}$ 后将组合出一个 ${}_{\mathfrak{R}}M$ 中的元素 $v$，并且 $\beta =B_g/2$，$ϵ=B_g^{-l}/2$（就是 $B_g$ 进制的浮点小数的有限精度表示）

近似分解算法 $De{c}_{H,\beta ,ϵ}:M\to {\mathfrak{R}}^{l^{\prime }}$ 定义如下：

接下来，我们定义 TGSW 样本。首先是抽象描述，接下来是典范描述。

Abstract TGSW samples：回顾 Abstract TLWE samples 中的 $\xi ,{\varphi }_s,{}_{\mathfrak{R}}M$，以及 $H\in M^{l^{\prime }}$ 对应的 $De{c}_{H,\beta ,ϵ}$，我们说 $C\in M^{l^{\prime }}$ 是一个关于 $\mu \in \mathfrak{R}$ 的fresh TGSW sample，当仅当 $C=Z+\mu \cdot H$，其中 $Z\in M^{l^{\prime }}$ 的每个 element 都是一个关于 $s\in {\mathbb{B}}_N[X{]}^k$ 的齐次 TLWE 样本。我们说 $C$ 是一个 valid TGSW sample，当仅当存在一个 $\mu \in \mathfrak{R}$ 使得 $C-\mu \cdot H$ 的每个 element 都是 valid TLWE sample。另外，我们将 TLWE 的相位扩展为 ${\varphi }_s(C)\in {\mathbb{T}}_I[X{]}^{l^{\prime }}$，它的每个分量就是对 $C$ 的各个 element 分别计算相位。

Canonical T®GSW samples：回顾 Canonical TLWE samples 以及 Canonical Gadget Decomposition 中的各个参数的设置，秘密 $s\in {\mathbb{B}}_N[X{]}^k$，那么对应的 T®GSW 样本为 $C\in M^{l^{\prime }}={\mathcal{M}}_{(k+1)l,k+1}({\mathbb{T}}_N[X])$，它包含 $(k+1)l$ 行，且 $C-\mu \cdot H$ 的每一行都是 ${\mathbb{T}}_N[X{]}^{k+1}$ 上的齐次 T®LWE 样本。

根据 phase 的线性，对于组合系数 $e_i\in \mathfrak{R}$，$C={\sum }_I{e}_i\cdot C_i$ 是 $\mu ={\sum }_I{e}_i\cdot {\mu }_i$ 的密文，并且
$$\begin{array}{rl}Var(C)& \le \sum _I\Vert e_i{\Vert }_2^2\cdot Var(C_i)\\ \Vert Err(C){\Vert }_{\infty }& \le \sum _I\Vert e_i{\Vert }_1\cdot \Vert Err(C_i){\Vert }_{\infty }\end{array}$$

另外，如果 $s$ 是二元系数的，那么任意的 $A\in {\mathcal{M}}_{p,k+1}({\mathbb{T}}_N[X])$，都有
$$\Vert {\varphi }_s(A){\Vert }_{\infty }\le (1+kN)\Vert A{\Vert }_{\infty }$$

也就是说，Canonical TGSW samples 中定义的 ${\varphi }_s$ 是一族 $(1-kN)$-Lipschitz 函数。

Operators

Products

TFHE 观察到，GSW 的不对称性有两个方面，

1. 如 AP14 所描述的噪声增长的不对称性，这可以支持长链乘法。
2. 解密操作的不对称性，即大部分运算是不必要的，只有所谓 “big coefficient” 对应的那一个 LWE 样本被用于解密出明文。

External product：我们定义（右结合）算符 $⊡$ 为
$$\begin{array}{rl}⊡:TGSW\times TLWE& \to TLWE\\ (A\in {}_{\mathfrak{R}}{M}^{l^{\prime }},b\in {}_{\mathfrak{R}}M)& \mapsto De{c}_{H,\beta ,ϵ}(b)\cdot A\in {}_{\mathfrak{R}}M\end{array}$$

容易验证它是 ${\mu }_A\cdot {\mu }_b$ 的密文。噪声分析如下，

而 GSW 的“内积”可以被视为多个“外积”组成的向量。

Internal Product：我们定义（右结合）算符 $⊠$ 为
$$\begin{array}{rl}⊠:TGSW\times TGSW& \to TGSW\\ (A\in {}_{\mathfrak{R}}{M}^{l^{\prime }},B\in {}_{\mathfrak{R}}{M}^{l^{\prime }})& \mapsto \left[\begin{array}{c}A⊡b_1\\ A⊡b_2\\ ⋮\\ A⊡b_{l^{\prime }}\end{array}\right]\in {}_{\mathfrak{R}}{M}^{l^{\prime }}\end{array}$$

容易验证它是 ${\mu }_A\cdot {\mu }_B$ 的密文，噪声分析与 External product 基本一致。

Key Switching

TFHE 扩展了秘钥切换的概念，定义了 TLWE 上的关于 $R$-Lipschitz 的线性态射 $f:{}_{\mathbb{Z}}{\mathbb{T}}^p\to {\mathbb{T}}_N[X]$ 的秘钥切换。假设从 $\mathfrak{K}\in {\mathbb{B}}^n$ 下的密文 $\mathfrak{c}$，切换到 $K\in {\mathbb{B}}_N[X{]}^k$ 下的密文 $c$。

对于公开的态射 $f$，秘钥切换的例程为 $PubKS(f,KS,\mathfrak{c})$，如图：

它的输出为 $c\in T(R)LW{E}_K(f({\mu }_1,\cdots ,{\mu }_p))$，噪声分析为

对于秘密的态射 $f$，方便起见使用增广形式的私钥（第 $n+1$ 分量置为 $-1$），此时 ${\varphi }_{\mathfrak{K}}(\mathfrak{c})=-\mathfrak{K}\cdot \mathfrak{c}$。秘钥切换的例程为 $PrivKS(K{S}^{(f)},\mathfrak{c})$，如图：

它的输出为 $c\in T(R)LW{E}_K(f({\mu }_1,\cdots ,{\mu }_p))$，噪声分析为

Simple Extraction

由于 T®LWE 或 T®GSW 的消息空间是 ${\mathbb{T}}_N[X]$，因此它包含 $N$ 个环面 $\mathbb{T}$ 上的槽（slot）。

对于 $n=kN$，LWE 的秘钥 $\mathfrak{K}\in {\mathbb{B}}^n$ 和 RLWE 的秘钥 $K\in {\mathbb{B}}_N[X{]}^k$ 可以相互转化（对应于同样的 $n$ 长二元向量表示），并且 RLWE 的密文可以被视作是：LWE 密文的第一分量不断反循环移位，从而获得一系列的 LWE 密文的第二分量（仔细想一下 ${\mathbb{T}}_N[X]$ 被 ${\mathbb{Z}}_N[X]$ 环作用，其中理想为 $I=(X^N+1)$）

给定 RLWE 样本 $c=(a,b)\in RLW{E}_K(\mu )$ 以及位置 $p\in [N]$，我们定义 $SimpleExtrac{t}_p(c)$ 的输出是一个 LWE 样本 $\mathfrak{c}=(\mathfrak{a},\mathfrak{b})\in LW{E}_{\mathfrak{K}}({\mu }_p)$，
$$\begin{array}{rl}{\mathfrak{a}}_{N(i-1)+j}& :=a_i[p-j],i\in [k]\\ \mathfrak{b}& :=b_p\end{array}$$

其中 $a_i\in {\mathbb{T}}_N[X]$ 使用 $N$-antiperiodic indexes 的系数向量表示，即 $a_i[j]$ 是 $X^{N-j}$ 的系数。

Blind Rotate

有时候旋转一个多项式（乘以 $X^i$）是有必要的。如果旋转程度被 LWE 加密 $(a,b)\in {\mathbb{Z}}^{p+1}$，多项式被 RLWE 加密 $c\in {\mathbb{T}}_N[X]$，盲旋转的算法如下：

其输出为 $ACC\in TRLW{E}_K(X^{⟨s,a⟩-b}\cdot v)$，噪声分析为

LHE & FHE

TFHE 先提出了一个 LHE 的自动机模型：布尔门电路，使用 TGSW 密文作为控制线，使用 TLWE 密文作为数据线。然后使用“外积”来计算 Bootstrapping，这比使用“内积”的 FHEW 快一个小多项式因子。

还有 随机函数查找表、水平打包、垂直打包 等等技术。

作者没细看，略啦 (づ｡◕ᴗᴗ◕｡)づ