💻 computer science

Ciphertext- and Polynomial-Level Optimization for Fully Homomorphic Encryption

This paper introduces Recifhe, a novel multi-level compiler for Fully Homomorphic Encryption that achieves a 1.25x speedup by performing global optimizations at the ciphertext level and eliminating redundant computations at the finer-grained polynomial level.

Original authors: Seongho Kim, Heelim Choi, Jaemin Kim, Seonyoung Cheon, Dongkwan Kim, Jaeho Lee, Hoyun Youm, Dongyoon Lee, Hanjun Kim, Yongwoo Lee

Published 2026-07-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Seongho Kim, Heelim Choi, Jaemin Kim, Seonyoung Cheon, Dongkwan Kim, Jaeho Lee, Hoyun Youm, Dongyoon Lee, Hanjun Kim, Yongwoo Lee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a giant puzzle, but you aren't allowed to look at the pieces. Instead, you have to solve the puzzle while wearing thick, foggy goggles that blur every shape and color. This is the world of Fully Homomorphic Encryption (FHE). It's a magical kind of math that lets computers crunch numbers on secret data without ever actually seeing the data itself. Think of it like a bank vault where a robot can count your money, add interest, and calculate your balance, all while the vault door stays locked and the robot never sees a single bill.

To make this magic work, the secret data is scrambled into something called a ciphertext. Inside the computer, this ciphertext isn't just one big block; it's actually a massive, complex polynomial (a fancy math equation with lots of terms). When the computer performs a simple task like "add these two numbers," it's actually running a long, winding sequence of smaller polynomial steps. The problem is that the software tools we use to tell the computer how to do this have been a bit clumsy. They've been treating the whole ciphertext like a single, heavy suitcase. They know how to pack the suitcase efficiently, but they don't look inside to see if they can rearrange the items within the suitcase to save space or time. They miss the tiny, hidden opportunities to make the math faster because they are looking at the problem from too far away.

Enter Recifhe, a new, super-smart compiler (a program that translates human instructions into machine code) created by Seongho Kim and his team. Think of Recifhe as a master organizer who doesn't just look at the suitcase; they open it up, take out every single item, and rearrange the whole pile to make the journey smoother.

The researchers found that by looking at the problem on two different levels, they could speed things up significantly. First, they looked at the "ciphertext level," which is the big picture. Here, they organized the flow of data to make sure the heavy lifting happened at the right times. But the real magic happened at the "polynomial level." This is the microscopic view where they looked at the individual math steps. They noticed that the computer was often doing the same math twice or carrying around extra "weight" (redundant calculations) that wasn't needed.

Recifhe uses a clever strategy called "performance-aware hoisting." Imagine you are carrying a heavy backpack up a hill. Sometimes, it's better to take the heavy item off your back before you start walking, carry it separately, and put it back on only when you absolutely have to. Recifhe does this with math operations. It figures out exactly when it's worth moving a heavy calculation to a different spot in the sequence. If the math shows that moving the calculation saves more time than it costs to move it, the compiler does it. If not, it leaves it alone. This isn't a guess; the team measured the time each tiny math step takes on their specific hardware to make sure every move was profitable.

The results are impressive. When they tested Recifhe on 12 different tasks, ranging from simple math problems to complex AI models like neural networks, it ran 1.25 times faster than the previous best methods that only looked at the big picture. Even more importantly, it didn't just get faster; it got smarter about memory. While other methods that tried to rearrange the math often caused the computer to run out of memory (like trying to fit too many suitcases in a tiny car), Recifhe's careful scheduling kept the memory usage low, using only 0.93 times the memory of the manually optimized versions found in existing libraries.

In short, the paper shows that by peeling back the layers of encryption and optimizing the tiny math steps inside, we can make secret computing much faster and more efficient. It proves that you don't have to choose between security and speed; with the right tools, you can have both.

Technical Summary: Recifhe – Ciphertext- and Polynomial-Level Optimization for Fully Homomorphic Encryption

Problem Statement
Fully Homomorphic Encryption (FHE) schemes, particularly RNS-CKKS, enable privacy-preserving computation on encrypted data but impose significant programming and performance burdens. Programmers must manually insert ciphertext management operations (e.g., Rescale, Bootstrap) to handle ciphertext attributes like level and scale. While recent FHE compilers automate this process, they operate primarily at the ciphertext level, where each ciphertext operation is treated as an atomic unit comprising a sequence of polynomial operations. This coarse granularity causes compilers to miss fine-grained optimization opportunities, such as eliminating redundant polynomial computations that occur across different ciphertext operations. Conversely, existing approaches that decompose operations into polynomial sequences often limit optimization to a single ciphertext operation due to complexity, or rely on manual library optimizations that use fixed algorithms. These manual optimizations fail to adapt to varying dataflows, often incurring unnecessary performance overhead or excessive memory growth by unconditionally raising operations to a heavier RNS basis (the $PQ$ basis) without evaluating profitability.

Methodology
The paper introduces Recifhe, a multi-level compiler designed to bridge the gap between coarse-grained ciphertext optimization and fine-grained polynomial optimization. Recifhe employs a two-tiered Intermediate Representation (IR) strategy:

Ciphertext-Level Optimization: Recifhe first transforms a non-FHE input program (written in a Python DSL) into an FHE program. At this level, it performs global optimizations such as placing ciphertext management operations (Rescale, Bootstrap) and applying Rescale hoisting. This coarse-grained approach reduces the complexity of global optimization compared to operating directly on the entire polynomial sequence.
Polynomial-Level Optimization: After lowering ciphertext operations into their corresponding polynomial sequences, Recifhe performs fine-grained optimizations across ciphertext boundaries. Key techniques include:
- Common Subexpression Elimination (CSE): Removes redundant polynomial computations for identical inputs across different lowered sequences.
- Performance-Aware ModDown Hoisting: This is the core innovation. Recifhe identifies regions where multiple ModDown operations (which reduce the RNS basis from $PQ$ to $Q$ ) can be consolidated. Unlike previous fixed-algorithm approaches, Recifhe uses offline profiling to estimate the latency of operations at both the $Q$ and $PQ$ bases. It calculates the trade-off between the benefit of removing ModDown operations and the overhead of executing insensitive operations (like additions) on the heavier $PQ$ basis. Hoisting is applied only when the estimated latency benefit exceeds the overhead.
- Operation Fusion: Recifhe fuses adjacent operations (e.g., ModDown and Rescale) to cancel internal Number Theoretic Transform (NTT) and inverse NTT (iNTT) pairs, keeping polynomials in the evaluation domain. It utilizes invModDown to lift operands to the $PQ$ basis when necessary to enable fusion across intervening operations.
- Liveness-Driven Scheduling: To counteract the memory growth inherent in polynomial-level optimization (caused by extended lifetimes of intermediate values), Recifhe schedules operations to immediately follow their most recently defined operands. This shrinks live ranges and allows the reuse of buffers for dead values, mitigating memory pressure.

Key Contributions

Multi-Level Architecture: A novel compiler design that integrates global ciphertext-level optimizations with fine-grained polynomial-level optimizations, addressing the limitations of single-granularity approaches.
Dataflow-Adaptive Hoisting: A performance-aware ModDown hoisting algorithm that dynamically evaluates the profitability of transformations based on specific dataflows and operation latencies, avoiding the pitfalls of fixed-algorithm optimizations.
Memory Management: A liveness-driven scheduling mechanism that specifically targets the memory overhead introduced by polynomial-level optimizations, ensuring that performance gains do not come at the cost of excessive memory usage.
Comprehensive Optimization Suite: The integration of CSE, operation fusion, and basis-sensitive scheduling to eliminate redundant computations across ciphertext operation boundaries.

Results
Recifhe was evaluated on 12 benchmarks (including machine learning models like LeNet, ResNet, and VGG16) against two baselines: a ciphertext-level-only optimizer and the manually optimized Cheddar library.

Performance: Recifhe achieved a 1.25× speedup over the ciphertext-level-only baseline across all 12 benchmarks. Compared to the Cheddar baseline, it achieved a 1.36× speedup on the 9 benchmarks where Cheddar completed successfully. Notably, the Cheddar baseline slowed down on 3 benchmarks (averaging 0.92× the speed of the ciphertext-only baseline) due to unprofitable, unconditional optimizations.
Memory Footprint: Recifhe reduced memory consumption compared to Cheddar, achieving 0.93× the memory footprint of the Cheddar baseline and 1.14× that of the ciphertext-only baseline. In contrast, Cheddar failed to complete 3 benchmarks due to Out-of-Memory (OOM) errors caused by unmanaged live ranges.
Compile Time: The polynomial-level passes increased compile time, averaging 39.0% of the total compilation time (2.92× the geometric mean of the ciphertext-only baseline), with performance-aware hoisting and fusion accounting for 1.31% and 14.3% of the total time, respectively.

Significance
The paper claims that Recifhe demonstrates the necessity of multi-level optimization in FHE compilers. By moving beyond the ciphertext level, it successfully eliminates redundant polynomial computations that previous compilers and manual library optimizations missed. Crucially, it proves that polynomial-level optimizations can be applied effectively without incurring prohibitive memory costs or performance penalties, provided that transformations are guided by dataflow analysis and latency profiling rather than fixed heuristics. This work establishes a new standard for FHE compilation, offering a balanced approach that maximizes execution speed while managing the memory constraints inherent in complex polynomial operations.

Technical Summary: Recifhe – Ciphertext- and Polynomial-Level Optimization for Fully Homomorphic Encryption

More like this