Paper 2024/1105

A New CRT-based Fully Homomorphic Encryption

Anil Kumar Pradhan, Vaultree Ltd.

We have proposed a novel FHE scheme that uniquely encodes the plaintext with noise in a way that prevents the increasing noise from overflowing and corrupting the plaintext. This allows users to perform computations on encrypted data smoothly. The scheme is constructed using the Chinese Remainder Theorem (CRT), supporting a predefined number of modular operations on encrypted plaintext without the need for bootstrapping. Although FHE recently became popular after Gentry's work and various developments have occurred in the last decade, the idea of "Fully Homomorphic Encryption (FHE)" scheme was first introduced in the 1970s by Rivest. The Chinese Remainder Theorem is one of the most suitable tools for developing a FHE Scheme because it forms a ring homomorphism \( Z_{p_1} \times Z_{p_2} \times \ldots \times Z_{p_k} \cong Z_{p_1 p_2 \ldots p_k} \). Various attempts have been made to develop a FHE using CRT, but most of them were unsuccessful, mainly due to the chosen plaintext attack (CPA). The proposed scheme overcomes the chosen plaintext attack. The scheme also adds random errors to the message during encryption. However, these errors are added in such a way that, when homomorphic operations are performed over encrypted data, the increasing values of errors never overwrite the values of the messages, as happens in LWE-based homomorphic schemes. Therefore, one can perform a predefined number of homomorphic operations (both addition and multiplication) without worrying about the increasing values of errors.

Available format(s)
Cryptographic protocols
Publication info
Fully Homomorphic Encryption (FHE)Chinese Reminder TheoremChosen Plaintext Attack
Contact author(s)
research @ vaultree com
2024-07-08: approved
2024-07-07: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Anil Kumar Pradhan},
      title = {A New {CRT}-based Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1105},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.