Evaluating Larger Lookup Tables using CKKS

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

On the blog

• Discrete CKKS Functional Bootstrapping October 8, 2025 · Introduction to CKKS functional bootstrapping for evaluating (large) LUTs.

Talks

• CHES'26 · Oct 2026 · Royal Seginus, Antalya, Türkiye Slides
• PEPR Secure Compute · Jun 2026 · ENS Ulm, Paris, France
• FHE.org Meetup · Mar 2026 SlidesVideo
• FHE.org'26 · Mar 2026 · Taipei Marriott Hotel, Taipei, Taiwan Poster

@article{Dumezy_Alexandru_Polyakov_Clet_Chakraborty_Boudguiga_2026,
	title        = {Evaluating Larger Lookup Tables using CKKS},
	author       = {Dumezy, Jules and Alexandru, Andreea and Polyakov, Yuriy and Clet, Pierre-Emmanuel and Chakraborty, Olive and Boudguiga, Aymen},
	year         = 2026,
	month        = {Jan.},
	journal      = {IACR Transactions on Cryptographic Hardware and Embedded Systems},
	volume       = 2026,
	number       = 1,
	pages        = {559–591},
	doi          = {10.46586/tches.v2026.i1.559-591},
	url          = {https://tches.iacr.org/index.php/TCHES/article/view/12693},
}