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