Paper 2022/089

NTRU-$\nu$-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus

Kamil Kluczniak

NTRUEncrypt is one of the first lattice-based encryption schemes. Furthermore, the earliest fully homomorphic encryption (FHE) schemes rely on the NTRU problem. Currently, NTRU is one of the leading candidates in the NIST post-quantum standardization competition. What makes NTRU appealing is the age of the cryptosystem and relatively good performance. Unfortunately, FHE based on NTRU became impractical due to efficient attacks on NTRU instantiations with ``overstretched'' modulus. In particular, currently, NTRU-based FHE schemes to support a reasonable circuit depth require instantiating NTRU with a very large modulus. Breaking the NTRU problem for such large moduli turns out to be easy. Due to these attacks, any serious work on practical NTRU-based FHE essentially stopped. In this paper, we reactivate research on practical FHE that can be based on NTRU. We design an efficient bootstrapping scheme in which the noise growth is small enough to keep the modulus to dimension ratio relatively small, thus avoiding the negative consequences of ``overstretching'' the modulus. Our bootstrapping algorithm is an accumulator-type bootstrapping scheme analogous to AP/FHEW/TFHE. Finally, we show that we can use the bootstrapping procedure to compute any function over $\mathbb{Z}_t$. Consequently, we obtain one of the fastest FHE bootstrapping schemes able to compute any function over elements of a finite field alongside reducing the error.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. ACM CCS 2022
Fully Homomorphic Encryption NTRU FHEW TFHE
Contact author(s)
kamil kluczniak @ cispa de
2022-09-20: revised
2022-01-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kamil Kluczniak},
      title = {NTRU-$\nu$-um: Secure Fully Homomorphic Encryption from NTRU with Small Modulus},
      howpublished = {Cryptology ePrint Archive, Paper 2022/089},
      year = {2022},
      doi = {10.1145/3548606.3560700},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.