Cryptology ePrint Archive: Report 2022/074

FINAL: Faster FHE instantiated with NTRU and LWE

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

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.

Category / Keywords: foundations / Fully Homomorphic Encryption, Bootstrapping, Lattices, LWE, NTRU

Date: received 19 Jan 2022, last revised 15 Feb 2022

Contact author: hilder vitor at gmail com, Charlotte Bonte at esat kuleuven be , ilia at esat kuleuven be, Jeongeun Park at esat kuleuven be, nigel smart at kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20220215:095856 (All versions of this report)

Short URL: ia.cr/2022/074