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
-
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} }