全同态加密理论、生态现状与未来展望（中2）

《全同态加密理论、生态现状与未来展望》系列由[e-mail]和[e-mail]整理原创发布，分为上中下三个系列：

• 全同态加密理论、生态现状与未来展望（上）：专注于介绍全同态加密理论知识。
• 全同态加密理论、生态现状与未来展望（中1）：专注于介绍全同态加密四代算法中第一代第二代FHE算法的衍化历程。
• 全同态加密理论、生态现状与未来展望（中2）：专注于介绍全同态加密四代算法中第三代第四代FHE算法的衍化历程。
• 全同态加密理论、生态现状与未来展望（下）：专注于介绍当前全同态加密生态现状及未来展望。

整个系列内容可能存在纰漏，希望能得到大家的反馈，有任何问题欢迎邮件联系[e-mail]和[e-mail]，或在本文下方评论留言。

3.3 第3代：基于LWE和RLWE

图 7: 第 3 代：基于 LWE 和 RLWE

3.3.1 GSW13

Homomorphic Encryption from Learning with Errors:Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

安全参数为$\lambda$，电路深度为$L$。模为$q$、噪声分布$\chi$、维数$n$ 以及$m$。 其中，分布$\chi$是$\mathbb{Z}$上的噪声高斯分布，$m=2n\log q$。令$l=\lceil \log q\rceil$,$N=(n+1)l$。

• 密钥生成： 选择随机向量${\mathbf{s}}^{\prime }\leftarrow {\mathbb{Z}}_q^n$，私钥为$sk=\mathbf{s}=(1,{\mathbf{s}}^{\prime })\in {\mathbb{Z}}_q^{n+1}$。
  有以下等式成立：
  $$\text{Powerof2}(\mathbf{s})=(\mathbf{s},2\mathbf{s},\cdots ,2^{l-1}\mathbf{s})\mathrm{mod}q=(1,2,\cdots ,2^{l-1},{\mathbf{s}}^{\prime },2{\mathbf{s}}^{\prime },\cdots ,2^{l-1}{\mathbf{s}}^{\prime })\mathrm{mod}q$$

  选取随机矩阵${\mathbf{A}}^{\prime }\leftarrow {\mathbb{Z}}_q^{m\times n}$和噪声向量$\mathbf{e}\leftarrow {\chi }^m$，计算
  $$b:={\mathbf{A}}^{\prime }\cdot {\mathbf{s}}^{\prime }+\mathbf{e}$$
  令$\mathbf{A}$为$n+1$列矩阵，由向量$\mathbf{b}$和矩阵${\mathbf{A}}^{\prime }$构成
  $$\mathbf{A}=[\mathbf{b}|-{\mathbf{A}}^{\prime }]\in {\mathbb{Z}}_q^{m\times (n+1)}$$
  公钥为$pk=\mathbf{A}$。
  注意，有以下等式成立 $$\mathbf{A}\cdot \mathbf{s}=[\mathbf{b}|-{\mathbf{A}}^{\prime }]\cdot (1,{\mathbf{s}}^{\prime })=({\mathbf{A}}^{\prime }\cdot {\mathbf{s}}^{\prime }+\mathbf{e})-{\mathbf{A}}^{\prime }{\mathbf{s}}^{\prime }=\mathbf{e}$$

• 加密：
  消息为 m ∈ { 0 , 1 } m \in \{0, 1\} m∈{0,1}，选取随机矩阵 R ∈ { 0 , 1 } N × m \mathbf{R} \in \{0, 1\}^{N \times m} R∈{0,1}N×m，如下计算：
  $$\mathbf{C}:=m\cdot {\mathbf{I}}_N+\mathbf{R}\cdot \mathbf{A}$$
  其中，${\mathbf{I}}_N$是$N\times N$的单位矩阵。则密文为$\mathbf{C}$。为满足同态性，密文长度不变，通常记为$\text{Flatten}(\mathbf{C})$。

• 解密： 输入私钥$\mathbf{s}$和密文$\mathbf{C}$，如下计算：
  $$\mathbf{Cs}=(m\cdot {\mathbf{I}}_N+\mathbf{R}\cdot \mathbf{A})\mathbf{s}=m\cdot {\mathbf{I}}_N\mathbf{s}+\mathbf{Re}=m\cdot {\mathbf{I}}_N\mathbf{s}+{\mathbf{e}}^{\ast }=m\cdot \text{Powersof2}(\mathbf{s})+{\mathbf{e}}^{\ast }$$
  其中，$m{\mathbf{I}}_N\mathbf{s}=(m,m{s}^{\prime })$取出$m$，$\mathbf{R}\cdot \mathbf{e}={\mathbf{e}}^{\ast }\approx 0$。

• 同态加法： $$\mathbf{C}+{\mathbf{C}}^{\prime }=(m+m^{\prime })\cdot {\mathbf{I}}_N+(\mathbf{R}+{\mathbf{R}}^{\prime })\cdot \mathbf{A}$$
  通常记为$\text{Flatten}(\mathbf{C}+{\mathbf{C}}^{\prime })$。

• 解密：
  $$(\mathbf{C}+{\mathbf{C}}^{\prime })\mathbf{s}=((m+m^{\prime })\cdot {\mathbf{I}}_N+(\mathbf{R}+{\mathbf{R}}^{\prime })\cdot \mathbf{A})\mathbf{s}=(m+m^{\prime })\cdot {\mathbf{I}}_N\mathbf{s}+(\mathbf{R}+{\mathbf{R}}^{\prime })\mathbf{e}$$

• 同态乘法： $$\mathbf{C}\bullet {\mathbf{C}}^{\prime }=(m\cdot {\mathbf{I}}_N+\mathbf{R}\cdot \mathbf{A})\bullet (m^{\prime }\cdot {\mathbf{I}}_N+{\mathbf{R}}^{\prime }\cdot \mathbf{A})$$
  通常记为$\text{Flatten}(\mathbf{C}\bullet {\mathbf{C}}^{\prime })$。

• 解密：
  由前面的解密步骤可知：$\mathbf{Cs}=m\cdot \text{Powersof2}(\mathbf{s})+{\mathbf{e}}^{\ast }$，所以如下解密：
  $$\begin{array}{rl}& (\mathbf{C}\bullet {\mathbf{C}}^{\prime })\mathbf{s}\\ & =\mathbf{C}\bullet (m^{\prime }\cdot \text{Powersof2}(\mathbf{s})+{\mathbf{e}}^{\prime })\\ & =m^{\prime }\mathbf{C}\text{Powersof2}(\mathbf{s})+\mathbf{C}{\mathbf{e}}^{\prime }\\ & =m^{\prime }(m\text{Powersof2}(\mathbf{s})+\mathbf{e})+\mathbf{C}{\mathbf{e}}^{\prime }\\ & =m^{\prime }m\text{Powersof2}(\mathbf{s})+m^{\prime }\mathbf{e}+\mathbf{C}{\mathbf{e}}^{\prime }\end{array}$$

当$m^{\prime }\mathbf{e}+\mathbf{C}{\mathbf{e}}^{\prime }\le (N+1)E=((n+1)l+1)\cdot 2nB\log q$时，可解密成功。
经过深度为$L$的电路计算后，结果密文的噪声至多为$(N+1{)}^{L}E$。因此，需满足一下条件才能正确解密：
$$(N+1{)}^{L}E=((n+1)l+1{)}^L\cdot 2nB\log q<q/8$$
GSW 方案的主要缺点是较高的通信成本（密文相对于对应的明文较大）和计算复杂性。为了减少计算开销，提出了各种优化方法以改进启动过程（图7）。

3.3.2 TRLWE18

TFHE: Fast Fully Homomorphic Encryption over the Torus

令$R=\mathbb{Z}[x]/⟨x^d+1⟩$。其中，$d$是2的幂次方。令$T=\mathbb{R}[x]/⟨x^d+1⟩\mathrm{mod}1$和$R_2={\mathbb{F}}_2[x]/⟨x^d+1⟩$，即$R_2$中的任何元素都是具有二进制系数的$R$中的多项式。
TRLWE18方案构造如下：

• 密钥生成： 输入安全参数$\lambda$，输出小的私钥$\mathbf{s}\in R_2^n$。

• 加密： 输入私钥$\mathbf{s}\in R_2^n$，错误参数$\alpha$和消息$m\in T$。然后，选择一个均匀随机的掩码$a\in T^n$，并选择一个小的噪声$e\in \chi$。其中，$\chi$ 是一个B有界分布，则密文为：
  $$\mathbf{c}:=(\mathbf{a},b)=(\mathbf{a},\mathbf{s}\cdot \mathbf{a}+m+e)\in T^n\times T$$

• 解密： 输入私钥$s\in R_2^n$和密文$\mathbf{c}\in T^{n+1}$,计算密文$\mathbf{c}$的秘密线性$\kappa$-Lipschitz函数 ${\phi }_s$（称为相位）。该相位${\phi }_s:T^n\times T\to T$ 满足：
  $${\phi }_s(\mathbf{a},b)=b-s\cdot \mathbf{a}$$
  注意，该函数由私钥$\mathbf{s}\in R_2^n$参数化。相位${\phi }_{\mathbf{s}}(\mathbf{c})$接近实际的消息：
  $${\phi }_{\mathbf{s}}(\mathbf{c})=\mathbf{s}\cdot \mathbf{a}+m+e-\mathbf{s}\cdot \mathbf{a}=m+e$$
  最后，将 ${\phi }_s(c)$ 四舍五入到消息空间 $M\subset T$ 中的最近点。

• （同态）密文的线性组合：
  设${\mathbf{c}}_1,\dots ,{\mathbf{c}}_p$为$p$个独立的密文，具有相同的密钥$\mathbf{s}$，并且设$f_1,\dots ,f_p$为$R$中的整数多项式。如下构造线性组合的密文：
  $$\mathbf{c}=\sum _{i=1}^p{f}_i\cdot {\mathbf{c}}_i$$
  要求误差幅度保持小于$1/4$，$||e|{|}_{\infty }\le 1/4$。

• 解密：
  $${\text{Dec}}_{\mathbf{s}}(\mathbf{c})=\sum _{i=1}^p{f}_i\cdot {\text{Dec}}_{\mathbf{s}}({\mathbf{c}}_i)$$

密文可以线性组合，从而得到一个新的密文，解密后可以获得明文的线性组合。

3.4 第4代：基于LWE和RLWE

图 8: 基于基于 LWE 和 RLWE 的第四代 FHE

3.4.1 CKKS16

Homomorphic Encryption for Arithmetic of Approximate Numbers

令$R=\mathbb{Z}[x]/⟨x^d+1⟩$ 且$d=2^M$。对于基数$p$、模$q_0$和自然数$L$（选择的层次），令$q_{\ell }=p^{\ell }\cdot q_0$对于$\ell =1,\dots ,L$。注意，层次$\ell$的密文是$R_{q_{\ell }}$中的一个向量。考虑以下相关分布：对于实数$\sigma$，$DG({\sigma }^2)$是一个在 ${\mathbb{Z}}^d$上的离散高斯分布，从独立的离散高斯分布中采样，每个分量的方差为${\sigma }^2$。对于$0⟨\rho ⟨1$的实数，分布$ZO(\rho )$是一个在 { − 1 , 0 , 1 } d \{-1, 0, 1\}^d {−1,0,1}d上的分布。其中，$0$的概率为$1-\rho$，而$-1$或$1$的概率为$\frac{\rho }{2}$。最后，$\chi$是一个$B$-有界分布。

层次型CKKS16方案构造如下：

• 密钥生成： 输入安全参数$\lambda$，选择$M$、整数$h$和$t$，以及实数$\sigma$，使得对关联的RLWE实例，最佳攻击的复杂度为$2^{\lambda }$。私钥为$sk=(1,s)$。其中，$s\in \chi$。生成一个均匀随机的$a\in R_{q_L}$，并计算$b=-as+e\mathrm{mod}{q}_L$。其中，$e$ 为$DG({\sigma }^2)$。最后，采样$a^{\prime }\in R_{t\cdot q_L}$和$e^{\prime }\in DG({\sigma }^2)$，并计算$b^{\prime }=-as+e^{\prime }+t{s}^{\prime }\mathrm{mod}t\cdot q_L$。公钥为$pk=(b,a)$和评估密钥为$evk=(b^{\prime },a^{\prime })$。

• 加密： 消息为$m\in R$，公钥为$pk=(b,a)\in R_{q_L}^2$，随机选择$v\in ZO(1/2)$和噪声$e_0,e_1\in DG({\sigma }^2)$，如下计算密文
  $$\mathbf{c}=(\beta ,\alpha )=v(b,a)+(m+e_0,e_1)\mathrm{mod}{q}_{\ell }=(vb+m+e_0,va+e_1)\mathrm{mod}{q}_{\ell }.$$

• 解密： 输入私钥$sk=(1,s)$和密文$\mathbf{c}\in R_{q_{\ell }}^2$，如下计算：
  $$\begin{array}{rl}& ⟨\mathbf{c},sk⟩\mathrm{mod}{q}_{\ell }\\ & =\beta +\alpha s\mathrm{mod}{q}_{\ell }\\ & =vb+m+e_0+(va+e_1)s\mathrm{mod}{q}_{\ell }\\ & =v(-as+e)+m+e_0+(va+e_1)s\mathrm{mod}{q}_{\ell }\\ & =m+ve+e_0+e_{1}s\end{array}$$

• 标量与密文乘法： 输入标量$k$和密文$\mathbf{c}$，直接乘
  $$k\mathbf{c}=(k\beta ,k\alpha )=kv(b,a)+k(m+e_0,e_1)\mathrm{mod}{q}_{\ell }=(kvb+km+k{e}_0,kva+k{e}_1)\mathrm{mod}{q}_{\ell }.$$

• 解密： $$\begin{array}{rl}& ⟨k\mathbf{c},sk⟩\mathrm{mod}{q}_{\ell }\\ & =k\beta +k\alpha s\mathrm{mod}{q}_{\ell }\\ & =kvb+km+k{e}_0+k(va+e_1)s\mathrm{mod}{q}_{\ell }\\ & =kv(-as+e)+km+k{e}_0+k(va+e_1)s\mathrm{mod}{q}_{\ell }\\ & =km+kve+k{e}_0+k{e}_{1}s\end{array}$$
  解密获得$km$。如果$k=10000$，则是扩大；如果$k=1/10000$则是缩小。注意：直接缩小可能会与噪声重叠，解密会出错。通常需要先放大，后缩小，才不会与噪声重叠。

• 同态加法：$\mathbf{c}+{\mathbf{c}}^{\prime }=((v+v^{\prime })b+(m+m^{\prime })+(e_0+e_0^{\prime }),(a+a^{\prime })a+(e_1+e_1^{\prime }))\mathrm{mod}{q}_{\ell }$

• 解密：
  输入私钥$sk=(1,s)$和密文$\mathbf{c}+{\mathbf{c}}^{\prime }\in R_{q_{\ell }}^2$，如下计算：
  $$\begin{array}{rl}& ⟨(\mathbf{c}+{\mathbf{c}}^{\prime }),sk⟩\mathrm{mod}{q}_{\ell }\\ & =(\beta +{\beta }^{\prime })+(\alpha +{\alpha }^{\prime })s\mathrm{mod}{q}_{\ell }\\ & =(v+v^{\prime })b+(m+m^{\prime })+(e_0+e_0^{\prime })+(a+a^{\prime })as+(e_1+e_1^{\prime })s\mathrm{mod}{q}_{\ell }\\ & =(v+v^{\prime })(-as+e)+(m+m^{\prime })+(e_0+e_0^{\prime })+(a+a^{\prime })as+(e_1+e_1^{\prime })s\mathrm{mod}{q}_{\ell }\\ & =(m+m^{\prime })+(v+v^{\prime })e+(e_0+e_0^{\prime })+(e_1+e_1^{\prime })s\end{array}$$

• 同态乘法： $$\mathbf{c}\cdot {\mathbf{c}}^{\prime }=(\beta ,\alpha )({\beta }^{\prime },{\alpha }^{\prime })=(\beta {\beta }^{\prime },\beta {\alpha }^{\prime },\alpha {\beta }^{\prime },\alpha {\alpha }^{\prime })=(d_0,d_1)+t^{-1}{d}_{2}evk\mathrm{mod}{q}_{\ell },$$
  使用密钥交换技术使得扩展密文$\mathbf{c}\cdot {\mathbf{c}}^{\prime }=(d_0,d_1,d_2)$变成正常密文$(\bar{\beta },\bar{\alpha })$。

• 解密：

  • 如果是扩展密文$\mathbf{c}\cdot {\mathbf{c}}^{\prime }=(d_0,d_1,d_2)$，则使用扩展私钥$(1,s,s^2)$解密；

  • 如果是再线性化密文$(\bar{\beta },\bar{\alpha })$，则使用正常私钥$(1,s)$解密（通常是该情况，使得加密生成的密文与经过同态计算的密文不可区分）。

需要注意：当我们有两个密文$\mathbf{c},{\mathbf{c}}^{\prime }$处于不同的级别 ${\ell }^{\prime }<\ell$ 时，应该通过调整更高级别的密文的级别来匹配两个密文的级别，即${\ell }^{\prime }=\ell$。这可以通过重新缩放过程实现，该过程将级别为 $\ell$ 的密文$\mathbf{c}\in R_{q_{\ell }}^2$ 转换为${\mathbf{c}}^{\prime }=\lfloor q_{{\ell }^{\prime }}/q_{\ell }\rceil \mathrm{mod}{q}_{{\ell }^{\prime }}$。

CKKS16特点： 消息空间可以表示为扩展域$C$中的元素。非正式地，消息$m$可以嵌入$S=R[x]/⟨x^d+1⟩$ 中。由于$x^d+1$的根是复数单位根，若要将 $m\in S$转换为复数向量，只需在这些复数根上对其进行求值。

第四代方案类似于第二代方案，区别在第四代是近似计算，能用于浮点数计算，且计算速度显著提高。

3.4.2 CKKS16应用

CKKS16实现浮点计算：
$1.234\times 0.689\times 2.194\times 0.971\times 3.323\times 4.154\times 0.489\times 3.772=?$

• ChatGPT 4o: $46.03$

• Gork 2.0: $45.8$

• deepseek: $46.12$

逐步计算并保留2位小数：$1.23\times 0.68\times 2.19\times 0.91\times 3.32\times 4.15\times 0.48\times 3.77=41.62$

逐步计算并保留所有小数：$1.23\cdot 0.68\cdot 2.19\cdot 0.91\cdot 3.32\cdot 4.15\cdot 0.48\cdot 3.77=41.5594574077313280\approx 41.56$

先放大，再缩小：$12340\cdot 6890\cdot 21940\cdot 9170\cdot 33230\cdot 41540\cdot 4890\cdot 37720/10000^8=4.361\cdot 10^{33}/10000^8=43.61$

方法： 先放大，再计算，再缩小最终结果，则能获得准确值。
消息1.234扩大12340，然后加密，然后同态乘法，然后解密，然后缩小10000，获得1.234。加密和解密过程中的噪声对放大的消息影响较小。

缩减技术： CKKS16的密文能够乘以常量$1/p$，实现对应明文数据的缩小，用于缩小噪声。

图 9: 近似同态计算

参考文献

• GGH公钥密码系统 Public-key cryptosystems from lattice reduction problems

• Regev05论文On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

• Brakerski12论文Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP

• Micciancio-Regev书 Lattice-based cryptography

• KTX07论文Multi-bit Cryptosystems Based on Lattice Problems

• DGHV10论文Fully homomorphic encryption over the integers

• LV10论文On Ideal Lattices and Learning with Errors over Rings

• Gentry09论文Fully homomorphic encryption using ideal lattices

• CR16论文Recovering Short Generators of Principal Ideals in Cyclotomic Rings

• BV11论文Efficient Fully Homomorphic Encryption from (Standard)LWE

• LTV13论文On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

• GSW13论文Homomorphic Encryption from Learning with Errors:Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

• TRLWE18论文TFHE: Fast Fully Homomorphic Encryption over the Torus

• 陈智罡 全同态加密：从理论到实践

• 周福才、徐剑 格理论与密码学

• Google Jeremy Kun 2024.5博客 A High-Level Technical Overview of Fully Homomorphic Encryption

• Optalysys团队2024年10月博客 Fully Homomorphic Encryption industry leaders join forces to form global FHE Hardware Consortium

• Fhenix团队2023年10月17日博客 The Holy Grail of Encryption: The Rise of FHE Technology

• NGC Ventures团队2024年1月12日博客 Introduction to FHE and Blockchain: Implications for Scalability and Privacy

• Awesome Fully Homomorphic Encryption (FHE) x Blockchain resources, libraries, projects, and more

• Awesome Homomorphic Encryption

• PANews 2024年9月17日文章 全同态加密（FHE）的进展与应用

• 2022年论文《Survey on Fully Homomorphic Encryption, Theory, and Applications》

• Craig Gentry 2022年论文《Homomorphic encryption: a mathematical survey》

• 2024年12月20日Jorge Myszne，Niobium Microsystems 首席产品官 博客 3 Homomorphic Encryption Trends for 2025

• HCLTech团队2024年6月研报 Homomorphic encryption: Exploring technology trends and future approach

• 2024年论文《vFHE: Verifiable Fully Homomorphic Encryption》

• PPS Lab团队2023年10月博客 Arithmetizing FHE in Circom

• PPS Lab团队2023年10月博客 A primer on the FHEW & TFHE schemes

• 2024年论文《Oraqle: A Depth-Aware Secure Computation Compiler》

• 2023年10月论文《A Survey on Implementations of Homomorphic Encryption Schemes》

• Sunscreen团队2021年8月博客 An Intro to Fully Homomorphic Encryption for Engineers

• TFHE：2016年论文《Faster Fully Homomorphic Encryption: Bootstrapping in less than 0.1 Seconds》

• BGV：2011年论文 《Fully Homomorphic Encryption without Bootstrapping》

• BFV：2012年论文《Somewhat Practical Fully Homomorphic Encryption》

• CKKS：2016年论文《Homomorphic Encryption for Arithmetic of Approximate Numbers》

• HomomorphicEncryption.org 2018年slide Building Applications with Homomorphic Encryption

• Greenfield Capital 2024年7月博客 The muted Seven – 7 things you should consider re confidential compute

• Sunscreen 2023年8月博客 How SNARKs fall short for FHE

• 2024年4月18日BigBrainVC团队博客 Flawed Homomorphic Encryption

• 2024年Verisense Network slide An Introduction To FHE and Its Application in Rust

• Vitalik 2020年7月20日博客 Exploring Fully Homomorphic Encryption

• 2023年论文《Verifiable Fully Homomorphic Encryption》

• 2018年《Homomorphic Encryption Standard v1.1》

• 2021年论文《SoK: Fully Homomorphic Encryption Compilers》

• 2024年论文《SoK: Fully Homomorphic Encryption Accelerators》

• Sunscreen团队2023年5月博客 Building an FHE compiler for the real world

• Zama团队2023年5月23日博客 Private Smart Contracts Using Homomorphic Encryption

• Craig Gentry 2024年6月分享视频 FHE: Past, Present and Future