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 -bit Boolean function, we reduce evaluation time by a factor of at the expense of an additional memory of "only" as a trade-off: The total asymptotic memory is also , which is the same as that of prior works. Our empirical results demonstrate that a speedup in runtime is obtained with a 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 and , respectively, for 8-bit Boolean functions. The core idea is to decompose the function 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
Published elsewhere. WAHC 2024 – 12th Workshop on Encrypted Computing & Applied Homomorphic Cryptography
DOI
10.1145/3689945.3694801
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-09-09: last of 3 revisions
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},
      doi = {10.1145/3689945.3694801},
      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.