Welcome to the resource topic for 2024/1898
Title:
NTRU-based Bootstrapping for MK-FHEs without using Overstretched Parameters
Authors: Binwu Xiang, Jiang Zhang, Kaixing Wang, Yi Deng, Dengguo Feng
Abstract:Recent attacks on NTRU lattices given by Ducas and van Woerden (ASIACRYPT 2021) showed that for moduli q larger than the so-called fatigue point n^{2.484+o(1)}, the security of NTRU is noticeably less than that of (ring)-LWE. Unlike
NTRU-based PKE with q typically lying in the secure regime of NTRU lattices (i.e., q<n^{2.484+o(1)}), the security of existing NTRU-based multi-key FHEs (MK-FHEs) requiring q=O(n^k) for k keys could be significantly affected by those attacks.
In this paper, we first propose a (matrix) NTRU-based MK-FHE
for super-constant number k 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 q=O(k\cdot n^{1.5}) only linear in the number k 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 O(n^2) bits to O(n) 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 k=8 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).
ePrint: https://eprint.iacr.org/2024/1898
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .