CryptoDB
Faster NTRU-based Bootstrapping in less than 4 ms
NOTE: imports for ToSC and TCHES are no longer functioning.
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Bootstrapping is a critical technique in constructing fully homomorphic encryption (FHE), which serves to refresh the noise in FHE ciphertexts, enabling an arbitrary number of homomorphic operations. Among published results, the TFHE-rs library [Zam22] offers the fastest bootstrapping implementation on CPU platforms by taking advantage of AVX-512 instructions.In this paper, we improve the efficiency of the bootstrapping algorithm based on the NTRU problem. First, we introduce the approximate gadget decomposition method tailored for NTRU ciphertext, reducing the number of NTT operations required for external products. Second, by integrating the approximate decomposition and key unrolling techniques, we improve the performance of CMux-based blind rotation. Third, for the automorphism-based blind rotation method, we present a hybrid window size technique that reduces the number of automorphisms by 34% compared to recent work [XZD+23](in Crypto23).Subsequently, we implement the proposed bootstrapping algorithm on the CPU platform with AVX instructions. Experimental results demonstrate that our method only takes 3.8ms, which achieves a 1.8× speedup compared to the TFHE-rs library. Finally, we propose an efficient FPGA accelerator based on the CMux method, which not only achieves the best performance but also exhibits high throughput advantages. Our accelerator can improve performance by 2x compared to state-of-the-art FPGA implementations (e.g., FPT). |
BibTeX
@article{tches-2024-34447,
title={Faster NTRU-based Bootstrapping in less than 4 ms},
journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
publisher={Ruhr-Universität Bochum},
volume={2024},
pages={418-451},
url={https://tches.iacr.org/index.php/TCHES/article/view/11683},
doi={10.46586/tches.v2024.i3.418-451},
author={Zhihao Li and Xianhui Lu and Zhiwei Wang and Ruida Wang and Ying Liu and Yinhang Zheng and Lutan Zhao and Kunpeng Wang and Rui Hou},
year=2024
}