Over 100x Faster Bootstrapping in Fully Homomorphic Encryption through Memory-centric Optimization with GPUs¶
Authors: Jung, Kim, Ahn, Cheon, Lee
Year: 2021
Venue: TCHES 2021
type: library collection: catalogue status: auto
Links: ePrint 2021/508
Summary¶
Auto-extracted summary (unreviewed)
Presents the first GPU implementation of CKKS bootstrapping, showing that main-memory bandwidth, not computation, is the bottleneck of FHE operations on GPUs, and applying memory-centric optimisations such as kernel fusion, operation reordering, dnum selection for generalized key-switching, batched plaintext-ciphertext MACs and hoisting. On a V100 it achieves 7.02x faster homomorphic multiplication than the prior GPU implementation PrivFT, a 257x bootstrapping speed-up over a single-threaded CPU (0.423 us amortized per bit), and 40x faster logistic regression training than an 8-thread CPU.
Abstract¶
Fully Homomorphic encryption (FHE) has been gaining popularity as an emerging way of enabling an unlimited number of operations on the encrypted message without decryption. A major drawback of FHE is its high computational cost. Especially, a bootstrapping that refreshes the noise accumulated through consequent FHE operations on the ciphertext is even taking minutes. This significantly limits the practical use of FHE in numerous real applications. By exploiting massive parallelism available in FHE, we demonstrate the first GPU implementation for bootstrapping CKKS, one of the most promising FHE schemes that support arithmetic of approximate numbers. Through analyzing FHE operations, we discover that the major performance bottleneck is their high main-memory bandwidth requirement, which is exacerbated by leveraging existing optimizations targeted to reduce computation. These observations lead us to extensively utilize memory-centric optimizations such as kernel fusion and reordering primary functions. Our GPU implementation shows a 7.02× speedup for a single FHE-multiplication compared to the state-of-the-art GPU implementation and 0.423us of amortized bootstrapping time per bit, which corresponds to a speedup of 257× over a singlethreaded CPU implementation. By applying this to a logistic regression model training, we achieved a 40.0× speedup compared to the previous 8-thread CPU implementation with the same data.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | first GPU implementation of CKKS bootstrapping | llm | 0.90 |
| contribution | analysis identifying main-memory bandwidth as the key bottleneck | llm | 0.90 |
| contribution | intra- and inter-FHE-operation kernel fusion and reordering | llm | 0.90 |
| contribution | dnum selection for generalized key-switching on GPU | llm | 0.90 |
| contribution | batched plaintext-ciphertext MAC and hoisting in bootstrapping | llm | 0.90 |
| contribution | GPU-accelerated encrypted logistic regression training | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| schemes | RNS-CKKS | llm | 0.90 |
| libraries | CUDA | llm | 0.90 |
| models | logistic regression | llm | 0.90 |
| tasks | CKKS bootstrapping | llm | 0.90 |
| tasks | logistic regression training | llm | 0.90 |
| hardware | NVIDIA Tesla V100 GPU | llm | 0.90 |
| hardware | Intel Xeon Gold 6234 CPU (8 cores) | llm | 0.90 |
| security level | lambda > 80 (parameter sets of 98, 100, 106, 128 and 173 bits) | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| limitations | bootstrapping parameter sets add about 2^-19 mean error to the message | llm | 0.90 |
| limitations | PrivFT is closed-source, so comparison relies on numbers reported in its paper | llm | 0.90 |
| llm relevance | low | llm | 0.90 |
| key result | HMULT speed-up vs PrivFT GPU: 7.02x (N=2^16, 128-bit fusedH parameter set) | llm | 0.90 |
| key result | bootstrapping speed-up vs single-thread CPU: 257x (526.96 ms) (N=2^17, 173-bit security) | llm | 0.90 |
| key result | amortized bootstrapping time: 0.423 us per bit / 8 us per slot (19-bit precision) | llm | 0.90 |
| key result | logistic regression training speed-up: 40.0x (single GPU vs 8-thread CPU, same data) | llm | 0.90 |
| key result | HMULT speed-up vs single-thread CPU: 152x (N=2^16, log Q=2305, L=44) | llm | 0.90 |
System card: 100x faster GPU bootstrapping¶
| Group | 7. FHE libraries, GPU back-ends and compilers |
| Family | CKKS |
| Arithmetic | CUDA |
| Interaction | GPU technique |
| Model scale | - |
| Status | Foundational |
| Relation to the SoK | Showed CKKS bootstrapping is memory-bound on GPUs. |
| Note | Kernel fusion ideas reused by Phantom, Cheddar and FIDESlib. |
| Systems page | 100x faster GPU bootstrapping |
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 49 [p.1], BFV 4 [p.20], TFHE 3 [p.20], RSA 2 [p.23], Leveled / somewhat HE 2 [p.21]
- library: HElib 3 [p.23], cuFHE / nuFHE 3 [p.20], Microsoft SEAL 1 [p.22]
- model: Logistic regression 6 [p.1], CNN 1 [p.23], Naive Bayes 1 [p.21]
- dataset: MNIST 3 [p.19]
- hardware: GPU 112 [p.1], NVIDIA V100 4 [p.4], Intel Xeon 3 [p.4], CUDA 2 [p.16]
- technique: NTT 87 [p.3], Bootstrapping 84 [p.1], RNS 35 [p.2], Key switching 20 [p.2], Rescaling 16 [p.2], Rotations 14 [p.2], Sigmoid 2 [p.19], Convolution 2 [p.5]
- assumption: RLWE 3 [p.5], LWE 2 [p.16], 128-bit security 2 [p.2]
- task: Genomics 7 [p.2], Language modeling / generation 2 [p.7], Medical / healthcare 2 [p.24]
- topic: Homomorphic encryption 116 [p.1], Benchmark 2 [p.16]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/7-101_over-100x-faster-bootstrapping-in-fully-homomorphic-encrypti.pdf |
catalogue | 33 | 2.7 MB | 4e79a57e2129 |
Database key: over-100x-faster-bootstrapping-in-fully-homomorphic-encryption-through · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set over-100x-faster-bootstrapping-in-fully-homomorphic-encryption-through COLUMN VALUE