Paper 2025/1301
Evaluating Larger Lookup Tables using CKKS
, Université Paris-Saclay, CEA-List, Duality Technologies, Duality Technologies, Université Paris-Saclay, CEA-List, Université Paris-Saclay, CEA-List, Université Paris-Saclay, CEA-ListAbstract
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
- A minor revision of an IACR publication in TCHES 2026
- Keywords
- FHEFunctional BootstrappingProgrammable BootstrappingLookup TableCKKS
- Contact author(s)
-
jules dumezy @ cea fr
aalexandru @ dualitytech com
ypolyakov @ dualitytech com
pierre-emmanuel clet @ cea fr
olive chakraborty @ cea fr
aymen boudguiga @ cea fr - History
- 2025-10-24: last of 2 revisions
- 2025-07-16: received
- See all versions
- Short URL
- https://ia.cr/2025/1301
- License
-
CC BY
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}
}
