Interactive Ciphertext Expansion for Dynamic Multi-Key Fully Homomorphic Encryption

doi:10.19678/j.issn.1000-3428.0252104

Abstract

Abstract: Fully Homomorphic Encryption (FHE) is a class of encryption schemes that enables the direct computation of encrypted data. Most of the existing FHE schemes are based on standard Learning with Errors (LWE) assumptions. Multi-Key Fully Homomorphic Encryption (MKFHE) is an advanced variant of FHE that supports computation over ciphertexts encrypted using different public keys. Numerous MKFHE schemes that offer various improvements in security and efficiency have been proposed. However, traditional MKFHE schemes do not support dynamic scalability and are typically limited to computations with a fixed number of keys. They also face challenges such as significant ciphertext expansion and insufficient security guarantees. To address these issues, this paper proposes a cloud-assisted interactive ciphertext expansion mechanism and designs a dynamic multi-key FHE scheme based on LWE within an asymmetric cryptographic framework. This scheme allows the dynamic inclusion of new users with additional keys into computations over fresh, evaluated, or previously expanded ciphertexts. This is achieved by constructing intermediate ciphertexts and block matrices that enable the compatibility and expansion of ciphertexts for newly participating users. Each participant generates auxiliary ciphertexts by committing to their secret key, and the cloud performs computations by combining these auxiliary data with the original ciphertext. This ensures that the expanded ciphertext correctly embeds the original plaintext and preserves decryption accuracy. Compared with existing constructions, our scheme achieves smaller parameter sizes. Furthermore, the ciphertext expansion process is interactive. It distributes a small computational burden to users while reducing the computational overhead on the cloud server, thereby lowering the service costs charged to users and improving the efficiency of ciphertext expansion. In addition, the proposed MKFHE scheme preserves computational accuracy and semantic security by relying solely on the hardness of the standard LWE assumption.

Key words: Multi-Key Fully Homomorphic Encryption (MKFHE), ciphertext expansion, Gentry—Sahai—Waters (GSW) homomorphic encryption, Learning with Errors (LWE) problem, encryption technology

摘要： 全同态加密（FHE）是一类可以在加密数据上进行计算的加密方案。现有的全同态加密方案通常基于标准的容错学习（LWE）假设来实现。多密钥全同态加密(MKFHE)是全同态加密的一种高级变体，其允许在不同密钥下对加密数据进行运算处理。目前已经有许多方案被提出，带来了在安全性和效率方面的各种改进。然而传统多密钥全同态加密不支持动态扩展，仅能在密钥数量固定的情景下进行运算，同时还存在密文扩展开销大、安全性不足等挑战。为了解决上述问题，设计了一个云端与参与方交互式进行密文扩展的构造方法，基于LWE提出了一种非对称密码体制的动态多密钥全同态加密方案。该方案允许对新鲜的、运算后的或已扩展密文，动态引入拥有额外密钥的新用户，并通过构造中间密文和分块矩阵的方式，实现密文对新参与方的兼容扩展。各参与方对自身私钥进行承诺生成辅助密文，云端结合这些辅助信息与原密文进行计算，使扩展后的密文结构能够嵌入原始明文信息并保证解密正确性。与现有的构造方法相比，本文方法具有更小的参数尺寸，且密文扩展过程为交互式的，让用户承担少量计算负担，同时降低了云服务器的计算量，即降低了用户向云服务器提供商支付的费用，使得密文扩展更高效。此外，提出的多密钥全同态加密方案保持运算正确性和语义安全，依赖于标准LWE假设的困难性。

关键词: 多密钥全同态加密, 密文扩展, GSW同态加密, 容错学习问题, 加密技术

CLC Number:

TP309

LI Zaidong, CHEN Yuling, WANG Xuewei, LUO Yun. Interactive Ciphertext Expansion for Dynamic Multi-Key Fully Homomorphic Encryption[J]. Computer Engineering, 2026, 52(11): 284-294.

李再东, 陈玉玲, 王学伟, 罗运. 交互式密文扩展的动态多密钥全同态加密[J]. 计算机工程, 2026, 52(11): 284-294.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0252104

https://www.ecice06.com/EN/Y2026/V52/I11/284

References

[1] 唐莹莹, 陈玉玲, 罗运, 等. 基于全同态加密的可验证多关键词密文检索方案[J]. 计算机工程, 2025, 51(4): 188-197.TANG Y Y, CHEN Y L, LUO Y, et al. Verifiable multi-keyword ciphertext retrieval scheme based on fully homomorphic encryption[J]. Computer Engineering, 2025, 51(4): 188-197. (in Chinese)
[2] ASHAROV G, JAIN A, LÓPEZ-ALT A, et al. Multiparty computation with low communication, computation and interaction via threshold FHE[C]//Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2012: 483-501.
[3] LÓPEZ-ALT A, TROMER E, VAIKUNTANATHAN V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C]//Proceedings of the 44th Annual ACM Symposium on Theory of Computing. New York, USA: ACM Press, 2012: 1219-1234.
[4] REGEV O. On lattices, learning with errors, random linear codes, and cryptography[J]. Journal of the ACM, 2009, 56(6): 1-40.
[5] LYUBASHEVSKY V, PEIKERT C, REGEV O. On ideal lattices and learning with errors over rings[C]//Proceedings of the 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2010: 1-23.
[6] HOFFSTEIN J, PIPHER J, SILVERMAN J H. NTRU: a ring-based public key cryptosystem[M]//BUHLER J P. Algorithmic number theory. Berlin, Germany: Springer, 1998: 267-288.
[7] 徐科鑫, 王丽萍. 多方全同态加密研究进展[J]. 密码学报(中英文), 2024, 11(4): 719-739.XU K X, WANG L P. Research progress on multi-party fully homomorphic encryption[J]. Journal of Cryptologic Research, 2024, 11(4): 719-739. (in Chinese)
[8] 李习习, 唐春明, 胡业周. 支持多比特加密的多密钥全同态加密体制[J]. 密码学报, 2022, 9(2): 248-256. LI X X, TANG C M, HU Y Z. Multi-key fully homomorphic encryption system that supports multi-bit encryption[J]. Journal of Cryptologic Research, 2022, 9(2): 248-256. (in Chinese)
[9] CHEN H, DAI W, KIM M, et al. Efficient multi-key homomorphic encryption with packed ciphertexts with application to oblivious neural network inference[C]//Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. New York, USA: ACM Press, 2019: 395-412.
[10] HOFMANN T, BASILICO J. Collaborative machine learning[M]//HEMMJE M, NIEDERÉE C, RISSE T. From integrated publication and information systems to information and knowledge environments. Berlin, Germany: Springer, 2005: 173-182.
[11] WANG J B, PAL A, YANG Q L, et al. Collaborative machine learning: schemes, robustness, and privacy[J]. IEEE Transactions on Neural Networks and Learning Systems, 2023, 34(12): 9625-9642.
[12] BRAKERSKI Z, GENTRY C, VAIKUNTANATHAN V. (Leveled) Fully homomorphic encryption without bootstrapping[J]. ACM Transactions on Computation Theory, 2014, 6(3): 1-36.
[13] LI N B, ZHOU T P, YANG X Y, et al. Two round multiparty computation via multi-key fully homomorphic encryption with faster homomorphic evaluations[EB/OL]. [2025-01-02]. https://eprint.iacr.org/2018/1249.
[14] CHE X L, ZHOU T P, LI N B, et al. Modified multi-key fully homomorphic encryption based on NTRU cryptosystem without key-switching[J]. Tsinghua Science and Technology, 2020, 25(5): 564-578.
[15] MOUCHET C, TRONCOSO-PASTORIZA J, BOSSUAT J P, et al. Multiparty homomorphic encryption from ring-learning-with-errors[J]. Proceedings on Privacy Enhancing Technologies, 2021(4): 291-311.
[16] FAN J F, VERCAUTEREN F. Somewhat practical fully homomorphic encryption[EB/OL]. [2025-01-02]. https://eprint.iacr.org/2012/144.
[17] CLEAR M, MCGOLDRICK C. Multi-identity and multi-key leveled FHE from learning with errors[C]//Proceedings of the 35th Annual Cryptology Conference. Berlin, Germany: Springer, 2015: 630-656.
[18] GENTRY C, SAHAI A, WATERS B. Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based[C]//Proceedings of the 33rd Annual Cryptology Conference. Berlin, Germany: Springer, 2013: 75-92.
[19] MUKHERJEE P, WICHS D. Two round multiparty computation via multi-key FHE[C]//Proceedings of the 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2016: 735-763.
[20] PEIKERT C, SHIEHIAN S. Multi-key FHE from LWE, revisited[C]//Proceedings of TCC 2016. Berlin, Germany: Springer, 2016: 217-238.
[21] BRAKERSKI Z, PERLMAN R. Lattice-based fully dynamic multi-key FHE with short ciphertexts[C]//Advances in Cryptology-CRYPTO 2016. Berlin, Germany: Springer, 2016: 190-213.
[22] CHEN Y L, DONG S, LI T, et al. Dynamic multi-key FHE in asymmetric key setting from LWE[J]. IEEE Transactions on Information Forensics and Security, 2021, 16: 5239-5249.
[23] BISWAS C, DUTTA R. Dynamic multi-key FHE in symmetric key setting from LWE without using common reference matrix[J]. Journal of Ambient Intelligence and Humanized Computing, 2022, 13(2): 1241-1254.
[24] LUO F C, WANG H Y, SAIF A K, et al. Multi-key fully homomorphic encryption without CRS from RLWE[J]. Computer Standards & Interfaces, 2023, 86: 103742.
[25] ZENG S C, HSU C, CUI J Q, et al. Efficient dynamic multi-key FHE scheme from LWE for untrusted cloud environments[C]//Proceedings of the 29th International Conference on Parallel and Distributed Systems (ICPADS). Ocean Flower Island, China: IEEE Press, 2023: 1039-1044.
[26] CHEN L, ZHANG Z F, WANG X Q. Batched multi-hop multi-key FHE from ring-LWE with compact ciphertext extension[C]//Proceedings of TCC 2017. Berlin, Germany: Springer, 2017: 597-627.
[27] CHEN H, CHILLOTTI I, SONG Y. Multi-key homomorphic encryption from TFHE[C]//Proceedings of the 25th International Conference on the Theory and Application of Cryptology and Information Security. Berlin, Germany: Springer, 2019: 446-472.
[28] BISWAS C, DUTTA R. Secure and efficient multi-key FHE scheme supporting multi-bit messages from LWE preserving non-interactive decryption[J]. Journal of Ambient Intelligence and Humanized Computing, 2023, 14(12): 16451-16464.
[29] LI Z P, MA C G, ZHOU H S. Multi-key FHE for multi-bit messages[J]. Science China Information Sciences, 2018, 61(2): 029101.
[30] MICCIANCIO D, PEIKERT C. Trapdoors for lattices: simpler, tighter, faster, smaller[C]//Proceedings of the 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Germany: Springer, 2012: 700-718.
[31] BRAKERSKI Z, VAIKUNTANATHAN V. Efficient fully homomorphic encryption from (standard) LWE[J]. SIAM Journal on Computing, 2014, 43(2): 831-871.
[32] DU G, MA C G, LI Z P, et al. Towards fully homomorphic encryption from gentry-peikert-vaikuntanathan scheme[C]//Cloud Computing and Security. Berlin, Germany: Springer, 2017: 256-267.

Please choose a citation manager

Content to export