Welcome to the resource topic for 2022/055
Title:
Key lifting : Multi-key Fully Homomorphic Encryption in plain model without noise flooding in partial decryption
Authors: 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 leakage resilient property of the leftover hash lemma(\LHL). In particular, we noticed that as long as our encryption scheme is leakage-resilient, the partial decryption does not need to introduce noise flooding technique, and the semantic security of fresh ciphertext can also be guaranteed, which greatly compresses the modulus q and the computational overhead of the entire scheme. 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 protocol.
ePrint: https://eprint.iacr.org/2022/055
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .