TFHE 的全同态模结构（FHE Module Structure）

参考文献：

1. [CGGI20] 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.
2. [BGGJ20] Boura C, Gama N, Georgieva M, et al. Chimera: Combining ring-lwe-based fully homomorphic encryption schemes[J]. Journal of Mathematical Cryptology, 2020, 14(1): 316-338.

Notation

代数结构：

• 实数环面 $\mathbb{T}=\mathbb{R}/\mathbb{Z}=[0,1)$
• 整系数多项式环 $R=\mathbb{Z}[x]/(x^N+1)$
• 系数取自整环 A ∈ { Z , R , C } A \in \{\mathbb Z,\mathbb R,\mathbb C\} A∈{Z,R,C}，多项式环 $R_A=R{\otimes }_{\mathbb{Z}}A=A[x]/(x^N+1)$
• 商环 $R_q=R/qR={\mathbb{Z}}_q[x]/(x^N+1)$，自然满射 ${\pi }_q:R\to R_q$ 是同态
• 商群 ${\mathbb{T}}_R=R_{\mathbb{R}}/R_{\mathbb{Z}}=\mathbb{T}[x]/(x^N+1)$，它是 $R$ 左模（但不是环），环 $R$ 左作用模 ${\mathbb{T}}_R$ 称为 “外积”

Lipschitz 函数：斜率绝对值不大于 $\kappa$，因此被两个一次函数夹逼。

集中分布（concentrated distributions）：除了可忽略的测度，概率分布的支撑集是某个半径 $1/2$ 球体的子集；此时，这个实数环面上的概率分布是良的，存在良定义的期望、标准差。

TLWE

底层的代数结构，

• 秘钥空间：$\mathcal{B}\subseteq {\mathbb{Z}}^N$，小范数的整数向量集合
• 明文空间：$\mathbb{T}$，是 $\mathbb{Z}$ 模（不是环，乘法未定义）
• 密文空间：${\mathbb{T}}^N\times \mathbb{T}={\mathbb{T}}^{N+1}$，是 $\mathbb{Z}$ 模（无法被 $\mathbb{T}$ 作用，同态乘法不自然）
• 相位函数：${\varphi }_s:(a,b)\mapsto b-s^{t}a$，是 $\kappa$ Lipschitz 函数，其中 $\kappa$ 很小（关于环面上 $l_{\infty }$ 范数）

不考虑（具有同态性质的）纠错码，

对称密钥：

1. 均匀采样 $s\leftarrow \mathcal{B}$，它是整系数的短向量

加密：

1. 明文 $\mu \in \mathbb{T}$
2. 均匀采样 $a\leftarrow {\mathbb{T}}^N$，零中心高斯采样 $e\leftarrow \mathbb{T}$
3. 计算 $b:=s^{t}a+e\in \mathbb{T}$，满足 ${\varphi }_s(a,b)=e\approx 0$
4. 密文 $c:=(a,b)+(0,\mu )$，是长度 $N+1$ 的列向量

解密：

1. 密文 $(a,b^{\prime })\in {\mathbb{T}}^N\times \mathbb{T}$
2. 计算 ${\varphi }_s(a,b^{\prime })=e+\mu \in \mathbb{T}$
3. 带噪明文 $\mu +e$ 是一个随机变量，均值是 $\mu$

同态运算：

1. 根据 $\mathbb{Z}$ 模的加法，${\mu }_1+{\mu }_2⟺c_1+c_2$
2. 根据 $\mathbb{Z}$ 模的环作用，$k\cdot \mu ⟺k\cdot c$，其中 $k\in \mathbb{Z}$
3. 不支持乘法运算，BGV 的密文张量积不自然，${\mu }_1{\mu }_2⟺s^t{c}_1\cdot s^t{c}_2=s^t{c}_1\otimes s^t{c}_2=(s\otimes s{)}^t\cdot (c_1\otimes c_2)$

TRLWE

底层的代数结构，

• 秘钥空间：$\mathcal{B}\subseteq R$，小范数的整系数多项式集合
• 明文空间：${\mathbb{T}}_R$，是 $R$ 模（不是环，乘法未定义）
• 密文空间：${\mathbb{T}}_R\times {\mathbb{T}}_R={\mathbb{T}}_R^2$，是 $R$ 模（无法被 ${\mathbb{T}}_R$ 作用，同态乘法不自然）
• 相位函数：${\varphi }_s:(a,b)\mapsto b-s\cdot a$，是 $\kappa$ Lipschitz 函数，其中 $\kappa$ 很小（关于环面上 $l_{\infty }$ 范数）

不考虑（具有同态性质的）纠错码，

对称密钥：

1. 均匀采样 $s\leftarrow \mathcal{B}$，它是短的整系数多项式

加密：

1. 明文 $\mu \in {\mathbb{T}}_R$
2. 均匀采样 $a\leftarrow {\mathbb{T}}_R$，零中心高斯采样 $e\leftarrow {\mathbb{T}}_R$
3. 计算 $b:=s\cdot a+e\in {\mathbb{T}}_R$，满足 ${\varphi }_s(a,b)=e\approx 0$
4. 密文 $c:=(a,b)+(0,\mu )$，是长度 $2$ 的列向量

解密：

1. 密文 $(a,b^{\prime })\in {\mathbb{T}}_R\times {\mathbb{T}}_R$
2. 计算 ${\varphi }_s(a,b^{\prime })=e+\mu \in {\mathbb{T}}_R$
3. 带噪明文 $\mu +e$ 是一个随机变量，均值是 $\mu$

同态运算：

1. 根据 $R$ 模的加法，${\mu }_1+{\mu }_2⟺c_1+c_2$
2. 根据 $R$ 模的环作用，$k\cdot \mu ⟺k\cdot c$，其中 $k\in R$
3. 不支持乘法运算，BFV 的密文多项式乘积不自然，${\mu }_1{\mu }_2⟺c_1(s)\cdot c_2(s)=(c_1\cdot c_2)(s)$

TGSW

底层的代数结构，

• 秘钥空间：$\mathcal{B}\subseteq {\mathbb{Z}}^N$，小范数的整数向量集合
• 明文空间：$\mathbb{Z}$，是整数环（定义了乘法）
• 密文空间：${\mathbb{T}}^{N\times (N+1)l}\times {\mathbb{T}}^{Nl}={\mathbb{T}}^{(N+1)\times (N+1)l}$，是 $\mathbb{Z}$ 模（同态乘法自然）
• 相位函数：${\varphi }_s:(A,b)\mapsto b-s^{t}A$，是 $\kappa$ Lipschitz 函数，其中 $\kappa$ 很小（关于环面上 $l_{\infty }$ 范数）

采用 Gadget 纠错码，设置行向量 $g=[2^{-1},2^{-2},\cdots ,2^{-l}]$，其中 $\alpha =2^{-l}$ 是实数环面的离散化精度 $2^{-l}\mathbb{Z}/\mathbb{Z}\subseteq \mathbb{T}$，
G = I N + 1 ⊗ g = [ g g ⋱ g ] ∈ Z ( N + 1 ) × ( N + 1 ) l G = I_{N+1} \otimes g = [gg⋱g]

\in \mathbb Z^{(N+1) \times (N+1)l} G=IN+1​⊗g= ​g​g​⋱​g​ ​∈Z(N+1)×(N+1)l

对应的逆变换 $G^{-1}$ 是个随机化程序，满足 $\Vert G{G}^{-1}(C)-C{\Vert }_{\infty }\le \alpha /2$，对于任意的 $C\in {\mathbb{T}}^{(N+1)\times (N+1)l}$

对称密钥：

1. 均匀采样 $s\leftarrow \mathcal{B}$，它是整系数的短向量

加密：

1. 明文 $\mu \in \mathbb{Z}$，编码为有限精度的环面矩阵 $\mu G\in {\mathbb{T}}^{(N+1)\times (N+1)l}$
2. 均匀采样 $A\leftarrow {\mathbb{T}}^{N\times (N+1)l}$，零中心高斯采样 $e\leftarrow {\mathbb{T}}^{(N+1)l}$（行向量）
3. 计算 $b:=s^{t}A+e\in {\mathbb{T}}^{(N+1)l}$（行向量），满足 ${\varphi }_s(A,b)=e\approx 0$
4. 密文 $c:=\left[\begin{array}{c}A\\ b\end{array}\right]+\mu G$，基本是 $(N+1)l$ 个 TLWE 密文的组合（除了纠错码不同）

解密：

1. 密文 $\left[\begin{array}{c}{A}^{\prime }\\ b^{\prime }\end{array}\right]\in {\mathbb{T}}^{(N+1)\times (N+1)l}$
2. 计算 ${\varphi }_s(A^{\prime },b^{\prime })=e+\mu (-s,1)G\in {\mathbb{T}}^{(N+1)l}$（行向量）
3. 截取长度 $l$ 的尾巴，得到的 $e^{\prime }+\mu g\in {\mathbb{T}}^l$ 是含噪码字，均值 $\mu g$

同态运算：

1. 根据 $\mathbb{Z}$ 模的加法，${\mu }_1+{\mu }_2⟺c_1+c_2$

2. 根据 $\mathbb{Z}$ 模的环作用，$k\cdot \mu ⟺k\cdot c$，其中 $k\in \mathbb{Z}$

3. 同态乘法，明文空间 ${\mu }_1\in \mathbb{Z}$ 对于密文空间 $G^{-1}({\mu }_{2}G)\in {\mathbb{T}}^{(N+1)\times (N+1)l}$ 的环作用，
      C 1 ⋅ G − 1 ( C 2 ) =    ( ( A 1 , b 1 ) + μ 1 G ) ⋅ G − 1 ( ( ( A 2 , b 2 ) + μ 2 G ) ) =    ( ( A 1 , b 1 ) ⋅ G − 1 ( C 2 ) + μ 1 C 2 ) + μ 1 μ 2 G C1⋅G−1(C2)=((A1,b1)+μ1G)⋅G−1(((A2,b2)+μ2G))=((A1,b1)⋅G−1(C2)+μ1C2)+μ1μ2G

   ==​C1​⋅G−1(C2​)((A1​,b1​)+μ1​G)⋅G−1(((A2​,b2​)+μ2​G))((A1​,b1​)⋅G−1(C2​)+μ1​C2​)+μ1​μ2​G​

   它的噪声增长是不平衡的，导出了乘法链的右结合性。

TRGSW

底层的代数结构，

• 秘钥空间：$\mathcal{B}\subseteq R$，小范数的整系数多项式集合
• 明文空间：$R$，是整系数多项式环（定义了乘法）
• 密文空间：${\mathbb{T}}_R^{2l}\times {\mathbb{T}}_R^{2l}={\mathbb{T}}_R^{2\times 2l}$，是 $R$ 模（同态乘法自然）
• 相位函数：${\varphi }_s:(A,b)\mapsto b-sA$，是 $\kappa$ Lipschitz 函数，其中 $\kappa$ 很小（关于环面上 $l_{\infty }$ 范数）

采用 Gadget 纠错码，设置 $g=[2^{-1},2^{-2},\cdots ,2^{-l}]$ 是行向量，其中 $\alpha =2^{-l}$ 是环面的离散化精度 $2^{-l}{R}_{\mathbb{Z}}/R_{\mathbb{Z}}\subseteq {\mathbb{T}}_R$，
G = g ⊗ I 2 = [ 2 − 1 I , 2 − 2 I , ⋯   , 2 − l I ] ∈ T R 2 × 2 l G = g \otimes I_2 = [2−1I,2−2I,⋯,2−lI]

\in \mathbb T_R^{2 \times 2l} G=g⊗I2​=[2−1I,2−2I,⋯,2−lI​]∈TR2×2l​

对应的逆变换 $G^{-1}$ 是个随机化程序，满足 $\Vert G{G}^{-1}(C)-C{\Vert }_{\infty }\le \alpha /2$，对于任意的 $C\in {\mathbb{T}}_R^{2l\times 2}$

对称密钥：

1. 均匀采样 $s\leftarrow \mathcal{B}$，它是短的整系数多项式

加密：

1. 明文 $\mu \in R$，编码为有限精度的环面矩阵 $\mu G\in {\mathbb{T}}_R^{2\times 2l}$
2. 均匀采样 $A\leftarrow {\mathbb{T}}_R^{2l}$（行向量），零中心高斯采样 $e\leftarrow {\mathbb{T}}_R^{2l}$（行向量）
3. 计算 $b:=sA+e\in {\mathbb{T}}_R^{Nl}$（行向量），满足 ${\varphi }_s(A,b)=e\approx 0$
4. 密文 $c:=\left[\begin{array}{c}A\\ b\end{array}\right]+\mu G$，基本是 $2l$ 个 TRLWE 密文的组合（除了纠错码不同）

解密：

1. 密文 $(A^{\prime },b^{\prime })\in {\mathbb{T}}_R^{2l}\times {\mathbb{T}}_R^{2l}$
2. 计算 ${\varphi }_s(A^{\prime },b^{\prime })=e+\mu (-s,1)G\in {\mathbb{T}}_R^{2l}$（行向量）
3. 截取索引 $2,4,\cdots ,2l$ 的元素，得到的 $e^{\prime }+\mu g\in {\mathbb{T}}_R^l$ 是含噪码字，均值 $\mu g$

同态运算：

1. 根据 $R$ 模的加法，${\mu }_1+{\mu }_2⟺C_1+C_2$

2. 根据 $R$ 模的环作用，$k\cdot \mu ⟺k\cdot C$，其中 $k\in R$

3. 同态乘法，明文空间 ${\mu }_1\in R$ 对于密文空间 $G^{-1}({\mu }_{2}G)\in {\mathbb{T}}_R^{2\times 2l}$ 的环作用，
      C 1 ⋅ G − 1 ( C 2 ) =    ( ( A 1 , b 1 ) + μ 1 G ) ⋅ G − 1 ( ( ( A 2 , b 2 ) + μ 2 G ) ) =    ( ( A 1 , b 1 ) ⋅ G − 1 ( C 2 ) + μ 1 C 2 ) + μ 1 μ 2 G C1⋅G−1(C2)=((A1,b1)+μ1G)⋅G−1(((A2,b2)+μ2G))=((A1,b1)⋅G−1(C2)+μ1C2)+μ1μ2G

   ==​C1​⋅G−1(C2​)((A1​,b1​)+μ1​G)⋅G−1(((A2​,b2​)+μ2​G))((A1​,b1​)⋅G−1(C2​)+μ1​C2​)+μ1​μ2​G​

   它的噪声增长是不平衡的，导出了乘法链的右结合性。

FHE Module Structure

非正式地，全同态模结构是五元元组 $(R,{\Pi }_R,M,{\Pi }_M,⊡)$：

1. 环 $R$ 的加密方案 ${\Pi }_R=(En{c}_R,De{c}_R)$，它的密文空间是 ${\mathcal{C}}_R$

2. 模 $M$ 的同态加密方案 ${\Pi }_M=(En{c}_M,De{c}_M)$，它的密文空间是 ${\mathcal{C}}_M$

3. 两个方案的密文之间的运算 $⊡:{\mathcal{C}}_R\times {\mathcal{C}}_M\to {\mathcal{C}}_M$（外积），使得
   $$De{c}_M(En{c}_R(r)⊡En{c}_M(m))=r\cdot m,\forall r\in R,\forall m\in M$$

TFHE 就是让 TGSW 和 TLWE、TRGSW 和 TRLWE 组成了全同态模结构，从而实现了 “外积”，

• 元组 $((\mathbb{Z},\text{TGSW}),(\mathbb{T},\text{TLWE}))$，组成了环 $\mathbb{Z}$ 模 $\mathbb{T}$ 的全同态模结构，外积定义为：
     T G S W s ( r ∈ Z ) ⊡ α T L W E s ( m ∈ T ) =    ( [ A s A + e ] + r ⋅ G ) ⋅ G α − 1 ( [ a s a + e ′ ] + [ 0 m ] ) =    [ A s A + e ] ⋅ G α − 1 ( T L W E s ( m ) ) + r ⋅ T L W E s ( m ) =    T L W E s ( r ⋅ m ∈ T ) TGSWs(r∈Z)⊡αTLWEs(m∈T)=([AsA+e]+r⋅G)⋅G−1α([asa+e′]+[0m])=[AsA+e]⋅G−1α(TLWEs(m))+r⋅TLWEs(m)=TLWEs(r⋅m∈T)

  ===​TGSWs​(r∈Z)⊡α​TLWEs​(m∈T)([AsA+e​]+r⋅G)⋅Gα−1​([asa+e′​]+[0m​])[AsA+e​]⋅Gα−1​(TLWEs​(m))+r⋅TLWEs​(m)TLWEs​(r⋅m∈T)​

• 元组 $((R_{\mathbb{Z}},\text{TRGSW}),({\mathbb{T}}_R,\text{TRLWE}))$，组成了环 $R_{\mathbb{Z}}$ 模 ${\mathbb{T}}_R$ 的全同态模结构，外积定义为：
     T R G S W s ( r ∈ R Z ) ⊡ α T R L W E s ( m ∈ T R ) =    ( [ A s A + e ] + r ⋅ G ) ⋅ G α − 1 ( [ a s a + e ′ ] + [ 0 m ] ) =    [ A s A + e ] ⋅ G α − 1 ( T R L W E s ( m ) ) + r ⋅ T R L W E s ( m ) =    T R L W E s ( r ⋅ m ∈ T R ) TRGSWs(r∈RZ)⊡αTRLWEs(m∈TR)=([AsA+e]+r⋅G)⋅G−1α([asa+e′]+[0m])=[AsA+e]⋅G−1α(TRLWEs(m))+r⋅TRLWEs(m)=TRLWEs(r⋅m∈TR)

  ===​TRGSWs​(r∈RZ​)⊡α​TRLWEs​(m∈TR​)([AsA+e​]+r⋅G)⋅Gα−1​([asa+e′​]+[0m​])[AsA+e​]⋅Gα−1​(TRLWEs​(m))+r⋅TRLWEs​(m)TRLWEs​(r⋅m∈TR​)​