Zikai Zhou, Tsinghua University; William Seo and Edward Chen, Carnegie Mellon University; Alex Ozdemir, Max Planck Institute for Security and Privacy; Fraser Brown and Wenting Zheng, Carnegie Mellon University
Fully Homomorphic Encryption (FHE) allows computation on encrypted data without decrypting it. In theory, FHE makes privacy-preserving machine learning possible. In practice, however, it remains impractically slow for real workloads. A major source of slowdown is bootstrap operations; in CKKS, a popular FHE scheme for tensor workloads, the slowdown is compounded by scale management and rescale operations.
FHE compilers for machine learning inference aim to make bootstrap placement and scale management efficient and easy by compiling high-level tensor programs into optimized CKKS computations. Unfortunately, existing approaches miss crucial optimization opportunities because they overlook a key property of CKKS programs: bootstrap and rescale placement are fundamentally coupled through the level budget. In this paper, we present Orbit, an FHE compiler that jointly optimizes bootstrap and rescale placement through a novel Integer Linear Programming (ILP) formulation that reasons about both ciphertext level and scale constraints. To make this formulation tractable for structured tensor workloads, particularly convolutional neural networks, we introduce three techniques that reduce ILP complexity while preserving optimality. Across five workloads and multiple cryptographic parameter configurations, Orbit achieves a geometric mean speedup of 19% over DaCapo, 73% over Orion, and 52% over ReSBM, keeps compilation under 6 minutes, and retains model accuracy within 0.3% of plaintext execution.
USENIX Security '26 Open Access Sponsored by
King Abdullah University of Science and Technology (KAUST)
Open Access Media
USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.
author = {Zikai Zhou and William Seo and Edward Chen and Alex Ozdemir and Fraser Brown and Wenting Zheng},
title = {Orbit: Optimizing Rescale and Bootstrap Placement with Integer Linear Programming Techniques for Secure Inference},
booktitle = {35th USENIX Security Symposium (USENIX Security 26)},
year = {2026},
isbn = {978-1-939133-58-8},
address = {Baltimore, MD},
pages = {61--80},
url = {https://www.usenix.org/conference/usenixsecurity26/presentation/zhou},
publisher = {USENIX Association},
month = aug
}



