Paper 2022/055

Key lifting : Multi-key Fully Homomorphic Encryption in plain model without noise flooding

Abstract

Multi-key Fully Homomorphic Encryption (\MK), based on the Learning With Error assumption (\LWE), usually lifts ciphertexts of different users to new ciphertexts under a common public key to enable homomorphic evaluation. The efficiency of the current Multi-key Fully Homomorphic Encryption (\MK) scheme is mainly restricted by two aspects: Expensive ciphertext expansion operation : In a boolean circuit with input length $$, multiplication depth $$, security parameter $$, the number of additional encryptions introduced to achieve ciphertext expansion is $$. Noise flooding technology resulting in a large modulus $$ : In order to prove the security of the scheme, the noise flooding technology introduced in the encryption and distributed decryption stages will lead to a huge modulus $$, which corrodes the whole scheme and leads to sub-exponential approximation factors $$. This paper solves the first problem by presenting a framework called Key-Lifting Multi-key Fully Homomorphic Encryption (\KL). With this \emph{key lifting} procedure, the number of encryptions for a local user is reduced to $$, similar to single-key fully homomorphic encryption (\FHE). For the second problem, we prove the discrete Gaussian version of the Smudging lemma, and combined with the anti-leakage properties of the encryption, we remove the noise flooding technique introduced in the distributed decryption. Secondly, we propose an analysis method based on R\'{e}nyi divergence, which removes the noise flooding technology in the encryption stage. These approaches significantly reduces the size of the modulus $$ (with $$) and the computational overhead of the entire scheme.