Efficient RLWE-Based Multi-key Fully Homomorphic Encryption Without Key-Switching

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.