Paper 2023/645
Fast and Accurate: Efficient Full-Domain Functional Bootstrap and Digit Decomposition for Homomorphic Computation
, Tsinghua UniversityAbstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A major revision of an IACR publication in TCHES 2024
- DOI
- 10.46586/tches.v2024.i1.592-616
- Keywords
- Homomorphic EncryptionTFHEFHEWFunctional BootstrapFDFBHomomorphic Decomposition
- Contact author(s)
- anyuwang @ tsinghua edu cn
- History
- 2024-02-27: revised
- 2023-05-07: received
- See all versions
- Short URL
- https://ia.cr/2023/645
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/645,
author = {Shihe Ma and Tairong Huang and Anyu Wang and Qixian Zhou and Xiaoyun Wang},
title = {Fast and Accurate: Efficient Full-Domain Functional Bootstrap and Digit Decomposition for Homomorphic Computation},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/645},
year = {2023},
doi = {10.46586/tches.v2024.i1.592-616},
url = {https://eprint.iacr.org/2023/645}
}
