International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: FINAL: Faster FHE instantiated with NTRU and LWE

Charlotte Bonte , Intel Corporation, Emerging Security Lab
Ilia Iliashenko , CipherMode Labs & imec-COSIC, KU Leuven
Jeongeun Park , imec-COSIC, KU Leuven
Hilder Vitor Lima Pereira , imec-COSIC, KU Leuven
Nigel Smart , imec-COSIC, KU Leuven, Zama
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: 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.
Video from ASIACRYPT 2022
  title={FINAL: Faster FHE instantiated with NTRU and LWE},
  author={Charlotte Bonte and Ilia Iliashenko and Jeongeun Park and Hilder Vitor Lima Pereira and Nigel Smart},