Paper 2024/1114

Time-Memory Trade-off Algorithms for Homomorphically Evaluating Look-up Table in TFHE

Shintaro Narisada, KDDI Research (Japan)
Hiroki Okada, KDDI Research (Japan), University of Tokyo
Kazuhide Fukushima, KDDI Research (Japan)
Takashi Nishide, University of Tsukuba
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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
FHECMux TreeSpace–Time Trade-Off
Contact author(s)
sh-narisada @ kddi com
ir-okada @ kddi com
ka-fukushima @ kddi com
nishide @ risk tsukuba ac jp
History
2024-07-10: approved
2024-07-09: received
See all versions
Short URL
https://ia.cr/2024/1114
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1114,
      author = {Shintaro Narisada and Hiroki Okada and Kazuhide Fukushima and Takashi Nishide},
      title = {Time-Memory Trade-off Algorithms for Homomorphically Evaluating Look-up Table in {TFHE}},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1114},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/1114}},
      url = {https://eprint.iacr.org/2024/1114}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.