一句话：首个支持循环的全同态加密自举管理编译器，通过循环感知放置与优化降低自举开销。
全同态加密（FHE）支持在密文上计算，但重复乘法会耗尽密文的有限层级；自举可重置层级，却因高开销和下溢风险需要精细放置，加重编程负担。已有编译器虽能自动放置自举，但不支持循环。本文提出首个循环感知的自举管理编译器 HALO，它匹配循环中 live-in 与 loop-carried 密文的加密类型和层级，并通过将循环携带变量打包为单个密文、展开短循环、按需调整自举目标层级来减少循环体内自举次数与延迟。在七个含平坦和嵌套循环的机器学习程序上，HALO 相比在全展开循环上放置自举的最新编译器取得 27% 性能加速，并将编译时间和代码大小分别以几何平均降低 209.12 倍和 11.0 倍。
Thanks to the computation ability on encrypted data, fully homomorphic encryption (FHE) is an attractive solution for privacy-preserving computation. Despite its advantages, FHE suffers from limited applicability in small programs because repeated FHE multiplications deplete the level of a ciphertext, which is finite. Bootstrapping reinitializes the level, thus allowing support for larger programs. However, its high computational overhead and the risk of level underflow require sophisticated bootstrapping placement, thereby increasing the programming burden. Although a recently proposed compiler automatizes the bootstrapping placement, its applicability is still limited due to lack of loop support. This work proposes the first loop-aware bootstrapping management compiler, called HALO, which optimizes bootstrapping placement in an FHE program with a loop. To correctly support bootstrapping-enabled loops, HALO matches encryption types and levels between live-in and loop-carried ciphertexts in the loops. To reduce the bootstrapping overheads, HALO decreases the number of bootstrapping within a loop body by packing the loop-carried variables to a single ciphertext, reduces wasted levels in a short loop body by unrolling the loop, and optimizes the bootstrapping latency by adjusting the target level of bootstrapping as needed. For seven machine learning programs with flat and nested loops, HALO shows 27% performance speedup compared to the state-of-the-art compiler that places bootstrapping operations on fully unrolled loops. In addition, HALO reduces the compilation time and code size by geometric means of 209.12x and 11.0x compared to the compiler, respectively.
@inproceedings{Cheon0Y0YJL025,
title = {HALO: Loop-aware Bootstrapping Management for Fully Homomorphic Encryption},
author = {Seonyoung Cheon and Yongwoo Lee and Hoyun Youm and Dongkwan Kim and Sungwoo Yun and Kunmo Jeong and Dongyoon Lee and Hanjun Kim},
booktitle = {ASPLOS},
year = {2025},
doi = {10.1145/3669940.3707275}
}