Paper 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.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- Fully Homomorphic EncryptionBootstrappingLatticesLWENTRU
- Contact author(s)
-
hilder vitor @ gmail com
Charlotte Bonte @ esat kuleuven be
ilia @ esat kuleuven be
Jeongeun Park @ esat kuleuven be
nigel smart @ kuleuven be - History
- 2022-09-08: last of 3 revisions
- 2022-01-20: received
- See all versions
- Short URL
- https://ia.cr/2022/074
- License
-
CC BY