学习同态加密：第三代全同态加密经典论文合集

全同态加密领域的首创者是Gentry，他做出的开创性工作的为三个主要的全同态加密研究阶段的铺平了道路。

本文会按照全同态加密经典论文的研究阶段进行划分，并给出相关的阅读建议，第一代论文分享请见学习同态加密：第一代全同态加密经典论文合集，第二代论文分享请见学习同态加密：第二代全同态加密经典论文合集。

有兴趣的同学还可以阅读往期推送，了解更多全同态加密的知识体系整理，详情请请见全同态加密知识体系整理(上)和全同态加密知识体系整理(下)。

1

第三代全同态加密

经典论文

第三代FHE始于Gentry等人（GSW）方案，GSW方案提出了一种不同的方法来执行同态运算，引入了近似特征向量方法，该方法消除了对密钥和模切换技术的要求。这种新技术将同态乘法引入的误差增长减少到一个小的多项式因子。

C. Gentry, A. Sahai, and B. Waters, “Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based,” in Advances in Cryptology—CRYPTO 2013, R. Canetti and J. A. Garay, Eds. Berlin, Germany: Springer, 2013, pp. 75–92.

这是相对于先前方案（例如BGV或FV）的一个独特方面，对于先前方案，最终误差以准多项式因子增长，该方案的RLWE版本由Khedr等人给出。

A. Khedr, G. Gulak, and V. Vaikuntanathan, “SHIELD: Scalable homomorphic implementation of encrypted data-classifiers,” IEEE Trans. Comput., vol. 65, no. 9, pp. 2848–2858, Sep. 2015.

GSW方案的主要缺点是高通信成本（密文相对于相应的明文是大的）和计算复杂性。为了减少计算开销，已经提出了各种优化来改进自举过程。

具体而言，Alperin-Scheiff和Peikert（AP）提出了一种新的自举算法，将解密视为算术函数，而不是布尔电路。

J. Alperin-Sheriff and C. Peikert, “Faster bootstrapping with polynomial error,” in Advances in Cryptology—CRYPTO 2014, J. A. Garay and R. Gennaro, Eds. Berlin, Germany: Springer, 2014, pp. 297–314.

J. Alperin-Sheriff and C. Peikert, “Practical bootstrapping in quasilinear time,” in Advances in Cryptology—CRYPTO 2013, R. Canetti and J. A. Garay, Eds. Berlin, Germany: Springer, 2013, pp. 1–20.

Hiromasa等人优化了Alperin等人的工作，构建了支持同态矩阵运算的FHE方案（基于GSW方案）。

R. Hiromasa, M. Abe, and T. Okamoto, “Packing messages and optimizing bootstrapping in GSW-FHE,” IEICE Trans. Fundamentals Electron., Commun. Comput. Sci., vol. E99.A, no. 1, pp. 73–82, 2016.

此外，Brakerski和Vaikunthanathan从GSW开始，首次提出了基于多项式逼近因子（和循环安全性）的GapSVP的FHE方案。

Z. Brakerski and V. Vaikuntanathan, “Lattice-based FHE as secure as PKE,” in Proc. 5th Conf. Innov. Theor. Comput. Sci., Jan. 2014, pp. 1–12.

Ducas和Micciancio提出了AP自举技术的环变体FHEW方案。他们引入了一种新的方法来同态计算。在这项工作中，他们还采用了复杂的FFT，使该方案能够实现最快的傅立叶变换（该方案名称FHEW的“W”来自于此）。这组优化使得GSW的方案自举过程比BGV的方案更快。

L. Ducas and D. Micciancio, “FHEW: Bootstrapping homomorphic encryption in less than a second,” in Advances in Cryptology—EUROCRYPT 2015, E. Oswald and M. Fischlin, Eds. Berlin, Germany: Springer, 2015, pp. 617–640.

在随后的一篇论文中，Chillotti等人改进了Ducas-Micciancio的结果，并使用了一种不同的自举技术，即Gama、Izabachène、Nguyen和Xie（GINX）提出的技术。

N. Gama, M. Izabachène, P. Q. Nguyen, and X. Xie, “Structural lattice reduction: Generalized worst-case to average-case reductions and homomorphic cryptosystems,” in Advances in Cryptology—EUROCRYPT 2016. Cham, Switzerland: Springer, 2016, pp. 528–558.

作者在Torus上提出了三种不同的FHE方案，通常称为TFHE。

Chillotti等人指出，可以对密文进行线性组合，以获得新的密文，即消息的线性组合。然而，当我们不得不非线性地处理密文时，TFHE似乎错过了一些属性。为了避免这个问题，Chillotti等人提出了广义尺度不变的GSW版本，称为TRGSW。

I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène, “TFHE: Fast fully homomorphic encryption over the torus,” J. Cryptol., vol. 33, no. 1, pp. 1–58, 2019.

Micciancio和Polyakov比较了FHEW和TFHE方案，并证明性能差异是由两种方案中采用的不同自举算法决定的：AP用于FHEW，GINX用于TFHE。

D. Micciancio and Y. Polyakov, “Bootstrapping in FHEW-like cryptosystems,” in Proc. 9th Workshop Encrypted Comput. Appl. Homomorphic Cryptogr., Nov. 2021, pp. 17–28.

具体而言，对于二进制秘密，TFHE比FHEW快，而对于更高的秘密大小（高于三进制），FHEW在运行时间上优于TFHE。在内存方面，TFHE有一个比FHEW更小的自举密钥。

然而，值得注意的是，在最近的一篇论文中，Lee等人介绍了一种新的自举过程，该过程实现了两种算法的优点：AP和GINX。新方法在不增加运行时间的情况下支持任意密钥分布（如AP/FHW），并且它还实现了相当小的自举密钥大小（如GINX/TFHE）。

Y. Lee et al., “Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption,” Cryptol. ePrint Arch., 2022.

TFHE方案的一个相关特征是，自举技术能够在降噪操作（即PBS）的同时评估单变量函数。

I. Chillotti, D. Ligier, J.-B. Orfila, and S. Tap, “Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. Springer, 2021, pp. 670–699.

已经提出了一些优化方案来改进TFHE方案，特别是其PBS程序。Carpov等人提出了PBS的多输出版本，即一种新技术，可以通过单个自举执行在不同变量上执行多个同态运算。

S. Carpov, N. Gama, M. Georgieva, and J. R. Troncoso-Pastoriza, “Privacy-preserving semi-parallel logistic regression training with fully homomorphic encryption,” Cryptol. ePrint Arch., Tech. Rep. 2019/101, 2019. [Online]. Available: https://eprint.iacr.org/2019/101

这种构造也可以用于同时对同一加密消息上的几个函数进行同态求值。在最近的一项工作中，Guimarães等人优化了自举过程，以评估大型密文上的多个函数。

A. Guimarães, E. Borin, and D. F. Aranha, “Revisiting the functional bootstrap in TFHE,” IACR Trans. Cryptograph. Hardw. Embedded Syst., vol. 23, pp. 229–253, Feb. 2021.

Chillotti等人提出了一些增强，包括一种在不增加额外错误的情况下同时评估多个函数的通用方法。

I. Chillotti, D. Ligier, J.-B. Orfila, and S. Tap, “Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. Springer, 2021, pp. 670–699.

最后，Chen等人从TFHE中提出了一种多密钥同态加密方案，实现细节、理论示例以及PBS技术的清晰描述。

H. Chen, I. Chillotti, and Y. Song, “Multi-key homomorphic encryption from TFHE,” in Proc. Int. Conf. Theory Appl. Cryptol. Inf. Secur. Cham, Switzerland: Springer, 2019, pp. 446–472.

2

阅读建议

Gentry等人提出的GSW是第三代全同态加密的经典工作，引出了后续的一系列相关优化研究，其中2013年Alpersin、2015年Ducas以及2016年的TFHE是一脉相承的工作，其中TFHE更是目前最先进的同态加密技术之一，可以考虑作为优先阅读的文献。

2019年开始，大家关注多密钥以及自举相关的优化技术，但是目前还缺少具有显著优势的技术，可以作为密切跟踪的前沿技术领域。

END

往期推荐

1.学习同态加密：第二代全同态加密经典论文合集
2.学习同态加密：第一代全同态加密经典论文合集3.笔记分享|浙大暑期密码学课程：Idealized Model ll4.笔记分享|浙大暑期密码学课程：Idealized Model l