Faster Bootstrapping via Modulus Raising and Composite NTT

Abstract: FHEW-like schemes utilize exact gadget decomposition to reduce error growth and ensure that the bootstrapping incurs only polynomial error growth. However, the exact gadget decomposition method requires higher computation complexity and larger memory storage. In this paper, we improve the efficiency of the FHEWlike schemes by utilizing the composite NTT that performs the Number Theoretic Transform (NTT) with a composite modulus. Specifically, based on the composite NTT, we integrate modulus raising and gadget decomposition in the external product, which reduces the number of NTTs required in the blind rotation from 2(dg + 1)n to 2(⌈dg⌉/2 + 1)n. Furthermore, we develop a modulus packing technique that uses the Chinese Remainder Theorem (CRT) and composite NTT to bootstrap multiple LWE ciphertexts through one blind rotation process. We implement the bootstrapping algorithms and evaluate the performance on various benchmark computations using both binary and ternary secret keys. Our r.... https://tches.iacr.org/index.php/TCHES/article/view/11262

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch

References and Relationships

• Bibliographic citation: Faster Bootstrapping via Modulus Raising and Composite NTT ; volume:2024 ; number:1 ; year:2023 ; IACR transactions on cryptographic hardware and embedded systems ; 2024, Heft 1 (2023)

Contributors, Places and Time

• Creator: Li, Zhihao ; Liu, Ying ; Lu, Xianhui ; Wang, Ruida ; Wei, Benqiang ; Chen, Chunling ; Wang, Kunpeng

Further information

• DOI: 10.46586/tches.v2024.i1.563-591
• URN: urn:nbn:de:101:1-2023120617543992270236
• Rights: Open Access; Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 15.08.2025, 7:23 AM CEST