Paper 2022/055

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

Xiaokang Dai, Wenyuan Wu, and Yong Feng


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.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Multi-key homomorphic encryptionLWERLWELeakage resilient cryptography.
Contact author(s)
daixiaokang @ cigit ac cn
2022-02-15: last of 3 revisions
2022-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Xiaokang Dai and Wenyuan Wu and Yong Feng},
      title = {Key lifting : Multi-key Fully Homomorphic Encryption in plain model},
      howpublished = {Cryptology ePrint Archive, Paper 2022/055},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.