Paper 2024/1898
NTRU-based Bootstrapping for MK-FHEs without using Overstretched Parameters
Binwu Xiang, Institute of Information Engineering, CAS
Jiang Zhang, State Key Laboratory of Cryptology
Kaixing Wang, State Key Laboratory of Cryptology
Yi Deng, Institute of Information Engineering, CAS
Dengguo Feng, State Key Laboratory of Cryptology
Abstract
Recent attacks on NTRU lattices given by Ducas and van Woerden (ASIACRYPT 2021) showed that for moduli larger than the so-called fatigue point , the security of NTRU is noticeably less than that of (ring)-LWE. Unlike
NTRU-based PKE with typically lying in the secure regime of NTRU lattices (i.e., ), the security of existing NTRU-based multi-key FHEs (MK-FHEs) requiring for keys could be significantly affected by those attacks.
In this paper, we first propose a (matrix) NTRU-based MK-FHE
for super-constant number of keys without using overstretched NTRU parameters. Our scheme is essentially a combination of two components following the two-layer framework of TFHE/FHEW:
- a simple first-layer matrix NTRU-based encryption that naturally supports multi-key NAND operations
with moduli only linear in the number of keys;
-and a crucial second-layer NTRU-based encryption that supports an efficient hybrid product between a single-key ciphertext and a multi-key ciphertext for gate bootstrapping.
Then, by replacing the first-layer with a more efficient LWE-based multi-key encryption, we obtain an improved MK-FHE scheme with better performance. We also employ a light key-switching technique to reduce the key-switching key size from the previous bits to bits.
A proof-of-concept implementation shows that our two MK-FHE schemes outperform the state-of-the-art TFHE-like MK-FHE schemes in both computation efficiency and bootstrapping key size. Concretely, for at the same 100-bit security level, our improved MK-FHE scheme can bootstrap a ciphertext in {0.54s} on a laptop and only has a bootstrapping key of size {13.89}MB,which are respectively 2.2 times faster and 7.4 times smaller than the MK-FHE scheme (which relies on a second-layer encryption from the ring-LWE assumption) due to Chen, Chillotti and Song (ASIACRYPT 2019).
Note: full version