Skip to content

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