An Effective NTRU-Based Fully Homomorphic Encryption Scheme

Fully homomorphic encryption (FHE) supports arbitrary computations on ciphertexts without decryption to protect users’ privacy. However, currently, there are still some shortcomings in research studies on FHE. For example, the NTRU-based FHE scheme constructed using the approximate eigenvector method requires complex matrix multiplications, and the power-of-two cyclotomic ring cannot prevent subfield attacks. To address these problems, this paper proposed a NTRU-based FHE scheme constructed based on the power-of-prime cyclotomic ring and made the following improvements: (1) the power-of-prime cyclotomic ring is immune to subfield attacks; (2) complex matrix multiplications are replaced with matrix-vector multiplications to modify the ciphertext forms and decryption structures, so as to gain advantages in storage, transportation, and computations; (3) the single instruction multiple data (SIMD) technology is introduced, and homomorphic operations are executed through the Chinese remainder theorem, further improving the scheme computation and storage efficiency. The ciphertext of the scheme is in a form of a vector, and no key exchange is required for homomorphic operations. In addition, this scheme can eliminate the decisional small polynomial ratio (DSPR) assumption under certain conditions and only relies on the ring learning with errors (RLWE) assumption. The standard security model can prove that this scheme is secure against chosen-plaintext (IND-CPA) attacks. Compared with similar schemes, the proposed scheme improves the efficiency at least by a factor of l φ x / d +   1 and quadratically decreases the noise growth rate.