# Efficient Multi-Identity Full Homomorphic Encryption Scheme on Lattice
## 1 Introduction
[7] to the first MIBFHE scheme based on the standard LWE problem (this scheme is called CM15 scheme), but the process of ciphertext expansion is complex and the noise growth is too fast. In 2019, [PERSON] et al. [13] made use of the transformation mechanism of [12] and combined with the hierarchical identity-based encryption scheme proposed by [PERSON] et al. [14] to construct a hierarchical multi-identity full homomorphic encryption scheme. In the same year, [PERSON] et al. [15] proposed a hierarchical multi-identity fully homomorphic encryption scheme based on the multi-key scheme of [PERSON] et al. [16]. In 2020, [PERSON] and [PERSON] [17] constructed a multi-identity multi-attribute MIBFHE scheme with chosen ciphertext security on the basis of multi-key full homomorphism, but their extension process uses Witness Pseudorandom Function (WPRF), which is a non-standard assumption. In 2021, [PERSON] et al. [18] constructed a compressible multi-key and multi-identity fully homomorphic encryption based on the compressible FHE scheme proposed by [PERSON] et al. [19]. In 2022, [PERSON] et al. [20] constructed a hierarchical multi-hop MIBFHE scheme based on the IBE scheme proposed by [PERSON] et al. [21] and the hierarchical multi-hop multi-key FHE scheme proposed by [PERSON] et al. [22]. The trapdoor generation of the above scheme is quite complex and too inefficient in terms of both operation and output's quality, which is not suitable for practice. It mainly used the trapdoor generation algorithm of [23; 24], which involves the calculation of complex HNF (Hermite Normal Forms) and matrix inversion operations. Although the dimension and quality of its output are asymptotically optimal, the hidden constant factor is quite large. In addition, the preimage sampling algorithm of [21] needs to perform high-precision real number orthogonalization iterative operation during the sampling process, resulting in high complexity of the preimage sampling. In 2012, [PERSON] et al. [25] proposed a new trapdoor generation algorithm and corresponding preimage sampling algorithm (this scheme is called MP12 scheme). Compared with the structure of [23; 24], it is essentially equivalent to one-time multiplication operation of two random matrices, which does not involve the calculation of complex HNF and matrix inversion operations. Its terms are chosen independently in the appropriate probability distribution, so it is more efficient. At the same time, [PERSON] also pointed out that MP12 trapdoor can be used to optimize all lattice-based IBE schemes, but no specific scheme is given. Our Contribution. In view of the above problems, in order to make the lattice MIBFHE scheme more practical, solving the problem of inefficient trapdoor generation must be considered. In this paper, we proposed an improved scheme using the transformation mechanism of [12]. First, based on the trapdoor function designed by [PERSON] et al. [25] and the IBE scheme of [PERSON] et al. [26], we proposed a new IBE scheme under the standard model, and proved that the scheme is IND-sID-CPA security under selective identity. Then, based on the above efficient IBE scheme and the eigenvector method proposed by [PERSON] et al. [7], which eliminate the evaluation key, the IBE scheme in this paper is transformed into a single-identity IBFHE scheme that satisfies homomorphic operation. Finally, a Link-Mask system was reconstructed based on the ciphertext extension method of [12], and IBFHE was converted into MIBFHE using the reconstructed extended ciphertext method and the masking scheme. Organization. The second chapter introduces some notation we need to use throughout the paper, and reviews important definitions, including the trapdoor generation algorithm and LWE hardness problem. The third chapter firstly constructs an efficient IBE scheme, and proves the correctness and security of the IBE scheme. The parameter setting of the scheme and the parameter comparison of other schemes are introduced.