Improved Bootstrapping for Approximate Homomorphic Encryption¶
Authors: Hao Chen; Ilaria Chillotti; Yongsoo Song
Year: 2019
Venue: EUROCRYPT 2019
type: technique collection: catalogue status: auto
Links: DOI · ePrint 2018/1043 · Semantic Scholar
Summary¶
Auto-extracted summary (unreviewed)
The paper speeds up CKKS bootstrapping by two orders of magnitude in amortized time per slot (from about 1 s to about 0.01 s) relative to the Cheon et al. Eurocrypt'18 procedure. It introduces a level-collapsing technique for the DFT-like linear transforms (CoeffToSlot/SlotToCoeff), replaces the Taylor approximation of the sine function with a more accurate Chebyshev interpolant, and designs a modified Paterson-Stockmeyer algorithm for evaluating Chebyshev polynomials on ciphertexts. On the HEAAN library, single-threaded on a laptop, the utility metric (levels x slots / second) improves about 50x (2.94 to 150) at about 20-bit precision.
Abstract¶
Since Cheon et al. introduced a homomorphic encryption scheme for approximate arithmetic (Asiacrypt ’17), it has been recognized as suitable for important real-life usecases of homomorphic encryption, including training of machine learning models over encrypted data. A follow up work by Cheon et al. (Eurocrypt ’18) described an approximate bootstrapping procedure for the scheme. In this work, we improve upon the previous bootstrapping result. We improve the amortized bootstrapping time per plaintext slot by two orders of magnitude, from ∼1 second to ∼0.01 second. To achieve this result, we adopt a smart level-collapsing technique for evaluating DFT-like linear transforms on a ciphertext. Also, we replace the Taylor approximation of the sine function with a more accurate and numerically stable Chebyshev approximation, and design a modified version of the Paterson-Stockmeyer algorithm for fast evaluation of Chebyshev polynomials over encrypted data.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | level-collapsing technique for evaluating DFT-like linear transforms on ciphertexts | llm | 0.90 |
| contribution | Chebyshev approximation of the sine function for homomorphic modular reduction | llm | 0.90 |
| contribution | modified Paterson-Stockmeyer algorithm for fast evaluation of Chebyshev polynomials under encryption | llm | 0.90 |
| contribution | two orders of magnitude improvement in amortized CKKS bootstrapping time | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| libraries | HEAAN | llm | 0.90 |
| tasks | CKKS bootstrapping | llm | 0.90 |
| hardware | Intel Core i7 2.8 GHz laptop CPU, 16 GB RAM, single thread | llm | 0.90 |
| security level | same as Cheon et al. Eurocrypt'18 parameter sets (log N, log Q unchanged; not quantified in excerpt) | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/snucrypto/HEAAN/releases/tag/2.1 (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/kimandrik/HEAANBOOT.14 (URL found in the full text) | regex | 0.50 |
| limitations | implemented on the original (non-RNS) HEAAN; porting to the RNS variant, reported up to 10x faster, is left as future work | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | amortized bootstrapping time per slot: ~0.01 s (from ~1 s) (Set-IV, log N=16, 2^14 slots, 18.63-bit precision, 158.32 s total) | llm | 0.90 |
| key result | bootstrapping utility (levels x slots / second): 150 vs 2.94 (~50x) (~20-bit precision, vs Cheon et al. Eurocrypt'18) | llm | 0.90 |
| key result | total bootstrapping time: 167.87 s, 0.04 s amortized, 20.86-bit precision (Set-IV, 2^12 slots, 6 levels remaining after bootstrapping)* | llm | 0.90 |
| key result | total bootstrapping time: 38.33 s, 0.04 s amortized (Set-I, log N=15, 2^10 slots, 6.92-bit precision)* | llm | 0.90 |
System card: Improved CKKS bootstrapping (Chen-Chillotti-Song)¶
| Group | 3. CKKS bootstrapping and operation advances |
| Family | CKKS bootstrapping |
| Arithmetic | - |
| Interaction | - |
| Model scale | - |
| Status | Foundational |
| Relation to the SoK | Faster linear transforms and modular reduction. |
| Note | Basis of Microsoft SEAL-era bootstrapping implementations. |
| Systems page | Improved CKKS bootstrapping (Chen-Chillotti-Song) |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 27 [p.2], Leveled / somewhat HE 4 [p.2], BFV 2 [p.4], BGV 2 [p.4]
- library: HElib 2 [p.21]
- model: Logistic regression 6 [p.2]
- technique: Bootstrapping 48 [p.1], Chebyshev 42 [p.1], Rotations 10 [p.6], Paterson-Stockmeyer 8 [p.1], Rescaling 4 [p.6], Minimax approximation 4 [p.12], RNS 3 [p.18], Taylor expansion 2 [p.1], SIMD packing 2 [p.9]
- assumption: LWE 2 [p.19]
- task: Language modeling / generation 6 [p.3]
- topic: Homomorphic encryption 28 [p.1], Open source 2 [p.19]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/3-034_improved-bootstrapping-for-approximate-homomorphic-encryptio.pdf |
catalogue | 21 | 400.3 KB | ac61f01b3571 |
Database key: improved-bootstrapping-for-approximate-homomorphic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set improved-bootstrapping-for-approximate-homomorphic-encryption COLUMN VALUE