International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Faster Bootstrapping via Modulus Raising and Composite NTT

Authors:
Zhihao Li , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Ying Liu , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Xianhui Lu , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Ruida Wang , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Benqiang Wei , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Chunling Chen , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Kunpeng Wang , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
Download:
DOI: 10.46586/tches.v2024.i1.563-591
URL: https://tches.iacr.org/index.php/TCHES/article/view/11262
Search ePrint
Search Google
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 results of the single bootstrapping process indicate that the proposed approach achieves speedups of up to 1.7 x, and reduces the size of the blind rotation key by 50% under specific parameters. Finally, we instantiate two ciphertexts in the packing procedure, and the experimental results show that our technique is around 1.5 x faster than the two bootstrapping processes under the 127-bit security level.
BibTeX
@article{tches-2023-33678,
  title={Faster Bootstrapping via Modulus Raising and Composite NTT},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={024 No. 1},
  pages={563-591},
  url={https://tches.iacr.org/index.php/TCHES/article/view/11262},
  doi={10.46586/tches.v2024.i1.563-591},
  author={Zhihao Li and Ying Liu and Xianhui Lu and Ruida Wang and Benqiang Wei and Chunling Chen and Kunpeng Wang},
  year=2023
}