高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

全同态加密技术的研究现状及发展路线综述

戴怡然 张江 向斌武 邓燚

戴怡然, 张江, 向斌武, 邓燚. 全同态加密技术的研究现状及发展路线综述[J]. 电子与信息学报, 2024, 46(5): 1774-1789. doi: 10.11999/JEIT230703
引用本文: 戴怡然, 张江, 向斌武, 邓燚. 全同态加密技术的研究现状及发展路线综述[J]. 电子与信息学报, 2024, 46(5): 1774-1789. doi: 10.11999/JEIT230703
DAI Yiran, ZHANG Jiang, XIANG Binwu, DENG Yi. Overview on the Research Status and Development Route of Fully Homomorphic Encryption Technology[J]. Journal of Electronics & Information Technology, 2024, 46(5): 1774-1789. doi: 10.11999/JEIT230703
Citation: DAI Yiran, ZHANG Jiang, XIANG Binwu, DENG Yi. Overview on the Research Status and Development Route of Fully Homomorphic Encryption Technology[J]. Journal of Electronics & Information Technology, 2024, 46(5): 1774-1789. doi: 10.11999/JEIT230703

全同态加密技术的研究现状及发展路线综述

doi: 10.11999/JEIT230703
基金项目: 国家重点研发计划(2023YFB4503203),国家自然科学基金(62372447, 61932019)
详细信息
    作者简介:

    戴怡然:女,博士生,研究方向为全同态加密

    张江:男,副研究员,研究方向为公钥密码可证明安全理论、抗量子密码、多方安全计算协议设计与分析研究

    向斌武:男,博士生,研究方向为抗量子密码算法的设计与安全性分析、 全同态加密

    邓燚:男,研究员,研究方向为零知识证明、安全归约方法

    通讯作者:

    邓燚 deng@iie.ac.cn

  • 11) 通常自举算法只需自举密钥与密文做乘法即可同时完成密文的解密与重加密
  • 22) 每个明文槽都只包含字段(或环)的一个元素,而不是扩展字段(或环)。
  • 中图分类号: TN918.4; TP309

Overview on the Research Status and Development Route of Fully Homomorphic Encryption Technology

Funds: The National Key Research and Development Project of China (2023YFB4503203), The National Natural Science Foundation of China (62372447, 61932019)
  • 摘要: 随着物联网、云计算、人工智能的应用与普及,数据安全与隐私保护成为人们关注的焦点。全同态加密,作为隐私安全问题的有效解决办法,允许对加密数据执行任意同态计算,是一种强大的加密工具,具有广泛的潜在应用。该文总结了自2009年以来提出全同态加密方案,并根据方案的核心技术划分成4条技术路线,分析讨论了各类方案的关键构造,算法优化进程和未来发展方向。首先,全面介绍了全同态加密相关的数学原理,涵盖了全同态加密方案的基础假设和安全特性。随后,按照4条全同态加密方案的技术路线,归纳了加密方案的结构通式,总结了自举算法的核心步骤,讨论了最新研究进展,并在此基础上综合分析比较了各类方案的存储效率及运算速度。最后,展示了同态算法库对每条技术路线下加密方案的应用实现情况,分析了在当前时代背景下全同态加密方案的机遇与挑战,并对未来的研究前景做出了展望。
  • 图  1  全同态加密的不同技术路线分支及其代表性方案

    表  1  Andrey Kim团队对BFV和BGV方案的算法优化

    BFV BGV 优化效果
    $\left\lfloor {\dfrac{q}{t}} \right\rfloor m \to \left\lfloor {\dfrac{{qm}}{t}} \right\rfloor $预计算$qm$ \ 降低初始噪声
    将乘法中的模切换步骤置于重线性化之后 \ 降低模切换维数
    将BFV的模数分层,乘法之后切换到小模数 \ 减缓噪声增长速度
    \ 静态噪声管理 增强方案的实用性
    下载: 导出CSV

    表  2  CKKS 类全同态加密方案自举的不同近似函数及自举精度对比

    方案名称 近似函数(方法) 自举精度(bit)
    CHKKS[31] $ \sin \left( {\dfrac{{2\pi x}}{q}} \right) \approx x\text{mod} q $ 24
    LLLK[32] $\left( {\dfrac{{2\pi x}}{q}} \right)\arcsin \left( {\sin \left( {\dfrac{{2\pi x}}{q}} \right)} \right) = x\text{mod} q$ 40.5
    JM[33] $\dfrac{q}{{2\pi }}\mathop \sum \limits_{k = 1}^n {\beta _k}{\text{sin}}\left( {\dfrac{{2\pi kx}}{q}} \right) \approx x\text{mod} q$ 44
    BCCKK[24] META BTS 255
    下载: 导出CSV

    表  3  4条技术路线全同态加密方案对比

    Gentry类 BGV类 GSW类 CKKS类
    基础假设 理想格 LWE RLWE (R)LWE RLWE
    密文空间 ${\mathbb{Z}_d}$ $\mathbb{Z}_q^n$ $R_q^n$ $\mathbb{Z}_q^{n \times n}$ $R_q^n$
    密文大小 $f\left( \lambda \right)$ $\left( {n + 1} \right)\left\lceil {\log_2 q} \right\rceil $ $2n\left\lceil {\log_2 q} \right\rceil $ ${\left( {n + 1} \right)^2}{\left\lceil {\log_2 q} \right\rceil ^3}$ $2n\left\lceil {\log_2 q} \right\rceil $
    明文空间 ${\mathbb{Z}_2}$ ${\mathbb{Z}_t}$ ${R_t}$ ${\mathbb{Z}_2}$ \
    单个密文存储明文数 1 1 n 1 n
    公钥大小 $s \cdot \left\lceil {2\sqrt S } \right\rceil \cdot {\log _2}d$ $2n\left( {n + 1} \right){\log_2}q$ $2n\left\lceil {\log_2 q} \right\rceil $ $2n\left( {n + 1} \right){\log_2}q$ $2n\left\lceil {\log_2 q} \right\rceil $
    是否支持消息打包 \ 暂不支持
    是否支持SIMD \ 暂不支持
    同态乘法噪声增长速度 ${N^{{{\Omega }}\left( 1 \right)}}$ $O\left( {{n^2}} \right)$ $O\left( {{n^2}} \right)$ $O\left( n \right)$ $O\left( {{n^2}} \right)$
    (平均)单比特自举时间 30 min \ 1.3 ms 13 ms 6.43 s
    下载: 导出CSV

    表  4  不同实现库的应用特点对比

    实现库名称 实现语言 支持加密方案 自举 特色功能
    Helib C++ BGV, CKKS 支持HE 汇编语言
    SEAL C++ BFV, CKKS 跨平台编译
    PALISADE C++ BGV, BFV, CKKS, FHEW, TFHE 跨平台编译,BGV/BFV/CKKS的多方扩展
    TFHE C/C++ GSW, FHEW, TFHE 可编程自举
    HEAAN C++ CKKS GPU加速
    NFLlib C++ \ \ 基于NTT的快速格计算
    cuFHE C++ TFHE CUDA加速
    Lattigo Go BGV, BFV, CKKS 跨平台编译,剩余数系统(RNS)
    OpenFHE C++ BGV, BFV, CKKS, FHEW, TFHE 剩余数系统(RNS),
    BGV/BFV/CKKS的多方扩展
    下载: 导出CSV
  • [1] BRICKELL E F and YACOBI Y. On privacy homomorphisms (Extended Abstract)[C]. The Workshop on the Theory and Application of Cryptographic Techniques, Amsterdam, The Netherlands, 1988: 117–125. doi: 10.1007/3-540-39118-5_12.
    [2] CRAMER R, DAMGÅRD I, and NIELSEN J B. Multiparty computation from threshold homomorphic encryption[C]. The International Conference on the Theory and Application of Cryptographic Techniques, Innsbruck, Austria, 2001: 280–300. doi: 10.1007/3-540-44987-6_18.
    [3] RIVEST R L, ADLEMAN L, and DERTOUZOS M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169–179.
    [4] ELGAMAL T. A public key cryptosystem and a signature scheme based on discrete logarithms[M]. BLAKLEY G R and CHAUM D. Advances in Cryptology. Berlin Heidelberg: Springer, 1985: 10–18. doi: 10.1007/3-540-39568-7_2.
    [5] RIVEST R L, SHAMIR A, and ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120–126. doi: 10.1145/359340.359342.
    [6] BONEH D, GOH E J, and NISSIM K. Evaluating 2-DNF formulas on ciphertexts[C]. The Second Theory of Cryptography Conference, Cambridge, USA, 2005: 325–341. doi: 10.1007/978-3-540-30576-7_18.
    [7] BEHERA S and PRATHURI J R. Design of novel hardware architecture for fully homomorphic encryption algorithms in FPGA for real-time data in cloud computing[J]. IEEE Access, 2022, 10: 131406–131418. doi: 10.1109/ACCESS.2022.3229892.
    [8] LI Juyan, QIAO Zhiqi, ZHANG Kejia, et al. A lattice-based homomorphic proxy re-encryption scheme with strong anti-collusion for cloud computing[J]. Sensors, 2021, 21(1): 288. doi: 10.3390/s21010288.
    [9] LEE J W, KANG H, LEE Y, et al. Privacy-preserving machine learning with fully homomorphic encryption for deep neural network[J]. IEEE Access, 2022, 10: 30039–30054. doi: 10.1109/ACCESS.2022.3159694.
    [10] 李腾, 方保坤, 马卓, 等. 基于同态加密的医疗数据密文异常检测方法[J]. 中国科学: 信息科学, 2023, 53(7): 1368–1391. doi: 10.1360/SSI-2022-0214.

    LI Teng, FANG Baokun, MA Zhuo, et al. Homomorphic encryption-based ciphertext anomaly detection method for e-health records[J]. Scientia Sinica Informationis, 2023, 53(7): 1368–1391. doi: 10.1360/SSI-2022-0214.
    [11] GENTRY C. Fully homomorphic encryption using ideal lattices[C]. The 41st Annual ACM Symposium on Theory of Computing, Bethesda, USA, 2009: 169–169. doi: 10.1145/1536414.1536440.
    [12] PEREIRA H V L. Bootstrapping fully homomorphic encryption over the integers in less than one second[C/OL]. The 24th IACR International Conference on Practice and Theory of Public Key Cryptography, 2021. doi: 10.1007/978-3-030-75245-3_13.
    [13] BONTE C, ILIASHENKO I, PARK J, et al. FINAL: Faster FHE instantiated with NTRU and LWE[C]. The 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, China, 2022. doi: 10.1007/978-3-031-22966-4_7.
    [14] KLUCZNIAK K. NTRU-v-um: Secure fully homomorphic encryption from NTRU with small modulus[C]. The 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, USA, 2022: 1783–1797. doi: 10.1145/3548606.3560700.
    [15] XIANG Binwu, ZHANG Jiang, DENG Yi, et al. Fast blind rotation for bootstrapping FHEs[C]. The 43rd Annual International Cryptology Conference, Santa Barbara, USA, 2023. doi: 10.1007/978-3-031-38551-3_1.
    [16] STEHLÉ D, STEINFELD R, TANAKA K, et al. Efficient public key encryption based on ideal lattices[C]. The 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, 2009. doi: 10.1007/978-3-642-10366-7_36.
    [17] SVP challenge[EB/OL]. https://www.latticechallenge.org/svp-challenge/.
    [18] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[C]. Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, Baltimore, USA, 2005: 84–93. doi: 10.1145/1060590.1060603.
    [19] BLUM A, FURST M, KEARNS M, et al. Cryptographic primitives based on hard learning problems[C]. The 13th Annual International Cryptology Conference, Santa Barbara, USA, 1994. doi: 10.1007/3-540-48329-2_24.
    [20] BRAKERSKI Z and VAIKUNTANATHAN V. Fully homomorphic encryption from ring-LWE and security for key dependent messages[C]. The 31st Annual Cryptology Conference, Santa Barbara, USA, 2011. doi: 10.1007/978-3-642-22792-9_29.
    [21] GENTRY C, HALEVI S, and VAIKUNTANATHAN V. i-Hop homomorphic encryption and rerandomizable Yao circuits[C]. The 30th Annual Cryptology Conference, Santa Barbara, USA, 2010. doi: 10.1007/978-3-642-14623-7_9.
    [22] KITAGAWA F and MATSUDA T. Circular security is complete for KDM security[C]. The 26th International Conference on the Theory and Application of Cryptology and Information Security, Daejeon, South Korea, 2020. doi: 10.1007/978-3-030-64837-4_9.
    [23] BRAKERSKI Z and VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[C]. The IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, USA, 2011: 97–106. doi: 10.1109/FOCS.2011.12.
    [24] GENTRY C, SAHAI A, and WATERS B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based[C]. The 33rd Annual Cryptology Conference, Santa Barbara, USA, 2013. doi: 10.1007/978-3-642-40041-4_5.
    [25] CHEON J H, KIM A, KIM M, et al. Homomorphic encryption for arithmetic of approximate numbers[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017. doi: 10.1007/978-3-319-70694-8_15.
    [26] GENTRY C. Computing arbitrary functions of encrypted data[J]. Communications of the ACM, 2010, 53(3): 97–105. doi: 10.1145/1666420.1666444.
    [27] GENTRY C and HALEVI S. Implementing Gentry’s fully-homomorphic encryption scheme[C]. The 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, 2011: 129–148. doi: 10.1007/978-3-642-20465-4_9.
    [28] GENTRY C and HALEVI S. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits[C]. The IEEE 52nd Annual Symposium on Foundations of Computer Science, Palm Springs, USA, 2011. doi: 10.1109/FOCS.2011.94.
    [29] GENTRY C, HALEVI S, and SMART N P. Better bootstrapping in fully homomorphic encryption[C]. The 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, 2012: 1–16. doi: 10.1007/978-3-642-30057-8_1.
    [30] BRAKERSKI Z, GENTRY C, and VAIKUNTANATHAN V. (Leveled) fully homomorphic encryption without bootstrapping[C]. The 3rd Innovations in Theoretical Computer Science Conference, Cambridge, USA, 2012. doi: 10.1145/2090236.2090262.
    [31] CHEON J H, HAN K, KIM A, et al. Bootstrapping for approximate homomorphic encryption[C]. The 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tel Aviv, Israel, 2018. DOI: 10.1007/978-3-319-78381-9_14.
    [32] LEE J W, LEE E, LEE Y, et al. High-precision bootstrapping of RNS-CKKS homomorphic encryption using optimal minimax polynomial approximation and inverse sine function[C]. The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 2021. doi: 10.1007/978-3-030-77870-5_22.
    [33] JUTLA C S and MANOHAR N. Sine series approximation of the mod function for bootstrapping of approximate HE[R]. Paper 2021/572, 2021.
    [34] BAE Y, CHEON J H, CHO W, et al. META-BTS: Bootstrapping precision beyond the limit[C]. The 2022 ACM SIGSAC Conference on Computer and Communications Security, Los Angeles, USA, 2022: 223–234. doi: 10.1145/3548606.3560696.
    [35] LI Baiyu and MICCIANCIO D. On the security of homomorphic encryption on approximate numbers[C]. The 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, 2021. doi: 10.1007/978-3-030-77870-5_23.
    [36] LI Baiyu, MICCIANCIO D, SCHULTZ M, et al. Securing approximate homomorphic encryption using differential privacy[R]. Paper 2022/816, 2022.
    [37] FAN Junfeng and VERCAUTEREN F. Somewhat practical fully homomorphic encryption[R]. Paper 2012/144, 2012.
    [38] GENTRY C, HALEVI S, and SMART N P. Fully homomorphic encryption with polylog overhead[C]. The 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, 2012. doi: 10.1007/978-3-642-29011-4_28.
    [39] GENTRY C, HALEVI S, and SMART N P. Homomorphic evaluation of the AES circuit[C]. The 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012. doi: 10.1007/978-3-642-32009-5_49.
    [40] HALEVI S and SHOUP V. Algorithms in HElib[C]. The 34th Annual Cryptology Conference, Santa Barbara, USA, 2014. doi: 10.1007/978-3-662-44371-2_31.
    [41] HALEVI S and SHOUP V. Design and implementation of HElib: A homomorphic encryption library[R]. Paper 2020/1481, 2020.
    [42] HALEVI S and SHOUP V. Bootstrapping for HElib[J]. Journal of Cryptology, 2021, 34(1): 7. doi: 10.1007/s00145-020-09368-7.
    [43] KIM A, POLYAKOV Y, and ZUCCA V. Revisiting homomorphic encryption schemes for finite fields[C]. Proceedings of the 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2021. DOI: 10.1007/978-3-030-92078-4_21.
    [44] ALPERIN-SHERIFF J and PEIKERT C. Faster bootstrapping with polynomial error[C]. The 34th Annual Cryptology Conference, Santa Barbara, USA, 2014: 297–314. doi: 10.1007/978-3-662-44371-2_17.
    [45] DUCAS L and MICCIANCIO D. FHEW: Bootstrapping homomorphic encryption in less than a second[C]. The 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, 2015: 617–640. doi: 10.1007/978-3-662-46800-5_24.
    [46] CHILLOTTI I, GAMA N, GEORGIEVA M, et al. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016. DOI: 10.1007/978-3-662-53887-6_1.
    [47] MYERS S and SHULL A. Practical revocation and key rotation[C]. The Cryptographers’ Track at the RSA Conference 2018, San Francisco, USA, 2018. DOI: 10.1007/978-3-319-76953-0_9.
    [48] LIU Fenghao and WANG Han. Batch bootstrapping II: Bootstrapping in polynomial modulus only requires $ O(1) $ FHE multiplications in amortization[C]. The 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 2023: 353–384. doi: 10.1007/978-3-031-30620-4_12.
    [49] LIU Fenghao and WANG Han. Batch bootstrapping I: A new framework for SIMD bootstrapping in polynomial modulus[C]. The 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 2023: 321–352. doi: 10.1007/978-3-031-30620-4_11.
    [50] MICCIANCIO D and REGEV O. Lattice-based cryptography[M]. BERNSTEIN D J, BUCHMANN J, and DAHMEN E. Post-Quantum Cryptography. Berlin, Heidelberg: Springer, 2009. doi: 10.1007/978-3-540-88702-7_5.
    [51] AJTAI M. Generating hard instances of lattice problems (extended abstract)[C]. The Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 99–108. doi: 10.1145/237814.237838.
    [52] LYUBASHEVSKY V, PEIKERT C, and REGEV O. On ideal lattices and learning with errors over rings[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010. doi: 10.1007/978-3-642-13190-5_1.
    [53] DUCAS L and DURMUS A. Ring-LWE in polynomial rings[C]. The 15th International Conference on Practice and Theory in Public Key Cryptography, Darmstadt, Germany, 2012: 34–51. doi: 10.1007/978-3-642-30057-8_3.
    [54] SMART N P and VERCAUTEREN F. Fully homomorphic SIMD operations[J]. Designs, Codes and Cryptography, 2014, 71(1): 57–81. doi: 10.1007/s10623-012-9720-4.
    [55] Homenc. HElib[EB/OL].https://github.com/homenc/HElib.
    [56] Microsoft. SEAL[EB/OL]. https://github.com/microsoft/SEAL.
    [57] Openfheorg. Openfhe-development[EB/OL]. https://github.com/openfheorg/openfhe-development.
    [58] Tfhe. Tfhe[EB/OL].https://github.com/tfhe/tfhe.
    [59] Snucrypto. HEAAN[EB/OL]. https://github.com/snucrypto/HEAAN.
    [60] CHOWDHURY S, SINHA S, SINGH A, et al. Efficient threshold FHE with application to real-time systems[R]. Paper 2022/1625, 2022.
    [61] YUAN Minghao, WANG Dongdong, ZHANG Feng, et al. An examination of multi-key fully homomorphic encryption and its applications[J]. Mathematics, 2022, 10(24): 4678. doi: 10.3390/math10244678.
    [62] PARK J and ROVIRA S. Efficient TFHE bootstrapping in the multiparty setting[R]. Paper 2023/759, 2023.
    [63] DI GIUSTO A and MARCOLLA C. Breaking the power-of-two barrier: Noise estimation for BGV in NTT-friendly rings[R]. Paper 2023/783, 2023.
    [64] CHEN Hao, ILIASHENKO I, and LAINE K. When HEAAN Meets FV: A new somewhat homomorphic encryption with reduced memory overhead[C]. The 18th IMA International Conference, 2021. doi: 10.1007/978-3-030-92641-0_13.
    [65] AUNG K M M, LIM E, SIM J J, et al. Field instruction multiple data[R]. Paper 2022/771, 2022.
    [66] LI Zengpeng and WANG Ding. Achieving one-round password-based authenticated key exchange over lattices[J]. IEEE Transactions on Services Computing, 2022, 15(1): 308–321. doi: 10.1109/TSC.2019.2939836.
    [67] WANG Qingxuan, WANG Ding, CHENG Chi, et al. Quantum2FA: Efficient quantum-resistant two-factor authentication scheme for mobile devices[J]. IEEE Transactions on Dependable and Secure Computing, 2023, 20(1): 193–208. doi: 10.1109/TDSC.2021.3129512.
  • 加载中
图(1) / 表(4)
计量
  • 文章访问数:  452
  • HTML全文浏览量:  104
  • PDF下载量:  108
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-09-28
  • 修回日期:  2024-01-22
  • 网络出版日期:  2024-05-12
  • 刊出日期:  2024-05-10

目录

    /

    返回文章
    返回