Research Article
Efficient RLWE-Based Multi-key Fully Homomorphic Encryption Without Key-Switching
@INPROCEEDINGS{10.1007/978-3-030-89814-4_24, author={Xiaoliang Che and Yao Liu and Shangwen Zheng and Longfei Liu and Tanping Zhou and Xiaoyuan Yang and Xu An Wang}, title={Efficient RLWE-Based Multi-key Fully Homomorphic Encryption Without Key-Switching}, proceedings={Mobile Multimedia Communications. 14th EAI International Conference, Mobimedia 2021, Virtual Event, July 23-25, 2021, Proceedings}, proceedings_a={MOBIMEDIA}, year={2021}, month={11}, keywords={Multi-key fully homomorphic encryption Key-switching technique Relinearization algorithm The time complexity}, doi={10.1007/978-3-030-89814-4_24} }- Xiaoliang Che
Yao Liu
Shangwen Zheng
Longfei Liu
Tanping Zhou
Xiaoyuan Yang
Xu An Wang
Year: 2021
Efficient RLWE-Based Multi-key Fully Homomorphic Encryption Without Key-Switching
MOBIMEDIA
Springer
DOI: 10.1007/978-3-030-89814-4_24
Abstract
The previous leveled BGV-type MKFHE schemes (e.g. CZW17, LZY+19) based on the standard RLWE assumption are implemented by using key-switching and modulus-switching techniques. However, the frequent usage of key-switching causes the low efficiency of homomorphic multiplication operation. The CDKS19 scheme proposed two new simpler and faster relinearization algorithms, which supported the homomorphic computation with certain circuit depth. However, the construction that satisfies the fully homomorphic computation was not designed, and its relinearization performance can be further optimized.
In this paper, a more efficient leveled BGV-type MKFHE scheme without key-switching is constructed. Firstly, the generation method of evaluation key is improved, and two optimized generation algorithms of relinearization key are proposed. Secondly, following the relinearization algorithm framework of CDKS19, two efficient relinearization algorithms are proposed. The new algorithms are much faster to re-linearize the product of ciphertexts. Finally, using the optimized relinearization algorithms to replace the key-switching technology logically, and combining the modulus-switching technology, an efficient leveled MKFHE is constructed.
The results show that our MKFHE scheme is IND-CPA secure based on the standard RLWE assumption, and supports any parties dynamically join the homomorphic computation at any time. Moreover, the time complexity of relinearization and decryption is less than that of CDKS19. So it is a leveled BGV-type MKFHE scheme with more efficient homomorphic computation.
