Paper 2022/074
FINAL: Faster FHE instantiated with NTRU and LWE
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)
-
PDF
- Category
- Foundations
- Publication info
- Published by the IACR in ASIACRYPT 2022
- Keywords
- 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 - 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
BibTeX
@misc{cryptoeprint:2022/074,
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},
url = {https://eprint.iacr.org/2022/074}
}