一句话：提出 ReSBM 编译器，用区域划分与最小割联合优化 RNS-CKKS 同态加密推理中的尺度管理和自举放置。
RNS-CKKS 全同态加密支持定点运算与 SIMD，但同态乘法引发的尺度升级与容量溢出，以及编译期尺度管理与自举放置，给加密推理带来挑战。本文提出 ReSBM 编译器：将程序数据流图划分为乘法深度为一的区域，使尺度管理操作与自举只影响区域延迟，而不改变活跃输出密文的尺度与层级；随后用分层策略求解 NP 难的最优自举放置，包括区域内最小割优化、跨区域的自举引导重缩放区域识别与终端试探自举，以及全局最小层级自举放置。CPU 上多种复杂模型评估显示，ReSBM 编译更快，加密推理效率较领先方法平均提升 12.1%。
The RNS-CKKS scheme in Fully Homomorphic Encryption (FHE) supports crucial features for privacy-preserving machine learning, such as fixed-point arithmetic and SIMD-style vectorization. Yet, managing the escalation of ciphertext scales from homomorphic multiplications, which risks capacity overflow, along with bootstrapping, presents significant challenges. These complexities are exacerbated by the need to efficiently handle scale and bootstrapping at compile time while ensuring rapid encrypted inference. In this paper, we present ReSBM, a novel compiler technique that simultaneously optimizes scale and bootstrapping for encrypted inference under RNS-CKKS. By partitioning a program's data flow graph (DFG) into regions with a uniform multiplicative depth of one, RESBM ensures that placements of Scale Management Operations (SMOs) and bootstraps affect only the latency of a region, not the scales and levels of its live-out ciphertexts. Our region-based approach tackles the NP-hard challenge of optimal bootstrapping placement with hierarchical strategies: (1) optimal intra-region SMO and bootstrapping placement using min-cut, (2) bootstrapping-guided rescaling region identification across a sequence of regions, culminating in tentative bootstrapping at two terminal regions, and (3) minimal-level bootstrap placement across the DFG, elevating ciphertexts only to the necessary minimal level. Validation across a variety of complex models on CPUs shows that ReSBM not only compiles these models more rapidly than a leading method but also boosts encrypted inference efficiency by an average of 12.1% when compared to another leading method. Consequently, ReSBM substantially improves the practical deployment of large models for encrypted inference, surpassing existing methods in terms of both compilation speed and inference performance.
@inproceedings{LiuLLSXYZZCX25,
title = {<scp>ReSBM:</scp>
Region-based Scale and Minimal-Level Bootstrapping Management for FHE via Min-Cut},
author = {Yan Liu and Jianxin Lai and Long Li and Tianxiang Sui and Linjie Xiao and Peng Yuan and Xiaojing Zhang and Qing Zhu and Wenguang Chen and Jingling Xue},
booktitle = {ASPLOS},
year = {2025},
doi = {10.1145/3669940.3707276}
}