Skip to content

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