Welcome to the resource topic for 2024/1114
Title:
Time-Memory Trade-off Algorithms for Homomorphically Evaluating Look-up Table in TFHE
Authors: Shintaro Narisada, Hiroki Okada, Kazuhide Fukushima, Takashi Nishide
Abstract:We propose time-memory trade-off algorithms for evaluating look-up table (LUT) in both the leveled homomorphic encryption (LHE) and fully homomorphic encryption (FHE) modes in TFHE. For an arbitrary n-bit Boolean function, we reduce evaluation time by a factor of O(n) at the expense of an additional memory of “only” O(2^n) as a trade-off: The total asymptotic memory is also O(2^n), which is the same as that of prior works. Our empirical results demonstrate that a 7.8 \times speedup in runtime is obtained with a 3.8 \times increase in memory usage for 16-bit Boolean functions in the LHE mode. Additionally, in the FHE mode, we achieve reductions in both runtime and memory usage by factors of 17.9 \times and 2.5 \times , respectively, for 8-bit Boolean functions. The core idea is to decompose the function f into sufficiently small subfunctions and leverage the precomputed results for these subfunctions, thereby achieving significant performance improvements at the cost of additional memory.
ePrint: https://eprint.iacr.org/2024/1114
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 .