Skip to content

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