International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Fast and Accurate: Efficient Full-Domain Functional Bootstrap and Digit Decomposition for Homomorphic Computation

Authors:
Shihe Ma , Institute for Network Sciences and Cyberspace, Tsinghua University, Beijing, China
Tairong Huang , Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China
Anyu Wang , Institute for Advanced Study, BNRist, Tsinghua University, Beijing, China; Zhongguancun Laboratory, Beijing, China; National Financial Cryptography Research Center, Beijing, China
Qixian Zhou , Ant Group
Xiaoyun Wang
Download:
DOI: 10.46586/tches.v2024.i1.592-616
URL: https://tches.iacr.org/index.php/TCHES/article/view/11263
Search ePrint
Search Google
Abstract: The functional bootstrap in FHEW/TFHE allows for fast table lookups on ciphertexts and is a powerful tool for privacy-preserving computations. However, the functional bootstrap suffers from two limitations: the negacyclic constraint of the lookup table (LUT) and the limited ability to evaluate large-precision LUTs. To overcome the first limitation, several full-domain functional bootstraps (FDFB) have been developed, enabling the evaluation of arbitrary LUTs. Meanwhile, algorithms based on homomorphic digit decomposition have been proposed to address the second limitation. Although these algorithms provide effective solutions, they are yet to be optimized. This paper presents four new FDFB algorithms and two new homomorphic decomposition algorithms that improve the state-of-the-art. Our FDFB algorithms reduce the output noise, thus allowing for more efficient and compact parameter selection. Across all parameter settings, our algorithms reduce the runtime by up to 39.2%. Our homomorphic decomposition algorithms also run at 2.0x and 1.5x the speed of prior algorithms. We have implemented and benchmarked all previous FDFB and homomorphic decomposition algorithms and our methods in OpenFHE.
BibTeX
@article{tches-2023-33679,
  title={Fast and Accurate: Efficient Full-Domain Functional Bootstrap and Digit Decomposition for Homomorphic Computation},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={024 No. 1},
  pages={592-616},
  url={https://tches.iacr.org/index.php/TCHES/article/view/11263},
  doi={10.46586/tches.v2024.i1.592-616},
  author={Shihe Ma and Tairong Huang and Anyu Wang and Qixian Zhou and Xiaoyun Wang},
  year=2023
}