Paper 2022/055

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

Xiaokang Dai, Wenyuan Wu, and Yong Feng

Abstract

Multi-key Fully Homomorphic Encryption(\MK) based on Learning With Error(\LWE) usually lifts ciphertexts of different users to new ciphertexts under a common public key to enable homomorphic evaluation. The main obstacle of current \MK schemese in applications is huge ciphertext expansion cost especially in data intensive scenario. For example, for an boolean circuit with input length $N$, multiplication depth $L$, security parameter $\lambda$ , the number of additional encryptions introduced to obtain ciphertext expansion is $O(N\lambda^6L^4)$. In this paper we present a framework to slove this problem that we call Key-Lifting Multi-key Fully Homomorphic Encryption (\KL). By introducing a key lifting procedure, the number of encryptio for a local user is pulled back to $O(N)$. Moreover, current \MK schemes are often based on Common Reference String model(\CRS). In our \textsf{LWE-based} scheme, \CRS is removed by using the leak resilient property of the leftover hash lemma(\LHL). Due to the structural properties of polynomial rings, such \textsf{LWE-based} scheme cannot be trivially transplanted to \textsf{RLWE-based} scheme. We give a \textsf{RLWE-based \KL} under Random Oracle Model(\ROM) by introduing a bit commitment protocal.