Bootstrapping for Approximate Homomorphic Encryption¶
Authors: Cheon, Han, Kim, Kim, Song
Year: 2018
Venue: EUROCRYPT 2018
type: technique collection: catalogue status: auto
Links: ePrint 2018/153
Summary¶
Auto-extracted summary (unreviewed)
Extends the leveled approximate-arithmetic scheme HEAAN (CKKS) to a fully homomorphic scheme by introducing the first bootstrapping procedure for it. The modular reduction in the decryption circuit is approximated by a scaled sine function evaluated with one homomorphic multiplication per iteration, so cost grows linearly with the decryption depth; an open-source implementation refreshes a ciphertext with 128 slots at 12-bit precision in 139.8 s (1.1 s per slot amortized).
Abstract¶
This paper extends the leveled homomorphic encryption scheme for an approximate arithmetic of Cheon et al. (ASIACRYPT 2017) to a fully homomorphic encryption, i.e., we propose a new technique to refresh low-level ciphertexts based on Gentry’s bootstrapping procedure. The modular reduction operation is the main bottleneck in the homomorphic evaluation of the decryption circuit. We exploit a scaled sine function as an approximation of the modular reduction operation and present an efficient evaluation strategy. Our method requires only one homomorphic multiplication for each of iterations and so the total computation cost grows linearly with the depth of the decryption circuit. We also show how to recrypt packed ciphertexts on the RLWE construction with an opensource implementation. For example, it takes 139.8 seconds to refresh a ciphertext that encrypts 128 numbers with 12 bits of precision, yielding an amortized rate of 1.1 seconds per slot.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | first bootstrapping procedure for the approximate HE scheme HEAAN/CKKS | llm | 0.90 |
| contribution | scaled sine approximation of modular reduction with efficient double-angle evaluation strategy | llm | 0.90 |
| contribution | O(L) homomorphic multiplications for decryption-circuit depth L | llm | 0.90 |
| contribution | recryption of packed (sparse-slot) RLWE ciphertexts with optimized linear transforms | llm | 0.90 |
| contribution | open-source implementation (HEAANBOOT) | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| libraries | HEAAN | llm | 0.90 |
| tasks | FHE bootstrapping | llm | 0.90 |
| tasks | approximate arithmetic on encrypted data | llm | 0.90 |
| security level | at least 80-bit | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/kimandrik/HEAANBOOT.13 (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/kimandrik/HEAAN (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/kimandrik/HEAANBOOT | llm | 0.90 |
| limitations | the linear transformation is the most time-consuming part; approximate evaluation of it is left as an open problem | llm | 0.90 |
| limitations | precision loss of about one bit per multiplication limits usable depth between bootstraps | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | bootstrapping latency: 139.8 s (ciphertext with 128 slots, 12 bits of precision) | llm | 0.90 |
| key result | amortized bootstrapping time per slot: 1.1 s (128 slots, 12 bits of precision) | llm | 0.90 |
| key result | bootstrapping latency: 26.6 s (single-slot ciphertext, 12 bits of precision) | llm | 0.90 |
System card: First CKKS bootstrapping¶
| Group | 3. CKKS bootstrapping and operation advances |
| Family | CKKS bootstrapping |
| Arithmetic | - |
| Interaction | - |
| Model scale | - |
| Status | Foundational |
| Relation to the SoK | Makes CKKS fully homomorphic. |
| Note | Introduced CoeffToSlot, EvalMod and SlotToCoeff. Every LLM framework relies on its descendants. |
| Systems page | First CKKS bootstrapping |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 32 [p.1], Leveled / somewhat HE 3 [p.1], FHEW 2 [p.4]
- library: HElib 2 [p.21]
- model: Logistic regression 3 [p.4]
- hardware: Intel Xeon 1 [p.17]
- technique: Bootstrapping 59 [p.1], Rotations 19 [p.9], Key switching 14 [p.9], Rescaling 6 [p.2], SIMD packing 4 [p.6], Matrix multiplication 4 [p.11], Taylor expansion 3 [p.3], Paterson-Stockmeyer 2 [p.2]
- assumption: RLWE 11 [p.1], LWE 6 [p.1]
- task: Language modeling / generation 4 [p.6], Medical / healthcare 4 [p.1], Genomics 3 [p.1], Finance 2 [p.20]
- topic: Homomorphic encryption 41 [p.1], Open source 3 [p.3]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/3-033_bootstrapping-for-approximate-homomorphic-encryption.pdf |
catalogue | 21 | 442.1 KB | c916601102b9 |
Database key: bootstrapping-for-approximate-homomorphic-encryption · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set bootstrapping-for-approximate-homomorphic-encryption COLUMN VALUE