Skip to content

General Functional Bootstrapping using CKKS

Authors: A. Alexandru; A. Kim; Y. Polyakov
Year: 2025
Venue: CRYPTO 2025

type: scheme collection: catalogue, schemes, sok-references status: auto

Links: ePrint 2024/1623

Visual lesson: CKKS functional bootstrapping · Scheme table row: CKKS functional bootstrapping

Summary

Auto-extracted summary (unreviewed)

The paper proposes and implements general functional bootstrapping on top of CKKS-style bootstrapping, so that an arbitrary lookup table can be evaluated for thousands of encrypted numbers at once instead of one at a time as in DM (FHEW) and CGGI (TFHE). A toolkit based on trigonometric Hermite interpolation gives FHE-friendly expressions for arbitrary functions with control over noise reduction, and is extended to amortized multi-precision evaluation of floor and sign functions, digit decomposition and S-boxes. For 8-bit LUT evaluation the method reaches 0.72 ms amortized time, about three orders of magnitude faster than DM/CGGI functional bootstrapping and 6.8x faster than BFV-based amortized functional bootstrapping.

Abstract

The Ducas–Micciancio (DM) and Chilotti–Gama–Georgieva– Izabachène (CGGI) cryptosystems provide a general privacy-preserving computation capability. These fully homomorphic encryption (FHE) cryptosystems can evaluate an arbitrary function expressed as a general lookup table (LUT) via the method of functional bootstrapping. The main limitation of DM/CGGI functional bootstrapping is its efficiency because this procedure has to bootstrap every encrypted number separately. A different bootstrapping approach, based on the Cheon–Kim–Kim–Song (CKKS) FHE scheme, can achieve much smaller amortized time due to its ability to bootstrap many thousands of numbers at once. However, CKKS does not currently provide a functional bootstrapping capability that can evaluate a general LUT. An open research question is whether such capability can be efficiently constructed. We give a positive answer to this question by proposing and implementing a general functional bootstrapping method based on CKKS-style bootstrapping. We devise a theoretical toolkit for evaluating an arbitrary function using the theory of trigonometric Hermite interpolations, which provides control over noise reduction during functional bootstrapping. Our experimental results for 8-bit LUT evaluation show that the proposed method achieves the amortized time of 0.72 milliseconds, which is three orders of magnitude faster than the DM/CGGI approach and 6.8x faster than (a more restrictive) amortized functional bootstrapping method based on the Brakerski/Fan- Vercauteren (BFV) FHE scheme. ⋆Distribution Statement "A" (Approved for Public Release, Distribution Unlimited). This work is supported in part by DARPA through HR0011-21-9-0003. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. Table of Contents
Source: pdf

Extracted details

Field Value Source Confidence
contribution general functional bootstrapping (arbitrary LUT evaluation) based on CKKS bootstrapping llm 0.80
contribution trigonometric Hermite interpolation toolkit for arbitrary function evaluation with noise control llm 0.80
contribution amortized multi-precision evaluation of floor and sign functions llm 0.80
contribution homomorphic digit decomposition and S-box noise analysis llm 0.80
contribution implementation and comparison with DM/CGGI and BFV-based functional bootstrapping llm 0.80
schemes CKKS llm 0.80
schemes LWE llm 0.80
schemes FHEW llm 0.80
schemes TFHE llm 0.80
schemes BFV llm 0.80
tasks arbitrary lookup-table evaluation llm 0.80
tasks multi-precision sign and floor evaluation llm 0.80
tasks S-box evaluation llm 0.80
interaction non-interactive FHE llm 0.80
llm relevance low llm 0.80
key result amortized time per 8-bit LUT evaluation: 0.72 ms (CKKS-based functional bootstrapping) llm 0.80
key result speed-up vs DM/CGGI functional bootstrapping: about 1000x (three orders of magnitude) (8-bit LUT, amortized) llm 0.80
key result speed-up vs BFV-based amortized functional bootstrapping: 6.8x (8-bit LUT, amortized) llm 0.80

Scheme card: CKKS functional bootstrapping

Group 1. CKKS and its variants
Kind Variant
Hardness assumption RLWE
Plaintext type Lookup tables on small integers
SIMD packing Yes
Bootstrapping Yes, evaluates a LUT while refreshing
Post-quantum Yes
Status Active SOTA
Fit for LLM inference TFHE-like LUTs at CKKS throughput. The SoK names it a robustness direction for piecewise non-linearities.
Follow-ups Fourier-extension FBS (2026/367); SWIFT shallow FBS (2026/1163); low-rank FBS (2026/1264).
Libraries OpenFHE
Follow-up papers in the archive High-Precision Functional Bootstrapping for CKKS from Fourier Extension
SWIFT: Shallow and SIMD-Aware CKKS Functional Bootstrapping for Low-Latency
The Power of Low Rank: Fast CKKS Functional Bootstrapping for High-Precision Lookup Tables

System card: General functional bootstrapping in CKKS

Group 2. CKKS core and variants
Family CKKS functional bootstrapping
Arithmetic Lookup tables on small integers
Interaction Non-interactive
Model scale -
Status Active SOTA
Relation to the SoK Evaluates LUTs during CKKS bootstrapping, like TFHE PBS.
Note The SoK lists it as a robustness direction for piecewise non-linear approximation in LLMs.
Code https://github.com/openfheorg/openfhe-development
Systems page General functional bootstrapping in CKKS

SoK reference [67]

A. Alexandru, A. Kim, and Y. Polyakov, “General functional bootstrapping using ckks,” in Advances in Cryptology – CRYPTO 2025, Y. Tauman Kalai and S. F. Kamara, Eds. Cham: Springer Nature Switzerland, 2025, pp. 304–337.

Listed on the reference page of the site.

Keyword mentions

Counts of vocabulary terms in the full text (first page of occurrence in brackets).

  • scheme: CKKS 140 [p.1], TFHE 61 [p.1], BFV 42 [p.1], BGV 11 [p.4], Leveled / somewhat HE 6 [p.4], FHEW 4 [p.4], RSA 3 [p.34], Hybrid HE / transciphering 2 [p.23], Scheme switching 2 [p.5]
  • library: OpenFHE 7 [p.6], TFHE-rs 7 [p.36], Microsoft SEAL 1 [p.40], Concrete (Zama) 1 [p.11], Zama 1 [p.36]
  • hardware: AVX-512 2 [p.38], AMD EPYC 1 [p.38], GPU 1 [p.41]
  • technique: Bootstrapping 226 [p.1], Lookup table 136 [p.1], Functional bootstrapping 92 [p.1], RNS 24 [p.2], Key switching 11 [p.30], Rescaling 11 [p.24], Paterson-Stockmeyer 8 [p.8], Programmable bootstrapping 7 [p.5], Modulus switching 6 [p.2], Chebyshev 5 [p.8], SIMD packing 5 [p.5], Polynomial approximation 3 [p.5], Taylor expansion 3 [p.15], NTT 2 [p.44]
  • assumption: RLWE 42 [p.7], LWE 38 [p.2], Lattice-based 4 [p.4], IND-CPA-D 2 [p.8]
  • task: Language modeling / generation 9 [p.8]
  • topic: Homomorphic encryption 44 [p.1], Benchmark 9 [p.38], Open source 3 [p.11]

Files

Path (under papers/) Collection Pages Size SHA-256 Note
references/catalogue/2-031_general-functional-bootstrapping-using-ckks.pdf catalogue 52 941.8 KB 72f3ce0a332d
references/schemes/s13-0_general-functional-bootstrapping-using-ckks.pdf schemes 52 941.8 KB 72f3ce0a332d byte-identical to references/catalogue/2-031_general-functional-bootstrapping-using-ckks.pdf
references/sok-references/067_general-functional-bootstrapping-using-ckks.pdf sok-references 52 941.8 KB 72f3ce0a332d byte-identical to references/catalogue/2-031_general-functional-bootstrapping-using-ckks.pdf

Database key: general-functional-bootstrapping-using-ckks · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set general-functional-bootstrapping-using-ckks COLUMN VALUE