HPAO: Polynomial-Level Optimization for RNS–CKKS Programs

Recommended citation: HPAO: Polynomial-Level Optimization for RNS–CKKS Programs. Tianxiang Sui, Qing Zhu, JianXin Lai, Mingzhe Zhang, Yan Liu, Long Li, Peng Yuan, Linjie Xiao, Xiaojing Zhang, Shoumeng Yan, Jingling Xue. IEEE/ACM International Symposium on Code Generation and Optimization. CGO 2027.

Abstract

Fully Homomorphic Encryption (FHE) enables computation on encrypted data without decryption, but its overhead relative to plaintext execution remains prohibitively high for practical deployment. Existing FHE software stacks expose only coarse-grained cryptographic primitives to compilers, while runtime libraries optimize each primitive largely in isolation. Consequently, important cross-primitive optimizations—including ModUp hoisting, ModDown hoisting, fast multiply, and lazy modular reduction—remain manual, expert-driven, and difficult to apply systematically at the program scale.

We present HPAO, a compiler framework for polynomial-level optimization of RNS-CKKS programs. HPAO introduces HPOLY, a compact polynomial-level IR that exposes polynomial operations, basis management operations, and internal structure of composite primitives, such as the ModUp–DotProd–ModDown decomposition of KeySwitch, enabling cross-primitive optimization. On top of HPOLY, HPAO performs rule-based transformations guided by dataflow analysis and a profitability-aware cost model. This framework automates four optimizations previously implemented only manually or through specialized library routines: ModUp hoisting (HPAO-MU), ModDown hoisting (HPAO-MD), fast multiply with static encoding (HPAO-FM), and lazy modular reduction via bit-width analysis (HPAO-LM).

We implement HPAO in ANT-ACE, a state-of-the-art FHE compiler, and evaluate it on seven DNNs under the RNS–CKKS scheme on CPUs. Across these workloads, HPAO achieves speedups of up to 2.06× over ANT-ACE, with a geometric-mean speedup of 1.54×.