Optimized Relinearization Algorithm of the Multikey Homomorphic Encryption Scheme

Multikey homomorphic encryption (MKHE) supports arbitrary homomorphic evaluation on the ciphertext of different users and thus can be applied to scenarios involving multiusers (e.g., cloud computing and artificial intelligence) to protect user privacy. CDKS19 is the current most efficient MKHE scheme, and its relinearization process consumes most of the time of homomorphic evaluation. In this study, an optimized relinearization algorithm of CDKS19 is proposed. This algorithm reorganizes the evaluation key during the key generation process, decreases the complexity of relinearization, and reduces the error growth rate during homomorphic evaluation. First, we reduce the scale of the evaluation key by increasing its modulus instead of using a gadget vector to decompose the user’s public key and extend the ciphertext of homomorphic multiplication. Second, we use rescaling technology to optimize the relinearization algorithm; thus, the error bound of the ciphertext is reduced, and the homomorphic operation efficiency is improved. Lastly, the average-case error estimation on the variances of polynomial coefficients and the upper bound of the canonical embedding map are provided. Results show that our scheme reduces the scale of the evaluation key, the error variance, and the computational cost of the relinearization process. Our scheme can effectively perform the homomorphic multiplication of ciphertexts.