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]
Related papers¶
- High-Precision Functional Bootstrapping for CKKS from Fourier Extension follow up of this paper — follow-up listed for scheme "CKKS functional bootstrapping"
- SWIFT: Shallow and SIMD-Aware CKKS Functional Bootstrapping for Low-Latency follow up of this paper — follow-up listed for scheme "CKKS functional bootstrapping"
- The Power of Low Rank: Fast CKKS Functional Bootstrapping for High-Precision Lookup Tables follow up of this paper — follow-up listed for scheme "CKKS functional bootstrapping"
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