DaCapo: Automatic Bootstrapping Management for Efficient Fully Homomorphic Encryption¶
Authors: S. Cheon; Y. Lee; D. Kim; J. M. Lee; S. Jung; T. Kim; D. Lee; H. Kim
Year: 2024
Venue: USENIX Security 2024
type: library collection: catalogue, sok-references status: auto
Links: link
Summary¶
Auto-extracted summary (unreviewed)
DaCapo is the first FHE compiler that automatically places bootstrapping operations in RNS-CKKS programs. It uses liveness analysis of live-out ciphertexts (including bypass edges) to find candidate insertion points and estimates operation latencies under different scale-management scenarios to choose the cheapest plan. On ResNet-20/44, AlexNet, VGG16, SqueezeNet and MobileNet with ReLU or SiLU activations on CIFAR-10, implemented with the GPU HEaaN library, DaCapo matches PyTorch accuracy within 0.1% and runs 1.21x faster on average than hand-placed bootstrapping.
Abstract¶
By supporting computation on encrypted data, fully homomorphic encryption (FHE) offers the potential for privacypreserving computation offloading. However, its applicability is constrained to small programs because each FHE multiplication increases the scale of a ciphertext with a limited scale capacity. By resetting the accumulated scale, bootstrapping enables a longer FHE multiplication chain. Nonetheless, manual bootstrapping placement poses a significant programming burden to avoid scale overflow from insufficient bootstrapping or the substantial computational overhead of unnecessary bootstrapping. Additionally, the bootstrapping placement affects costs of FHE operations due to changes in scale management, further complicating the overall management process. This work proposes DACAPO, the first automatic bootstrapping management compiler. Aiming to reduce bootstrapping counts, DACAPO analyzes live-out ciphertexts at each program point and identifies candidate points for inserting bootstrapping operations. DACAPO estimates the FHE operation latencies under different scale management scenarios for each bootstrapping placement plan at each candidate point, and decides the bootstrapping placement plan with minimal latency. This work evaluates DACAPO with deep learning models that existing FHE compilers cannot compile due to a lack of bootstrapping support. The evaluation achieves 1.21×speedup on average compared to manually implemented FHE programs.
Source: pdf
Extracted details¶
| Field | Value | Source | Confidence |
|---|---|---|---|
| contribution | first automatic bootstrapping management compiler for RNS-CKKS | llm | 0.90 |
| contribution | liveness analysis of live-out ciphertexts with bypass edges to restrict bootstrapping candidates | llm | 0.90 |
| contribution | latency estimation under different scale-management scenarios for each placement plan | llm | 0.90 |
| contribution | cost-aware selection of the minimal-latency bootstrapping plan | llm | 0.90 |
| schemes | CKKS | llm | 0.90 |
| libraries | HEaaN | llm | 0.90 |
| libraries | PyTorch | llm | 0.90 |
| models | ResNet-20 | llm | 0.90 |
| models | ResNet-44 | llm | 0.90 |
| models | AlexNet | llm | 0.90 |
| models | VGG-16 | llm | 0.90 |
| models | SqueezeNet | llm | 0.90 |
| models | MobileNet | llm | 0.90 |
| datasets | CIFAR-10 | llm | 0.90 |
| tasks | image classification | llm | 0.90 |
| tasks | FHE program compilation / bootstrapping placement | llm | 0.90 |
| hardware | GPU (HEaaN GPU-accelerated library, model not specified) | llm | 0.90 |
| security level | 128-bit | llm | 0.90 |
| interaction | non-interactive FHE | llm | 0.90 |
| code url | https://github.com/corelab-src/elasm.References (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/tuneinsight/lattigo (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/CEA-LIST/Cingulata (URL found in the full text) | regex | 0.50 |
| code url | https://github.com/corelab-src/elasm | llm | 0.90 |
| llm relevance | medium | llm | 0.90 |
| key result | speed-up over manual bootstrapping placement: 1.21x on average (12 benchmarks (6 models x ReLU/SiLU), waterline 240) | llm | 0.90 |
| key result | accuracy: 90.7% (ResNet-20 ReLU), 93.8% (VGG16 ReLU) (1,000 CIFAR-10 images, within 0.1% of PyTorch) | llm | 0.90 |
| key result | manual bootstrapping placement effort: ~4 hours per benchmark per waterline (baseline implementation) | llm | 0.90 |
| key result | maximum error from approximate activations: 13 bits (negligible accuracy difference) | llm | 0.90 |
System card: DaCapo¶
| Group | 7. FHE libraries, GPU back-ends and compilers |
| Family | CKKS compiler |
| Arithmetic | - |
| Interaction | Compiler/framework |
| Model scale | - |
| Status | Active |
| Relation to the SoK | Automatic bootstrapping placement for CKKS programs. |
| Note | SoK notes optimal bootstrapping placement is NP-complete in general. |
| Systems page | DaCapo |
SoK reference [68]¶
S. Cheon, Y. Lee, D. Kim, J. M. Lee, S. Jung, T. Kim, D. Lee, and H. Kim, “DaCapo: Automatic bootstrapping management for efficient fully homomorphic encryption,” in USENIX Security 2024: 33rd USENIX Security Symposium, D. Balzarotti and W. Xu, Eds. Philadelphia, PA, USA: USENIX Association, Aug. 14– 16, 2024. [Online]. Available: https://www.usenix.org/conference/ usenixsecurity24/presentation/cheon
Listed on the reference page of the site.
Keyword mentions¶
Counts of vocabulary terms in the full text (first page of occurrence in brackets).
- scheme: CKKS 73 [p.2], TFHE 3 [p.18]
- library: EVA / CHET 14 [p.5], HEaaN (library) 6 [p.3], Microsoft SEAL 2 [p.18], HElib 2 [p.17], TFHE-rs 2 [p.18], Zama 2 [p.18], PALISADE 1 [p.18], Lattigo 1 [p.15], Concrete (Zama) 1 [p.18], PyTorch 1 [p.11]
- model: ResNet 30 [p.2], AlexNet 22 [p.3], VGG 16 [p.3], MobileNet 15 [p.3], CNN 5 [p.15], LeNet 1 [p.5]
- dataset: CIFAR-10 3 [p.11]
- hardware: GPU 7 [p.3], NVIDIA RTX 1 [p.11]
- technique: Bootstrapping 151 [p.1], RNS 71 [p.2], ReLU 32 [p.3], Rescaling 27 [p.3], Compiler 23 [p.2], Convolution 17 [p.5], Rotations 9 [p.3], Polynomial approximation 2 [p.10], Minimax approximation 2 [p.10], SIMD packing 2 [p.2]
- assumption: Lattice-based 4 [p.2], RLWE 2 [p.3], LWE 2 [p.16]
- topic: Homomorphic encryption 50 [p.2], Benchmark 17 [p.10], Open source 8 [p.15], Privacy-preserving machine learning 4 [p.2]
Files¶
| Path (under papers/) | Collection | Pages | Size | SHA-256 | Note |
|---|---|---|---|---|---|
references/catalogue/7-106_dacapo-automatic-bootstrapping-management-for-efficient-full.pdf |
catalogue | 19 | 1.3 MB | 20c7e8451898 |
|
references/sok-references/068_dacapo-automatic-bootstrapping-management-for-efficient-full.pdf |
sok-references | 19 | 1.3 MB | 20c7e8451898 |
byte-identical to references/catalogue/7-106_dacapo-automatic-bootstrapping-management-for-efficient-full.pdf |
Database key: dacapo-automatic-bootstrapping-management-for-efficient-fully · created 2026-11-05 · updated 2026-11-05 · edit with python3 tools/paperdb.py set dacapo-automatic-bootstrapping-management-for-efficient-fully COLUMN VALUE