Investigate "Evaluating Larger Lookup Tables using CKKS"

Evaluating Larger Lookup Tables using CKKS
_Jules Dumezy, Andreea Alexandru, Yuriy Polyakov, Pierre-Emmanuel Clet, Olive Chakraborty, and Aymen Boudguiga_
[https://eprint.iacr.org/2025/1301.pdf](https://eprint.iacr.org/2025/1301.pdf)

> 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).

Improved functional bootstrapping using only CKKS for larger integers with an [experimental implementation](https://github.com/jdumezy/sec-ckks/).