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

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

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

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

1

第四代全同态加密

经典论文

2017年，Cheon等人引入了新一代FHE方案。作者提出了一种构造近似算术数字的分级同态加密方案的方法，并包括一个实现该方案的开源库。

这个方案最初被称为HEAAN，但如今，研究界将该方案称为CKKS（来自作者的名字）。

J. H. Cheon, A. Kim, M. Kim, and Y. Song, “Homomorphic encryption for arithmetic of approximate numbers,” in Advances in Cryptology—ASIACRYPT 2017, T. Takagi and T. Peyrin, Eds. Cham, Switzerland: Springer, 2017,

pp. 409–437.

一年后，Cheon等人将该方案扩展为FHE方案。

J. H. Cheon, K. Han, A. Kim, M. Kim, and Y. Song, “Bootstrapping for approximate homomorphic encryption,” in Advances in Cryptology—EUROCRYPT 2018, J. B. Nielsen and V. Rijmen, Eds. Cham, Switzerland: Springer,

2018, pp. 360–384.

随后，Cheon等通过包括基于CRT的密文打包技术，提出了CKKS方案的变体。

J. H. Cheon, K. Han, A. Kim, M. Kim, and Y. Song, “A full RNS variant of approximate homomorphic encryption,” in Proc. Int. Conf. Sel. Areas Cryptogr. Cham, Switzerland: Springer, 2018, pp. 347–368.

Boemer等人介绍了几种基于复杂打包技术的优化，以提升标量编码效率，降低密文明文加法和乘法运算的运行时间。

F. Boemer, A. Costache, R. Cammarota, and C. Wierzynski, “NGraph-HE2: A high-throughput framework for neural network inference on encrypted data,” in Proc. 7th ACM Workshop Encrypted Comput. Appl. Homomorphic Cryptogr., New York, NY, USA, 2019, pp. 45–56.

此外，Kim和Song介绍了一种不同类型的复杂打包技术。

D. Kim and Y. Song, “Approximate homomorphic encryption over the conjugate-invariant ring,” in Proc. Int. Conf. Inf. Secur. Cryptol. Cham, Switzerland: Springer, 2018, pp. 85–102.

Kim等人通过提出一种将计算过程中的误差最小化的新技术，提高了CKKS及其RNS变体的可用性。

具体来说，这个想法是在乘法之前而不是之后重新缩放密文，从而在执行乘法之前获得较小的误差。

A. Kim, A. Papadimitriou, and Y. Polyakov, “Approximate homomorphic encryption with reduced approximation error,” in Proc. Cryptographers’ Track RSA Conf. Cham, Switzerland: Springer, 2022, pp. 120–144.

此外，Chen等人增强了CKKS的自举版本。

A. Kim, A. Papadimitriou, and Y. Polyakov, “Approximate homomorphic encryption with reduced approximation error,” in Proc. Cryptographers’ Track RSA Conf. Cham, Switzerland: Springer, 2022, pp. 120–144.

Han和Ki讨论并改进了cheon的自举版本。

K. Han and D. Ki, “Better bootstrapping for approximate homomorphic encryption,” in Topics in Cryptology—CT-RSA 2020, S. Jarecki, Ed. Cham, Switzerland: Springer, 2020, pp. 364–390.

Cheon的自举版本包括同态模降，其通过三角函数近似以提高效率。并行工作改进了这种近似，例如Lee等人，他利用Kim等人提出的技术改进了RNS-KKS的自举。

J.-W. Lee, E. Lee, Y. Lee, Y.-S. Kim, and J.-S. No, “High-precision bootstrapping of RNS-CKKS homomorphic encryption using optimal minimax polynomial approximation and inverse sine function,” in Advances in Cryptology—EUROCRYPT 2021. Cham, Switzerland: Springer, 2021, pp. 618–647.

此外，Jutla和Manohar提出了一个正弦级数来近似模降，并实现了比以前工作高得多的精度。

C. S. Jutla and N. Manohar, “Sine series approximation of the mod function for bootstrapping of approximate HE,” in Advances in Cryptology—EUROCRYPT 2022. Cham, Switzerland: Springer, 2022, pp. 491–520.

还值得一提的是，如Jutla和Manohar以及Lee等人进行了在不依赖三角函数的情况下近似模归约的其他工作。

C. S. Jutla and N. Manohar, “Modular Lagrange interpolation of the mod function for bootstrapping of approximate HE,” Cryptol. ePrint Arch., 2020.

Y. Lee, J.-W. Lee, Y.-S. Kim, and J.-S. No, “Near-optimal polynomial for modulus reduction using L2-norm for approximate homomorphic encryption,” IEEE Access, vol. 8, pp. 144321–144330, 2020.

Bossuat等人提出了最有效的RNS-KKS自举实现，也是具有密集密文的自举算法的第一个实际实例。

J.-P. Bossuat, C. Mouchet, J. Troncoso-Pastoriza, and J.-P. Hubaux, “Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys,” in Advances in Cryptology—EUROCRYPT 2021. Cham, Switzerland: Springer, 2021, pp. 587–617.

另一方面，采用稀疏密文可以提高自举的效率，但由于最近的一些攻击，该方案的安全性较差。

基于这种权衡，Bossuat等人提出了一种稀疏密文打包技术，该技术克服了稀疏密文的安全漏洞问题，同时保留了可忽略的自举失败概率。

J.-P. Bossuat, J. Troncoso-Pastoriza, and J.-P. Hubaux, “Bootstrapping for approximate homomorphic encryption with negligible failure-probability by using sparse-secret encapsulation,” in Proc. Int. Conf. Appl. Cryptogr. Netw. Secur. Cham, Switzerland: Springer, 2022, pp. 521–541.

在最近的一项工作中，Li和Micciancio提出了一种针对CKKS的攻击，该攻击适用于特定的应用场景。

作者证明了CKKS方案（以及近似加密方案的所有改进和实现）容易受到访问加密功能的对手的攻击。也就是说，对手可以仅使用线性代数或格约简技术来提取密钥。具体地说，如果解密的元素和相应的密文都是已知的，则可以获得密钥，因为误差是密钥元素的线性组合。

B. Li and D. Micciancio, “On the security of homomorphic encryption on approximate numbers,” in Advances in Cryptology—EUROCRYPT 2021, A. Canteaut and F.-X. Standaert, Eds. Cham, Switzerland: Springer, 2021, pp. 648–677.

然而，正如Cheon等人在中指出的那样，如果密钥的所有者不共享解密消息的结果，则可以防止这种攻击。

J. H. Cheon, S. Hong, and D. Kim, “Remark on the security of CKKS scheme in practice,” IACR Cryptol. ePrint Arch., vol. 2020, p. 1581, Dec. 2020.

此外，值得提及的是Boura等人提出的工作，即CHIMERA方案，这是一种结合了三种基于RLWE的FHE方案的混合解决方案：TFHE、B/FV和CKKS。CHIMERA有一个特殊的特性，它可以在三种方案之间进行切换。

作者首先通过构建不同消息空间的嵌入来定义三种方案之间的公共明文空间。通过利用自举技术，CHIMERA能够将密文从TFHE切换到FV（反之亦然），并将CKKS切换到FV。

C. Boura, N. Gama, M. Georgieva, and D. Jetchev, “CHIMERA: Combining ring-LWE-based fully homomorphic encryption schemes,” J. Math. Cryptol., vol. 14, no. 1, pp. 316–338, 2020.

FV必须用作TFHE和CKKS之间转换的中间步骤。CHIMERA最初是作为Idash’18 Track 2比赛的解决方案提出的，后来Lu等人在PEGASUS中对其进行了改进。

W.-J. Lu, Z. Huang, C. Hong, Y. Ma, and H. Qu, “PEGASUS: Bridging polynomial and non-polynomial evaluations in homomorphic encryption,” in Proc. IEEE Symp. Secur. Privacy (SP), May 2021, pp. 1057–1073.

2

阅读建议

CKKS算法是第四代全同态算法的核心，可以有效满足实际中机器学习等近似运算的需求，因此作为核心阅读文献。

此外，针对CKKS的自举优化可以也是在熟悉了CKKS之后需要进行了解的，但是目前不同自举优化方案各有优势，缺少具有显著优势的研究，因此自举优化类文章可以考虑根据引用以及具体特点进行有选择地阅读。

END

往期推荐

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