Welcome to the resource topic for 2023/645
Title:
Fast and Accurate: Efficient Full-Domain Functional Bootstrap and Digit Decomposition for Homomorphic Computation
Authors: Shihe Ma, Tairong Huang, Anyu Wang, Xiaoyun Wang
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\%.
Furthermore, our FDFB algorithms introduce an error that can be as small as 1/15 of that introduced by previous algorithms when evaluating continuous functions.
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.
ePrint: https://eprint.iacr.org/2023/645
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .