Enhancing Multi-Key Fully Homomorphic Encryption with Efficient Key Switching and Batched Multi-Hop Computations
Source abstract
Abstract
Multi-Key Fully Homomorphic Encryption (MKFHE) offers a powerful solution for secure multi-party computations, where data encrypted under different keys can be jointly computed without decryption. However, existing MKFHE schemes still face challenges such as large parameter sizes, inefficient evaluation key generation, complex homomorphic multiplication processes, and limited scalability in multi-hop scenarios. In this paper, we propose an enhanced multi-hop MKFHE scheme based on the Brakerski-Gentry-Vaikuntanathan (BGV) framework. Our approach eliminates the need for an auxiliary Gentry-Sahai-Waters (GSW)-type scheme, simplifying the design and significantly reducing the public key size. We propose novel algorithms for evaluation key generation and key switching that simplify the computation while allowing each party to independently precompute and share its evaluation keys, thereby reducing both computational overhead and storage costs. Additionally, we combine the tensor product and key switching processes through homomorphic gadget decomposition, developing a new homomorphic multiplication algorithm and achieving linear complexity with respect to the number of parties. Furthermore, by leveraging the Polynomial Chinese Remainder Theorem (Polynomial CRT), we design a ciphertext packing technique that transforms our BGV-type MKFHE scheme into a batched scheme with improved amortized performance. Our schemes feature stronger multi-hop properties and operate without requiring a predefined maximum number of parties, offering enhanced flexibility and scalability compared to existing similar schemes.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Cryptography and Data Security · Security in Wireless Sensor Networks · Cryptographic Implementations and Security
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Computer and Electronic Information, Guangxi University, Nanning 530004, China
Funding
Guangxi Key Research and Development Program
References (33)
Show source-provided references
1. Gentry, C. (June, January 31). Fully homomorphic encryption using ideal lattices. Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, Bethesda, MD, USA.
2. Hamlin, A., Shelat, A., Weiss, M., and Wichs, D. (2018, January 25–29). Multi-key searchable encryption, revisited. Proceedings of the Public-Key Cryptography–PKC 2018: 21st IACR International Conference on Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil. Proceedings, Part I.10.1007/978-3-319-76578-5_4 ↗
3. Truly privacy-preserving federated analytics for precision medicine with multiparty homomorphic encryption10.1038/s41467-021-25972-y ↗
4. Graepel, T., Lauter, K., and Naehrig, M. (2012, January 28–30). ML confidential: Machine learning on encrypted data. Proceedings of the International Conference on Information Security and Cryptology, Seoul, Republic of Korea.10.1007/978-3-642-37682-5_1 ↗
5. (Leveled) fully homomorphic encryption without bootstrapping
6. Brakerski, Z. (2012, January 19–23). Fully homomorphic encryption without modulus switching from classical GapSVP. Proceedings of the Annual Cryptology Conference, Santa Barbara, CA, USA.10.1007/978-3-642-32009-5_50 ↗
7. Fan, J., and Vercauteren, F. (2025, April 04). Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive 2012. Available online: https://eprint.iacr.org/2012/144.
8. Gentry, C., Sahai, A., and Waters, B. (2013, January 18–22). Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Proceedings of the Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA. Proceedings, Part I.10.1007/978-3-642-40041-4_5 ↗
9. Cheon, J.H., Kim, A., Kim, M., and Song, Y. (2017, January 3–7). Homomorphic encryption for arithmetic of approximate numbers. Proceedings of the Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China. Proceedings, Part I.10.1007/978-3-319-70694-8_15 ↗
10. Chillotti, I., Gama, N., Georgieva, M., and Izabachene, M. (2016). Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. Advances in Cryptology–ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 4–8 December 2016, Springer. Proceedings, Part I.10.1007/978-3-662-53887-6_1 ↗
11. López-Alt, A., Tromer, E., and Vaikuntanathan, V. (2012, January 19–22). On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, USA.10.1145/2213977.2214086 ↗
12. Clear, M., and McGoldrick, C. (2015, January 16–20). Multi-identity and multi-key leveled FHE from learning with errors. Proceedings of the Advances in Cryptology—CRYPTO 2015: 35th Annual Cryptology Conference, Santa Barbara, CA, USA. Proceedings, Part II.10.1007/978-3-662-48000-7_31 ↗
13. Mukherjee, P., and Wichs, D. (2016, January 8–12). Two round multiparty computation via multi-key FHE. Proceedings of the Advances in Cryptology—EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria. Proceedings, Part II.10.1007/978-3-662-49896-5_26 ↗
14. Peikert, C., and Shiehian, S. (2016, January 1–3). Multi-key FHE from LWE, revisited. Proceedings of the Theory of Cryptography Conference, Beijing, China.10.1007/978-3-662-53644-5_9 ↗
15. Brakerski, Z., and Perlman, R. (2016, January 14–18). Lattice-based fully dynamic multi-key FHE with short ciphertexts. Proceedings of the Annual International Cryptology Conference, Santa Barbara, CA, USA.10.1007/978-3-662-53018-4_8 ↗
16. Chen, L., Zhang, Z., and Wang, X. (2017, January 12–15). Batched multi-hop multi-key FHE from ring-LWE with compact ciphertext extension. Proceedings of the Theory of Cryptography: 15th International Conference, TCC 2017, Baltimore, MD, USA. Proceedings, Part II.10.1007/978-3-319-70503-3_20 ↗
17. Efficient multi-key FHE with short extended ciphertexts and directed decryption protocol10.1109/ACCESS.2019.2913943 ↗
18. Chen, H., Chillotti, I., and Song, Y. (2019, January 8–12). Multi-key homomorphic encryption from TFHE. Proceedings of the Advances in Cryptology–ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan. Proceedings, Part II.10.1007/978-3-030-34621-8_16 ↗
19. Chen, H., Dai, W., Kim, M., and Song, Y. (2019, January 11–15). Efficient multi-key homomorphic encryption with packed ciphertexts with application to oblivious neural network inference. Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, London, UK.10.1145/3319535.3363207 ↗
20. Kim, T., Kwak, H., Lee, D., Seo, J., and Song, Y. (2023, January 26–30). Asymptotically faster multi-key homomorphic encryption from homomorphic gadget decomposition. Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security, Copenhagen, Denmark.10.1145/3576915.3623176 ↗
21. Hoffstein, J., Pipher, J., and Silverman, J.H. (1998, January 21–25). NTRU: A ring-based public key cryptosystem. Proceedings of the International Algorithmic Number Theory Symposium, Portland, OR, USA,.10.1007/BFb0054868 ↗
22. On lattices, learning with errors, random linear codes, and cryptography10.1145/1568318.1568324 ↗
23. On ideal lattices and learning with errors over rings10.1145/2535925 ↗
24. Zhou, T., Chen, L., Che, X., Liu, W., Zhang, Z., and Yang, X. (2025, April 04). Multi-key Fully Homomorphic Encryption Scheme with Compact Ciphertexts. Cryptology ePrint Archive 2021. Available online: https://eprint.iacr.org/2021/1131.
25. Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., and Wichs, D. (2012, January 15–19). Multiparty computation with low communication, computation and interaction via threshold FHE. Proceedings of the Advances in Cryptology—EUROCRYPT 2012: 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK. Proceedings 31.10.1007/978-3-642-29011-4_29 ↗
26. Gentry, C., Halevi, S., and Smart, N.P. (2012, January 15–19). Fully homomorphic encryption with polylog overhead. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK.10.1007/978-3-642-29011-4_28 ↗
27. Micciancio, D., and Peikert, C. (2012, January 15–19). Trapdoors for lattices: Simpler, tighter, faster, smaller. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK.10.1007/978-3-642-29011-4_41 ↗
28. Bajard, J.C., Eynard, J., Hasan, M.A., and Zucca, V. (2016, January 10–12). A full RNS variant of FV like somewhat homomorphic encryption schemes. Proceedings of the International Conference on Selected Areas in Cryptography, St. John’s, NL, Canada.10.1007/978-3-319-69453-5_23 ↗
29. Halevi, S., Polyakov, Y., and Shoup, V. (2019, January 4–8). An improved RNS variant of the BFV homomorphic encryption scheme. Proceedings of the Topics in Cryptology-CT-RSA 2019: The Cryptographers’ Track at the RSA Conference 2019, San Francisco, CA, USA. Proceedings.10.1007/978-3-030-12612-4_5 ↗
30. Ducas, L., and Micciancio, D. (2015, January 26–30). FHEW: Bootstrapping homomorphic encryption in less than a second. Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria.10.1007/978-3-662-46800-5_24 ↗
31. Probabilistic encryption10.1016/0022-0000(84)90070-9 ↗
32. Stehlé, D., and Steinfeld, R. (2011, January 15–19). Making NTRU as secure as worst-case problems over ideal lattices. Proceedings of the Advances in Cryptology—EUROCRYPT 2011: 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia. Proceedings 30.
33. Brakerski, Z., and Vaikuntanathan, V. (2011, January 14–18). Fully homomorphic encryption from ring-LWE and security for key dependent messages. Proceedings of the Annual Cryptology Conference, Santa Barbara, CA, USA.10.1007/978-3-642-22792-9_29 ↗