Evaluating Larger Lookup Tables using CKKS

Jules Dumezy; Andreea Alexandru; Yuriy Polyakov; Pierre-Emmanuel Clet; Olive Chakraborty; Aymen Boudguiga

Paper 2025/1301 Original: eprint.iacr.org/2025/1301 ↗

Evaluating Larger Lookup Tables using CKKS

Jules Dumezy

Andreea Alexandru

Yuriy Polyakov

Pierre-Emmanuel Clet

Olive Chakraborty

Aymen Boudguiga

Abstract

The Cheon-Kim-Kim-Song (CKKS) scheme is a fully homomorphic encryption scheme that traditionally supports only the evaluation of smooth functions. Recent works have enabled the evaluation of arbitrary (discontinuous) integer functions represented as lookup tables (LUT) on small inputs using the method of functional bootstrapping (FBT). Although well-suited for small integers (up to around 10 bits), the efficiency of FBT quickly declines for large LUTs, and a considerable increase in both runtime and memory requirements is observed. Building on CKKS functional bootstrapping, we propose in this paper two functional bootstrapping algorithms, specifically designed to target larger LUTs (up to 20 bits). For a 16-bit LUT, our implementation in OpenFHE achieves a speed-up of 47.5 in amortized time and 95.1 in latency for single-threaded execution, compared to the state-of-the-art CKKS-based functional bootstrapping method of Alexandru et al. (CRYPTO'25).

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
History: 2025-10-24: last updated; 2025-07-16: published
Short URL: https://ia.cr/2025/1301
License: https://creativecommons.org/licenses/by/4.0/

BibTeX

@misc{cryptoeprint:2025/1301,
      author = {Jules Dumezy and Andreea Alexandru and Yuriy Polyakov and Pierre-Emmanuel Clet and Olive Chakraborty and Aymen Boudguiga},
      title = {Evaluating Larger Lookup Tables using CKKS},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1301},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1301}
}