Concise and Efficient Multi-Identity Fully Homomorphic Encryption Scheme

Abstract

Combining multi-key fully homomorphic encryption (MKFHE) and identity-based encryption (IBE) to construct multi-identity based fully homomorphic encryption (MIBFHE) scheme can not only realize homomorphic operations and flexible access control on identity ciphertexts but also reduce the burden of public key certification management. However, MKFHE schemes used to construct MIBFHE usually have complex construction and large computational complexity, which also causes the same problem for MIBFHE schemes. To solve this problem, we construct a concise and efficient MIBFHE scheme based on the learning with errors (LWE) problem. Firstly, we construct an MKFHE scheme using a new method called “the decomposition method”. Secondly, we make a suitable deformation of the current IBE scheme. Finally, we combine the above MKFHE scheme with IBE scheme to construct our MIBFHE scheme and prove its IND-sID-CPA security under the LWE assumption in the random oracle model. The analysis results show that our MIBFHE scheme can generate the extended ciphertext directly from the encryption algorithm, without generating fresh ciphertext in advance. In addition, the noise expansion rate is reduced from the polynomial of lattice dimension n and modulus q to the constant K of the maximum number of users. The scale of introduced auxiliary ciphertexts is reduced from $\tilde {O}(n^{4}L^{4})$ to $\tilde {O}(n^{2}L^{4})$ when generating the extended ciphertext.

Keywords

• Multi-key
• multi-identity
• fully homomorphic encryption
• identity-based encryption