The previous NTRU-type multi-key fully homomorphic encryption (MKFHE) schemes were constructed over power-of-2 cyclotomic polynomial rings. And the complicated key-switching operations were used in the schemes to complete the fully homomorphic computation. So, they were suffered from the subfield attacks and had low evaluating efficiency. To this end, an NTRU-type MKFHE scheme with better security and higher efficiency was proposed. Firstly, the prime cyclotomic polynomial ring was applied to the previous NTRU-type MKFHE schemes. And an NTRU-type MKFHE basic scheme model (denote B-MKFHE in this paper) over prime cyclotomic polynomial ring was given, which could resist more subfield attacks. Secondly, based on the B-MKFHE model, the NTRU-type multi-key homomorphic evaluating structure was optimized by extending the dimension of ciphertext polynomial, thus the complicated and time-consuming key-switching operations were eliminated when running the homomorphic operations. Finally, combined the improved multi-key homomorphic evaluating structure with modulus-switching technology, a leveled NTRU-type MKFHE scheme (denote M-MKFHE in this paper) without key-switching operations was constructed. Compared with the previous schemes, the security of the proposed scheme was improved because of the based prime cyclotomic polynomial ring. As the memory (bit-size) and evaluating costs were reduced, the evaluating efficiency was improved. Meanwhile, the error magnitude was decreased in the homomorphic evaluating process, so the scheme supported deeper homomorphic evaluations.
