# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 1 Introduction  
With the continuous development of cloud computing, cloud computing faces the security problem of how to ensure data privacy in the process of implementing applications. In 1978, [PERSON] et al. [1] proposed the idea of homomorphic encryption to protect data security. Homomorphic encryption has special properties that it can perform effective operations on ciphertext without decryption in the phase of processing data ciphertext, which is equivalent to encrypting the plaintext after corresponding operations. Therefore, how to construct a scheme with homomorphic properties became a difficult problem for cryptographers. Until 2009, [PERSON] [2] proposed the first FHE (full homomorphic encryption) scheme based on ideal lattice. Since then, FHE became a research hotspot in the field of cryptography. Cryptographers proposed a series of FHE schemes based on different theoretical foundations, including integer-based FHE schemes (such as [DGHV10] scheme [3]), RLWE-based (Ring Learning with Errors, RLWE) FHE schemes (such as [BV11a] scheme [4]), LWE-based FHE schemes (such as [BV11b, BGV12] scheme [5,6]) and FHE scheme with eigenvector (such as [GSW13] scheme [7]). As an important extension of the public key encryption systems, FHE needs to consider the problem of identity authentication in the cloud computing environment. The general method is to introduce public key certificates for authentication. However, the existence of public key certificates brought additional costs to the entire cryptosystem in all aspects such as computing, storage, communication and management. Additionally, the existing FHE systems generally have the problem of large public key size. In 1984, [PERSON] [8] first proposed the IBE (identity-based encryption) scheme. Its central idea is to generate a public key from the user's unique identity (such as e-mailaddress, mobile phone number, etc.) and public parameters, so that there is no need to issue an additional public key for each user. The user's secret key can be generated by the trusted third party center (Key Generate Center, KGC) using the identity and the system's master secret key. It eliminates the additional overhead associated with public key certificates and can manage keys more efficiently. Therefore, scholars began to study how to combine homomorphic encryption and identity-based encryption to construct the scheme of IBFHE (identity-based full homomorphic encryption), which has the advantages of FHE and IBE at the same time. It can not only perform access control and homomorphic operation on identity ciphertext, but also effectively manage the key. In 2010, [PERSON] [9] first proposed the open issue of how to construct identity-based full homomorphic encryption scheme at the CRYPTO'2010 conference. In 2013, [PERSON] et al. [7] constructed the first IBFHE scheme based on the LWE problem with the method of eigenvectors, and also proposed a transformation mechanism that can transform the IBE scheme satisfying the corresponding conditions into the related IBFHE scheme, which solved the above open problem to some extent. However, it is only applicable to single-identity encryption scenarios. It can only perform homomorphic operations on ciphertext encrypted under the same identity, and cannot perform homomorphic operations on ciphertext encrypted based on different identities. However, in many real-world scenarios, homomorphic-encrypted ciphertexts are usually encrypted under different identities. In 2014, [PERSON] and [PERSON] [10] constructed a multi-identity based full homomorphic encryption (MIBFHE) scheme. However, the construction largely depended on indistinguishable obfuscation [11]. Since it is difficult to realize indistinguishable obfuscation at present, the current efficiency is very low, and the security of the scheme cannot be based on a recognized computational problem. In 2015, [PERSON] and [PERSON] [12] extended the FHE scheme constructed by [PERSON] et al.