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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
Multi-key homomorphic encryptionLWERLWELeakage resilient cryptography.
Contact author(s)
daixiaokang @ cigit ac cn
History
2022-02-15: last of 3 revisions
2022-01-18: received
See all versions
Short URL
https://ia.cr/2022/055
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/055,
      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{https://eprint.iacr.org/2022/055}},
      url = {https://eprint.iacr.org/2022/055}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.