Theses

Loop-Aware Bootstrapping Management for Efficient Fully Homomorphic Encryption [abstract] (PDF)
Seonyoung Cheon
Ph.D. Thesis, School of Electronical and Electronic Engineering, Yonsei University, August 2026.

Fully homomorphic encryption (FHE) enables computation directly on encrypted data without decryption, making it a promising approach for privacy-preserving machine learning in untrusted environments such as cloud computing. Among FHE schemes, RNS-CKKS is particularly well suited for machine learning because it supports fixed-point arithmetic and SIMD parallelism. However, repeated multiplications in RNS-CKKS consume the finite levels of a ciphertext. To continue computation beyond this limit, bootstrapping must recover consumed levels, but it is the most expensive operation in RNS-CKKS. Moreover, bootstrapping placement affects both the number of bootstrapping operations and the cost of subsequent FHE operations through scale management. Thus, optimizing placement requires considering overall program performance, making manual placement difficult and often inefficient.

This dissertation presents FORTE, a bootstrapping management compiler for fully homomorphic encryption that automatically inserts and optimizes bootstrapping operations. FORTE addresses two key challenges: placement for programs with static control flow and management for programs containing loops with dynamic iteration counts.

For programs with static control flow, FORTE introduces liveness-aware candidate selection, which analyzes live-out ciphertexts to identify insertion points that require the fewest simultaneous bootstrapping operations. FORTE further refines this candidate set through bypass-edge analysis, which excludes long-lived ciphertexts that do not require bootstrapping. Given the resulting candidate set, FORTE estimates placement costs under different scale-management plans and uses dynamic programming to select the lowest-latency plan. Evaluation on programs with static loop counts shows that FORTE achieves a geometric-mean speedup of 1.26× over manually implemented FHE programs by automatically finding lower-latency bootstrapping placements.

For programs containing loops, FORTE extends its management framework with loop-aware code generation and optimization. FORTE generates iteration-consistent loop code by matching the encryption status and levels of loop-carried ciphertexts across iterations through loop peeling and bootstrapping placement. To reduce the overhead introduced by iterative execution and level matching, FORTE applies three loop-aware optimizations: packing loop-carried variables into a single ciphertext, level-aware loop unrolling, and bootstrapping target-level tuning. For programs with dynamic loop counts, FORTE achieves 27% performance improvement over the state-of-the-art compiler that relies on full loop unrolling.