Time-Memory Trade-off Algorithms for Homomorphically Evaluating Look-up Table in TFHE
Shintaro Narisada, Hiroki Okada, Kazuhide Fukushima, Takashi Nishide · 2023
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 × speedup in runtime is obtained with a 3.8 × 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 × 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.