Paper 2022/074

FINAL: Faster FHE instantiated with NTRU and LWE

Charlotte Bonte
Ilia Iliashenko
Jeongeun Park
Hilder V. L. Pereira
Nigel P. Smart

The NTRU problem is a promising candidate to build efficient Fully Homomorphic Encryption (FHE). However, all the existing proposals (e.g. LTV, YASHE) need so-called `overstretched' parameters of NTRU to enable homomorphic operations. It was shown by Albrecht et al. (CRYPTO 2016) that these parameters are vulnerable against subfield lattice attacks. Based on a recent, more detailed analysis of the overstretched NTRU assumption by Ducas and van Woerden (ASIACRYPT 2021), we construct two FHE schemes whose NTRU parameters lie outside the overstretched range. The first scheme is based solely on NTRU and demonstrates competitive performance against the state-of-the-art FHE schemes including TFHE. Our second scheme, which is based on both the NTRU and LWE assumptions, outperforms TFHE with a 28% faster bootstrapping and 45% smaller bootstrapping and key-switching keys.

Available format(s)
Publication info
Published by the IACR in ASIACRYPT 2022
Fully Homomorphic Encryption Bootstrapping Lattices LWE NTRU
Contact author(s)
charlotte bonte @ intel com
ilia @ esat kuleuven be
Jeongeun Park @ esat kuleuven be
HilderVitor LimaPereira @ esat kuleuven be
nigel smart @ kuleuven be
2022-09-08: last of 3 revisions
2022-01-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Charlotte Bonte and Ilia Iliashenko and Jeongeun Park and Hilder V.  L.  Pereira and Nigel P.  Smart},
      title = {{FINAL}: Faster {FHE} instantiated with {NTRU} and {LWE}},
      howpublished = {Cryptology ePrint Archive, Paper 2022/074},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.