1
Ciphertext- and Polynomial-Level Optimization for Fully Homomorphic Encryption
arXiv:2607.15750v1 [cs.CR] 17 Jul 2026
Seongho Kim , Heelim Choi , Jaemin Kim , Seonyoung Cheon , Dongkwan Kim , Jaeho Lee , Hoyun Youm , Dongyoon Lee Member, IEEE, Hanjun Kim Member, IEEE, Yongwoo Lee Member, IEEE
Abstract—Fully homomorphic encryption (FHE) schemes such as RNS-CKKS enable privacy-preserving services by allowing direct computation on encrypted data. While recent FHE compilers optimize FHE programs, they operate at the coarse-grained ciphertext level, where each ciphertext operation comprises a sequence of polynomial operations. At this granularity, the compilers miss optimization opportunities across ciphertext operations. This work presents Recifhe, a new multi-level compiler that supports not only ciphertext-level but also polynomial-level optimization. At the ciphertext level, Recifhe transforms a nonFHE input program into an FHE program by inserting ciphertext management operations and applies global optimizations. At the polynomial level, Recifhe eliminates redundant polynomial computations across ciphertext operations. Recifhe achieves a 1.25× speedup over ciphertext-level-only optimization.
fusion. The profitability of ModDown hoisting depends on the dataflow, so Recifhe profiles the latency of each polynomial operation and applies hoisting only when the estimated latency benefit exceeds the overhead. Recifhe also reduces the memory growth inherent in polynomial-level optimization, caused by the extended polynomial lifetimes, through liveness-driven operation scheduling. As a result, Recifhe achieves a 1.25× speedup over ciphertext-level-only optimization, and a 1.36× speedup with 0.93× the memory footprint over the manually optimized polynomial sequences in existing FHE libraries.
Index Terms—FHE compiler, RNS-CKKS, ciphertext-level optimization, polynomial-level optimization
The residue number system (RNS) variant of CKKS (RNSCKKS) [1] encodes a vector of real numbers into a plaintext polynomial in Z[X]/(X N + 1), where N is the polynomial modulus degree, providing N/2 fixed-point slots with SIMD semantics. RNS-CKKS encrypts the plaintext as a pair of ciphertext polynomials in ZQ [X]/(X N + 1), where the coefficient modulus Q bounds the coefficients. Each polynomial consists QLof up to L residue polynomials with moduli qi , where Q = i=1 qi . The GPU library [11] in this work uses N = 216 and L = 27 with 32-bit moduli, so a plaintext occupies 4 bytes × N × L = 6.75 MB, and a ciphertext twice as much. Recent FHE compilers [2]–[8] operate at the ciphertext level, managing two attributes of a ciphertext, the level and the scale. The level is the number of Rescale operations applicable to the ciphertext, up to L, and the scale is the fixedpoint scaling factor by which the encoded message value is multiplied. A multiplication on a ciphertext enlarges the scale of the result, potentially incurring scale overflow. Rescale divides the scale by the last modulus and lowers the level by one, preventing the overflow. Bootstrap restores the depleted level to its maximum of L. The ciphertext-level compilers automatically place the ciphertext management operations, Rescale and Bootstrap. The scale management compilers [2]–[5] insert Rescale operations to prevent scale overflow. The bootstrapping management compilers [6]–[8] insert Bootstrap operations that recover the level, supporting programs with long multiplication chains while minimizing the Bootstrap count. These compilers also apply global optimizations, such as Rescale hoisting [3], [8], to reduce ciphertext operations but fail to remove redundant polynomial computations across ciphertext operations. Each ciphertext operation comprises a sequence of polynomial operations, and the polynomial operations manage a third
I. I NTRODUCTION Fully homomorphic encryption (FHE) enables direct computation on encrypted data without decryption, supporting privacy-preserving services. Among FHE schemes, RNSCKKS [1] is suited to machine learning because it supports fixed-point arithmetic on real numbers and SIMD vectorization. To utilize RNS-CKKS, programmers must transform a non-FHE program into an FHE program by inserting ciphertext management operations that adjust ciphertext attributes. To reduce the programming burden, recently proposed FHE compilers [2]–[10] automatically place ciphertext management operations and optimize FHE programs, but they fail to fully exploit optimization opportunities. Most compilers [2]–[8] operate at the ciphertext level, where each ciphertext operation comprises a sequence of polynomial operations, thereby missing fine-grained optimization opportunities such as eliminating redundant polynomial operations across ciphertext operations. A few compilers [9], [10] lower ciphertext operations into polynomial sequences, but their optimization is limited to a single ciphertext operation because the optimization complexity increases with more operations and attributes to manage. This work introduces Recifhe, a new multi-level compiler that supports both ciphertext-level and polynomial-level optimizations, each suited to its granularity. At the ciphertext level, Recifhe transforms a non-FHE input program into an FHE program and applies existing global optimizations such as Rescale hoisting. At the polynomial level, Recifhe eliminates redundant polynomial computations across ciphertext operations through common subexpression elimination, performance-aware ModDown hoisting, and operation
II. BACKGROUND AND M OTIVATION
2
Input DSL
Ciphertext-Level IR
t0 = Mul(a, p0); t1 = Mul(Rot(b), p1); t2 = Mul(Rot(c), p2); t3 = Mul(Rot(d), p3); t4 = Add(RS(t1), RS(t2)); t5 = Add(RS(t0), t4); out = Add(t5, RS(t3));
e.g. Rescale Hoisting a
b
c
Mul Rot MU Add KIP Auto
b
c
d
Rot Rot Rot
Mul Mul Mul Mul
Mul Mul Mul Mul
RS
RS
RS
RS
a
Add
Add
b
c
d
MU
MU
MU
a
Perf.-Aware Hoisting
b
c
d
MU
MU
MU
b
c
d
MU
MU
MU
a
b
c
d
MU
MU
MU
KIP KIP KIP
KIP KIP KIP
KIP KIP KIP
MD
MD
MD
Auto Auto Auto
Auto Auto Auto
pMul pMul pMul pMul
pMul pMul pMul pMul
MD
MD
MD
Auto Auto Auto
Auto Auto Auto
pMul pMul pMul pMul
pMul pMul pMul pMul
RS
pAdd
pAdd
pAdd
Recifhe Compiler
a
Operation Fusion
KIP KIP KIP
Add
Add
Add
MulCP pMul pMulCP Rotation MD ModDown ModUp invMD inverse MD AddCC RS Rescale KeyInnerProduct Automorphism
a
Lowering
Rot Rot Rot
Add
Abbreviation
d
Polynomial-Level IR Candidate Analysis
pAdd
pAdd pAdd
pAdd
invMD
MD
pAdd
pAdd
RS
RS
pAdd
pAdd pAdd MD+RS
RS
Fig. 1. Overview of Recifhe with the running example. The plaintexts (p0–p3) of the input DSL are omitted for simplicity.
TABLE I C IPHERTEXT- TO -P OLYNOMIAL O PERATION M APPING
Ciphertext Op.
Polynomial Op.
AddCC, AddCP MulCP MulCC Rotate
pAdd pMulCP pMulCC→ModUp→KIP→ModDown ModUp→KIP→ModDown→Automorphism
attribute, the RNS basis. The RNS basis is the set of moduli over which a polynomial is represented, and a polynomial operation requires its operands to share the same RNS basis. Table I lists the polynomial operation sequence of each ciphertext operation, omitting Rescale and Bootstrap, which appear identically at both levels. MulCC and Rotate produce an intermediate result under a different key, so key-switching restores it to the original key via ModUp, KIP, and ModDown. KIP computes the inner product of the ModUp result with the key-switching key, amplifying the key-switching error, so RNS-CKKS temporarily extends the working Q modulus from Q to P Q with an auxiliary modulus P = j pj . ModUp lifts a polynomial from the Q basis to the P Q basis by adding the pj moduli to its basis, and after KIP, ModDown divides the result by P to reduce the key-switching noise and returns it to the Q basis. Automorphism rotates the slots through an index permutation. The RNS-basis-insensitive operations in Table II apply identically on both the Q and P Q bases, processing each residue polynomial independently and preserving the factor P introduced by ModUp. ModUp, ModDown, Rescale, and Bootstrap, which change the RNS basis, internally use the number theoretic transform (NTT) and its inverse (iNTT) to perform basis conversion. Fusing an adjacent pair of these operations can cancel out the internal transformations. A few compilers [9], [10] decompose ciphertext operations into polynomial operation sequences but do not manage the RNS basis across ciphertext operations, limiting their optimization to a single ciphertext operation. Existing FHE libraries [11], [12] manually implement optimizations across ciphertext operations, such as removing repeated ModDown operations. The library optimization applies a fixed algorithm tuned to a specific dataflow, so it neither adapts to new programs nor accounts for the trade-off between the
TABLE II RNS-BASIS S ENSITIVITY OF P OLYNOMIAL O PERATIONS
Insensitive Sensitive
pAdd, pMulCP, Automorphism ModUp, KIP, ModDown, pMulCC, Rescale, Bootstrap
removed ModDown operations and the operations raised to the P Q basis. Furthermore, the library optimization extends polynomial lifetimes, incurring high memory overhead. These limitations motivate a compiler that applies dataflow-adaptive optimization at the polynomial level. III. R ECIFHE C OMPILER Recifhe applies each optimization at the granularity suited to it, adopting a multi-level design that performs global optimization on a ciphertext-level intermediate representation (IR) and fine-grained optimization across ciphertext operations on a polynomial-level IR. On the ciphertext-level IR, as shown in Fig. 1, Recifhe transforms an input Python DSL program into an FHE program and applies existing global optimizations, including the ciphertext management operation placement and Rescale hoisting. Applying global optimizations at the coarse-grained ciphertext level allows Recifhe to reduce optimization complexity compared to optimizing the entire program directly at the fine-grained polynomial level. Recifhe then decomposes each ciphertext operation into its corresponding polynomial sequence, enabling optimizations across ciphertext operations. Recifhe identifies candidates for ModDown hoisting on the polynomial-level IR through dataflow analysis, applies performance-aware hoisting guided by offline profiling, fuses operations, and schedules polynomial operations to reduce memory growth. Fig. 1 illustrates Recifhe on a running example that computes y = p0 ·a+p1 ·rot(b, r1 )+p2 ·rot(c, r2 )+p3 ·rot(d, r3 ), where each rotated ciphertext is multiplied by a plaintext and the resulting products are accumulated into a single output. This rotate-multiply-accumulate pattern recurs in FHE matrix multiplication algorithms [8], [13], where each rotation lowers into ModUp, KIP, ModDown, and Automorphism. The results of the three ModDown operations flow through only RNS-basis-insensitive operations, so hoisting them into
3
Algorithm 1: Performance-Aware ModDown Hoisting. Input: Polynomial-level function DAG Π, Latency profile E Output: ModDown-hoisted DAG Π 1 Function PerformanceAwareModDownHoisting (Π, E) : 2 S = {op ∈ Π | isSensitive(op) ∧ op ̸= ModDown} 3 I = {op ∈ Π | isInsensitive(op) ∨ op = ModDown} 4 foreach s ∈ S do 5 B ←S {b ∈ SS| ∃π ∈ Path(b, s) : ops(π) ⊆ I} 6 R ← b∈B π∈Path(b,s) ops(π) 7 M ← {op ∈ R | op = ModDown} 8 if |M | < 2 then 9 continue 10 end 11 F ← findNearestSensitiveSuccessors(Π, M ) 12 L ← {op ∈ ∈ M, f ∈ F } PPath(m, f ) | mP 13 benefit ← m∈M E(m) − f ∈F E(ModDown f) P 14 overhead ← op∈L EP Q (op) − EQ (op) 15 if benefit > overhead then 16 Π ← reassociate(Π, R, M ) 17 Π ← removeModDown(Π, M ) 18 Π ← insertModDownBefore(Π, F ) 19 end 20 end 21 return Π 22 end
a single ModDown reduces the ModDown count and enables fusing the surrounding operations. Rescale Hoisting and Lowering. Recifhe first places Bootstrap operations and manages the scale of the program using existing ciphertext-level techniques [2]–[8], so the level and the scale of every value are known by the time Recifhe lowers the ciphertext operations. Recifhe inherits Rescale hoisting [3], [8] and maintains this global transformation at the ciphertext level, since the program contains more operations at the polynomial level. Recifhe hoists Rescale operations past any operation that preserves the level and the scale, merging them to reduce the Rescale count. Recifhe then lowers each ciphertext operation into its polynomial operation sequence. The lowering translates each ciphertext operation independently, so Recifhe also eliminates repeated polynomial operations for the same input polynomial across the lowered sequences through common subexpression elimination. Candidate Analysis. Recifhe searches the polynomial-level DAG Π of each function for candidate regions where multiple ModDown operations merge into fewer ones, as Algorithm 1 describes. Recifhe visits each RNS-basis-sensitive operation s other than ModDown and forms its region. The boundary operations B are the preceding sensitive operations other than ModDown that can reach s through RNS-basis-insensitive or ModDown operations only, and the region R consists of the intermediate operations on every path from a boundary operation to s. The ModDown operations in the region form the set M , and their results can flow toward s only through insensitive operations. The insensitive operations compute correctly on both the Q and P Q bases, so a hoisted ModDown crosses them without changing the encoded values. Recifhe takes the region as a candidate when M holds multiple ModDown operations. The regions of different sensitive operations may nest, and hoisting in a nested region composes with hoisting in its
enclosing region without conflict because Recifhe recomputes each region on the updated DAG at every visit. Performance-Aware Hoisting. Hoisting removes the ModDown operations in M of each candidate region and places one hoisted ModDown before each operation in the sensitive frontier F . Function findNearestSensitiveSuccessors finds F , the set of sensitive operations that the results of M first reach via RNS-basis-insensitive operations only, and ModDownf denotes the hoisted ModDown before each f ∈ F . The set L consists of the insensitive operations on the paths from M to F , which act on P Q-basis polynomials after hoisting. The P Q basis holds more moduli than the Q basis, so the operations in L incur more computation. Whether this added cost outweighs the savings from the removed ModDown operations depends on the dataflow of each region. Recifhe therefore profiles the latency E of every polynomial operation offline at each level and RNS basis, with the basis denoted as a subscript, and estimates the cost of a set of operations as the sum of their latencies. Recifhe accepts a hoist only when the benefit, the latency of M minus the latency of the hoisted ModDown operations at F , exceeds the overhead, the latency increase of L raised to the P Q basis. Recifhe applies an accepted hoist by reordering the accumulations in the region with function reassociate to gather the results of M , removing M , and inserting ModDownf before each f ∈ F . The reordering preserves the encoded result because modular addition is associative and commutative. Operation Fusion. Recifhe fuses adjacent operations to remove an iNTT and forward NTT pair with no operation between them. Such a pair arises when a ModDown is adjacent to a Rescale, so fusing them into a single kernel of the backend library keeps the polynomial in the evaluation domain throughout. The pair is not always adjacent, as in the running example where an addition separates a ModDown from a Rescale. Recifhe then raises the other operand of the addition, which remains on the Q basis, to the P Q basis by inserting an invModDown, allowing the ModDown to sink past the addition and become adjacent to the Rescale. invModDown is a lightweight lift that multiplies each residue polynomial in the Q basis by P and zerofills the residue polynomials for the moduli in P , satisfying ModDown(invModDown(a)) = a. Polynomial Scheduling. Optimization at the polynomial level inherently increases memory pressure, and Recifhe reduces the memory growth with polynomial scheduling. The lowering places the polynomial operations of each ciphertext operation consecutively, separating a value’s producer from its consumers, and hoisting and fusion further extend polynomial lifetimes across ciphertext boundaries. Recifhe therefore moves each operation to immediately follow its most recently defined operand, shrinking the operand’s live range when the operation is its last use. Recifhe then reuses the buffer of a dead value for a later result of the same size, reducing the number of polynomials that are live simultaneously. IV. E VALUATION Environment. Recifhe is built on the MLIR-based Hecate framework [2] with a Python DSL frontend and Cheddar [11]
(a) Latency comparison. Lower is better.
OOM
1.23× 1.14×
Ciphertext Level Cheddar Recifhe
OOM
2.0 1.5 1.0 0.5 0.0
OOM
ial ion iate SVM eans MLP LoLA eNet xNet G16 sNet eNet eNet ean L Ale VG Re eez obil Gm nogmress ltivar y Km l Po Re Mu Squ M
Normalized Memory
OOM
1.09× 0.80×
Ciphertext Level Cheddar Recifhe
OOM
2.0 1.5 1.0 0.5 0.0
OOM
Normalized Latency
4
ial ion iate SVM eans MLP LoLA eNet xNet G16 sNet eNet eNet ean L Ale VG Re eez obil Gm nogmress ltivar y Km l Po Re Mu Squ M (b) Memory footprint comparison. Lower is better.
Fig. 2. Comparison of the Cheddar [11] baseline and Recifhe over the ciphertext-level-only baseline.
as the GPU backend, and is retargetable to other backend libraries by re-profiling operation latencies. Recifhe is evaluated on 12 benchmarks against two baselines sharing the same frontend and backend. The ciphertext-level-only baseline in Fig. 2 applies prior ciphertext-level optimizations [2]–[8], and the Cheddar baseline adds the manually optimized polynomial sequences on top of that baseline. All three configurations share the same RNS-CKKS setting, with the polynomial modulus degree N = 216 , the default scale of 240 , and the Cheddar Bootstrap modulus configuration at the 128-bit security level, yielding an effective multiplicative depth of 13 between Bootstrap operations. All benchmarks use pre-encoded plaintexts and place Bootstrap operations following prior benchmark suites [6]–[8]. The experiments run on two Intel Xeon Gold 6326 CPUs with 512 GB RAM and an NVIDIA RTX PRO 6000 Blackwell Max-Q GPU with 96 GB VRAM. Analysis. The Recifhe reimplementation of the library optimization [11] validates the backend equivalence, reproducing the Cheddar artifact on ResNet with ReLU activation within 0.9% by running in 0.714 s compared to the artifact’s 0.720 s. Fig. 2a reports the speedup normalized to the ciphertextlevel-only baseline, and Fig. 2b reports the memory footprint. The Cheddar baseline accelerates 6 of the 9 benchmarks it completes but slows down on the other 3, because the library optimization raises operations into the heavier P Q basis regardless of whether the dataflow makes the hoist profitable, exactly the fixed-algorithm limitation described in §II. The slowdown on the 3 benchmarks lowers the average to 0.92× the speed of the ciphertext-level-only baseline. The same unconditional transformation also drives the Cheddar baseline’s memory cost, since it lacks a scheduling pass to reclaim the extended live ranges. Its P Q-basis polynomials thus remain live longer than necessary, using more memory than the ciphertext-level-only baseline on every benchmark it completes, 1.23× the footprint on average, and running out of memory on 3 of the 12 benchmarks. In contrast, Recifhe applies hoisting only when Algorithm 1 finds it profitable, reaching 1.25× speedup over the ciphertextlevel-only baseline across all 12 benchmarks and 1.36× over the Cheddar baseline on the 9 benchmarks the Cheddar baseline completes. The liveness-driven scheduling of Recifhe reduces the memory consumption from hoisting and fusion, holding the footprint to 1.14× that of the ciphertext-levelonly baseline and 0.93× that of the Cheddar baseline. These gains cost additional compile time, with the polynomial-level passes taking 39.0% of Recifhe’s compile time on average,
and performance-aware hoisting and fusion taking 1.31% and 14.3% of the total compile time, respectively. Compile times range from 0.0182 s (Polynomial Regression) to 22.4 s (MobileNet), averaging 5.14 s across all 12 benchmarks, 2.92× that of the ciphertext-level-only baseline in geometric mean. V. C ONCLUSION This work proposes Recifhe, a new multi-level compiler that automatically generates FHE programs with global optimizations at the ciphertext level and removes, at the polynomial level, the redundant polynomial computations that neither ciphertext-level compilers nor library optimizations remove. Guided by measured per-operation latencies, Recifhe applies ModDown hoisting only when the estimated benefit exceeds the overhead, and reduces the memory growth these transformations introduce through liveness-driven scheduling. As a result, Recifhe achieves a 1.25× speedup over ciphertextlevel-only optimization. R EFERENCES [1] J. H. Cheon et al., “A full rns variant of approximate homomorphic encryption,” in Proc. Sel. Areas in Cryptog., 2018. [2] Y. Lee et al., “HECATE: Performance-Aware Scale Optimization for Homomorphic Encryption Compiler,” in Proc. IEEE/ACM Int. Symp. Code Gener. Optim., 2022. [3] ——, “Performance-aware scale analysis with reserve for homomorphic encryption,” in Proc. ACM Int. Conf. on Archit. Support for Prog. Lang. Oper. Syst., vol. 1, 2024. [4] R. Dathathri et al., “EVA: An encrypted vector arithmetic language and compiler for efficient homomorphic computation,” in Proc. ACM SIGPLAN Conf. on Program. Lang. Design Impl., 2020. [5] Y. Lee et al., “ELASM: Error-latency-aware scale management for fully homomorphic encryption,” in Proc. USENIX Secur. Symp., 2023. [6] S. Cheon et al., “DaCapo: Automatic bootstrapping management for efficient fully homomorphic encryption,” in Proc. USENIX Secur. Symp., 2024. [7] ——, “HALO: Loop-aware bootstrapping management for fully homomorphic encryption,” in Proc. ACM Int. Conf. on Archit. Support for Prog. Lang. Oper. Syst., vol. 1, 2025. [8] A. Ebel, K. Garimella, and B. Reagen, “Orion: A fully homomorphic encryption framework for deep learning,” in Proc. ACM Int. Conf. on Archit. Support for Prog. Lang. Oper. Syst., vol. 1, 2025. [9] S. Park et al., “Heaan.mlir: An optimizing compiler for fast ring-based homomorphic encryption,” Proc. ACM Program. Lang., 2023. [10] L. Li et al., “Ant-ace: An fhe compiler framework for automating neural network inference,” in Proc. ACM/IEEE Int. Symp. Code Gener. and Optim., 2025. [11] W. Choi, J. Kim, and J. H. Ahn, “Cheddar: A swift fully homomorphic encryption library designed for gpu architectures,” in Proc. ACM Int. Conf. on Archit. Support for Prog. Lang. Oper. Syst., vol. 1, 2025. [12] A. Şah Özcan and E. Savaş, “HEonGPU: a GPU-based fully homomorphic encryption library 1.0,” Cryptol. ePrint Arch., 2024. [13] J.-P. Bossuat et al., “Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys,” in Proc. Adv. Cryptol. – EUROCRYPT, Part I, 2021.