HALO: Loop-aware Bootstrapping Management for Fully Homomorphic Encryption

Seonyoung Cheon, Yongwoo Lee, Hoyun Youm, Dongkwan Kim, Sungwoo Yun, Kunmo Jeong and 2 others

Fully homomorphic encryption lets a server compute directly on encrypted data, but each encrypted value has a finite budget of multiplications before it must be refreshed by a slow operation called bootstrapping — and deciding where to place those refreshes is a punishing manual chore; a recent compiler automated it but only by fully unrolling loops, which explodes for large or unknown iteration counts; this paper (Yonsei) builds HALO, the first compiler that manages bootstrapping inside a rolled loop, matching the encryption state across iterations and adding three loop-aware optimizations, running 27 percent faster while compiling 200-plus times faster and producing 11 times smaller code.

The argument in one glance

Problem

Encrypted values run out of multiplications, and refreshing them is brutally expensive

Fully homomorphic encryption lets a server compute on data it cannot read: it can add and multiply encrypted values and hand back an encrypted result, which is a dream for privacy in cloud computing, finance, and healthcare. The catch is a hidden budget. Each ciphertext carries a level, and every multiplication spends some of it; when the level reaches zero, the value can no longer be multiplied. The only way to replenish it is bootstrapping, an operation that restores the level to its maximum — and bootstrapping is by far the slowest operation in the scheme, dominating runtime. So a programmer must place bootstrapping just right: too little and a value underflows and the computation breaks, too much or in the wrong spot and performance collapses. Doing this by hand, across a whole program, is a heavy and error-prone burden, which is exactly why people want a compiler to place bootstrapping automatically.
What people did

Automate bootstrapping placement by fully unrolling the loops

A recent compiler, DaCapo, does automate bootstrapping placement, and it handles loops the only simple way it can: by fully unrolling them into a long straight-line sequence, then placing bootstrapping across that flat program as if there were no loop at all.
Why it fell short

Full unrolling cannot handle real loops

Full unrolling only works when the iteration count is known at compile time and small. Many real programs — regression, iterative training — loop a number of times that is not known until run time, which cannot be unrolled at all. And even when the count is known, unrolling a large loop produces an enormous flat program that is slow to compile and bloats the code. Worse, inside a loop the cost of bootstrapping is multiplied by every iteration, so placing it well matters more here than anywhere, yet the rolled loop has its own constraint the flat view ignores: a value carried from one iteration to the next must return in exactly the same encrypted state it started in.
This paper's idea

Manage bootstrapping inside a rolled loop, with loop-aware optimizations

HALO is the first compiler that places and optimizes bootstrapping inside a loop without unrolling it. First it makes the loop legal: it matches the encryption status and level of every loop-carried value between the loop entry and the loop back-edge, so each value returns in the same state it began — a type-matched loop. Then it cuts the bootstrapping cost with three loop-aware optimizations: pack several loop-carried values into one ciphertext so a single bootstrapping serves them all, unroll a short body just enough to stop wasting levels, and lower each bootstrapping target level to the minimum needed to shorten its latency.

Why this problem is worth solving

The reason bootstrapping placement is a first-class problem is that it sits on top of a resource that is both finite and constantly draining.

In the RNS-CKKS scheme that HALO targets, a ciphertext is represented by a number of residue polynomials, and that number is its level — effectively how many more multiplications it can undergo. Each multiplication requires a rescaling that consumes a level, so a chain of multiplications steadily drains the budget until, at level zero, the value can no longer be multiplied and the computation would fail. Bootstrapping is the operation that recovers the level, lifting a depleted ciphertext back up to the maximum so computation can continue; it is what lets FHE run programs deeper than the initial level allows. But bootstrapping is enormously expensive, the longest-running operation in the scheme by a wide margin, so it cannot be sprinkled freely. The programmer, or the compiler, must decide exactly where to insert it: enough to prevent any value from underflowing, but no more, and at points that minimize its total cost. That decision is the whole game, and it is what makes automating bootstrapping placement valuable.

Loops turn this from a placement puzzle into a correctness problem, because a value that lives across iterations must keep a stable encrypted identity.

A loop-carried variable is one whose value in each iteration depends on the previous iteration, like an accumulator in a regression. In FHE this is uniquely tricky, because a ciphertext is not just a value but a value at a particular encryption status — plaintext or ciphertext — and a particular level. The operations placed inside the loop body are compiled once and then executed every iteration, so they assume the loop-carried ciphertext arrives in a fixed state each time. But multiplication in the body changes the level, and mixing plain and cipher operands can change the status, so without care a value would come back at the end of an iteration in a different state than it started, and the statically compiled body would be applied to the wrong kind of input on the next pass. To run a loop correctly, then, every loop-carried value must be returned to the same encryption status and the same level it had at the loop entry — a consistency requirement across iterations that straight-line code never has to satisfy, and that full unrolling sidesteps only by refusing to keep the loop a loop.

What people did before, and where it broke

Place bootstrapping by hand. Have the FHE programmer reason about levels across the whole program and insert bootstrapping manually. Where it broke. It is a heavy, error-prone burden, and hand placement often lands in suboptimal spots, giving poor performance; getting it wrong causes level underflow and a broken computation.
Automate parameter management without bootstrapping. Use an FHE compiler that analyzes and manages ciphertext levels but does not insert bootstrapping. Where it broke. Without bootstrapping, the program cannot exceed the multiplication depth allowed by the initial level, so these compilers are confined to small applications and cannot run deep computations at all.
Automate bootstrapping, but only for straight-line code (DaCapo). Add automatic bootstrapping placement, handling loops by fully unrolling them into flat code. Where it broke. Full unrolling is impossible for loops whose iteration count is unknown until run time, and for large known counts it produces a huge flat program that is very slow to compile and bloats code size; it also throws away the loop structure that makes loop-aware optimization possible.
Unroll and then optimize the flat result. Rely on ordinary straight-line optimizations after unrolling to reduce the bootstrapping cost. Where it broke. The per-iteration amplification of bootstrapping cost, and the special constraint that loop-carried values must return in a consistent state, are properties of the loop; once the loop is gone they cannot be reasoned about, so the biggest loop-specific savings are unavailable.
The gap. No compiler managed bootstrapping inside a real, rolled loop — matching the encryption state of loop-carried values across iterations for correctness, and exploiting the loop structure to minimize the per-iteration bootstrapping cost — which is what programs with dynamic or large loops actually need.

How HALO works

Making a rolled FHE loop legal, then cheap

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Keep the loop a loop, and make it legal by matching state across iterations. The prior approach only handled loops by destroying them: unroll into flat code so there is no loop-carried constraint left to satisfy. HALO refuses that trade and instead confronts the constraint head-on. It observes that a loop is correct in FHE only if every value carried from one iteration to the next returns in exactly the encryption status and level it started with, because the loop body is compiled once and reused each pass. So HALO matches those types — using loop peeling to handle the first iteration’s differences and placing bootstrapping to restore levels — turning an arbitrary loop into a type-matched loop that is safe to run rolled. Automating the tedious, correctness-critical management of a scarce encryption resource so the programmer does not have to reason about it by hand is the same service the scale-management compiler work covered elsewhere on this site provides, taking on the bookkeeping of a finite FHE quantity that is painful and dangerous to track manually. Keeping the loop rolled is also what avoids the compile-time and code-size explosion of unrolling, letting the compiler finish over two hundred times faster and emit code an order of magnitude smaller.

Treat the loop structure as an optimization target, not an obstacle. Once the loop is legal, HALO exploits the very structure unrolling threw away. Inside a loop, bootstrapping runs once per iteration, so shaving it pays off multiplied by the trip count — and the loop form is what lets HALO see and shave it. Its three optimizations are all loop-aware: pack the loop-carried variables into one ciphertext so a single bootstrapping covers them all, unroll a short body just enough that a full-level refresh is not wasted on a body that barely uses its levels, and lower each bootstrapping to the smallest target level the downstream code needs. Reasoning about and transforming loops as first-class structures to cut their dominant cost, rather than flattening them away, is the same discipline the nested-loop compilation work covered elsewhere on this site is built on, where preserving and analyzing the loop nest is precisely what enables the transformations that make it efficient. Together these give a 2.39 times improvement over a merely type-matched loop, which is the correctness baseline with no optimization.

Pack many values into one ciphertext, because the expensive operation is per-ciphertext. The single largest lever is packing. Bootstrapping’s cost attaches to a ciphertext, not to how many logical variables that ciphertext holds, and RNS-CKKS ciphertexts already hold many slots in SIMD fashion. So if a loop carries several variables — a benchmark may carry nine — bootstrapping each one separately means paying the dominant cost many times per iteration. HALO instead packs the loop-carried variables into a single ciphertext, so one bootstrapping refreshes all of them at once, collapsing many of the most expensive operations into one. Exploiting the fact that an encrypted value is really a wide vector, and co-locating many quantities in one ciphertext so a single costly operation amortizes across all of them, is the same packing strategy the encrypted-arithmetic vectorizing-compiler work covered elsewhere on this site relies on, arranging computation to make the most of every slot in a ciphertext rather than wasting the vector on one value.

Following a training loop through HALO

Compiling a regression loop with unknown iteration count

A trace, from the paper, of how HALO makes a loop-carrying FHE program correct and fast without unrolling it.

Step 1 of 5

Find the loop-carried type mismatches

The loop carries an accumulator and other variables that are multiplied each iteration. HALO detects that after one pass the accumulator level has dropped, and that some variable has changed between plaintext and ciphertext status, so its state at the loop back-edge does not match its state at the loop entry.

Statically placing the body operations would then apply them to the wrong kind of input on the next iteration, so the loop as written is incorrect in FHE.

Why it works

Type-matching makes a rolled FHE loop correct. A loop body compiled once assumes each carried value arrives in a fixed state, but multiplications and plain-cipher mixing change level and status → but peeling and placed bootstrapping restore every loop-carried value to its entry status and level → so the loop is legal without unrolling, which is what lets dynamic-count loops run at all.
Keeping the loop rolled avoids the unrolling blowup. Fully unrolling a large or unknown loop is impossible or produces a giant flat program → but managing bootstrapping inside the rolled loop keeps the code small → so HALO compiles about 209 times faster and emits up to 11 times less code than the unrolling compiler.
Packing amortizes the dominant cost across many variables. Bootstrapping cost is per ciphertext and a loop may carry many variables → but packing them into one ciphertext lets a single bootstrapping refresh them all → so the number of expensive bootstrappings per iteration drops sharply.
Right-sizing unroll and target level stops waste. A full-level bootstrapping in a short body leaves levels unused, and a high target level costs more latency than needed → but unrolling just enough to consume the levels and lowering the target level to what downstream code requires removes both wastes → so each bootstrapping does exactly the work needed and no more.
Loop-aware optimization compounds over iterations. Every bootstrapping saved is saved on every iteration → but only the loop form exposes the per-iteration structure to optimize → so the three loop-aware optimizations together yield a 2.39 times speedup over the correctness-only type-matched baseline.

What it costs (trade-offs and scope)

It targets one scheme and a compiler stack. HALO is built for RNS-CKKS, the approximate-arithmetic FHE scheme suited to machine learning, on an MLIR-based compiler with a Python frontend; its techniques are tied to that setting, and other FHE schemes with different level and bootstrapping semantics would need their own treatment.
Type-matching adds its own bootstrapping and peeling. Making the loop legal requires inserting bootstrapping and peeling iterations to reconcile states, which is overhead the optimizations then have to overcome; the 2.39 times gain is measured against this type-matched baseline precisely because the baseline itself already pays for correctness.
The optimizations are heuristic trade-offs. Level-aware unrolling trades some code growth for fewer wasted levels, packing assumes the loop-carried variables fit and benefit from sharing a ciphertext, and target-level tuning depends on knowing what downstream code needs; these are sound in the cases shown but are balances, not universal wins, and an adversarial loop could blunt them.
Correctness rests on the analysis being right. The whole approach depends on correctly identifying every loop-carried value’s status and level and restoring them; an imprecise analysis would either break correctness or force conservative, costlier placement, so the guarantees are only as strong as the type-matching analysis.
Evaluation is seven machine-learning programs. The results come from seven programs with flat and nested loops of various iteration counts against the state-of-the-art unrolling compiler; this is a solid demonstration on the intended workloads, but not a broad study across many applications, schemes, or hardware backends.

The evaluation

Handling a loop in an FHE program

Property	Manual placement	Automate by full unrolling	HALO
Loops with run-time-unknown counts
Correctness of loop-carried values
Bootstrapping cost in the loop
Compilation time and code size	n/a
Runtime versus the unrolling compiler	Varies

From the paper's evaluation on seven machine-learning programs with flat and nested loops against DaCapo, which places bootstrapping on fully unrolled loops. HALO is the first compiler to manage bootstrapping inside a rolled loop; the loop-aware optimizations contribute a 2.39-times speedup over the correctness-only type-matched loop.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The contribution is concrete and well scoped: HALO is the first FHE compiler to place and optimize bootstrapping inside a loop without unrolling it, which is what makes loops with run-time-unknown or large iteration counts possible at all. It does this in two moves — a type-matching pass that restores every loop-carried value to its entry encryption status and level so a rolled loop is correct, and three loop-aware optimizations (packing loop-carried variables into one ciphertext, unrolling a short body just enough to avoid wasted levels, and lowering each bootstrapping’s target level) that cut the dominant cost. The reported gains are a 27 percent runtime speedup over the state-of-the-art unrolling compiler, a 2.39 times speedup from the optimizations over the correctness baseline, and roughly 209 times faster compilation with up to 11 times smaller code from keeping the loop rolled. Read that within its scope: it is specific to RNS-CKKS on an MLIR stack, the optimizations are heuristic balances, correctness depends on the type-matching analysis being precise, and the evaluation is seven machine-learning programs. Within those bounds it closes a real gap that had kept FHE compilers from handling ordinary looping code.

Background

Why FHE, and why its cost is the whole story

It helps to see why researchers push so hard on one expensive operation. Fully homomorphic encryption is close to a holy grail for privacy: it lets you hand a server your encrypted data, have it run a computation, and get back an encrypted result the server never could read, which would let hospitals, banks, and clouds compute on sensitive data without ever exposing it. The reason it is not everywhere already is cost — FHE operations are orders of magnitude slower than their plaintext counterparts, and bootstrapping is the most expensive of all, so the practicality of any FHE application hinges almost entirely on how much bootstrapping it must do and how cheaply. Machine learning makes this acute, because models are deep and iterative, burning through levels quickly and looping many times, so the bootstrapping bill dominates. That reality, where making privacy-preserving computation usable is chiefly a matter of driving down the overhead of the encrypted operations, is the same pressure the end-to-end private-inference systems work covered elsewhere on this site operates under, engineering the whole pipeline so that encrypted machine learning is fast enough to be worth running. HALO attacks that bill from the compiler: by managing bootstrapping intelligently inside loops, it removes cost that programmers otherwise pay on every iteration.

If you remember only three things

1. Fully homomorphic encryption computes on encrypted data, but each ciphertext has a finite level that multiplications consume, and refreshing a depleted value requires bootstrapping — the scheme most expensive operation — so bootstrapping must be placed carefully to avoid both underflow and waste; the one compiler that automated this handled loops only by fully unrolling them, which is impossible for run-time-unknown iteration counts and explosively expensive for large ones.
2. HALO is the first compiler to manage bootstrapping inside a rolled loop. For correctness it builds a type-matched loop, using loop peeling and placed bootstrapping to restore every loop-carried value to the same encryption status (plain or cipher) and the same level it had at loop entry, since the loop body is compiled once and reused each iteration. For performance it adds three loop-aware optimizations: pack loop-carried variables into a single ciphertext so one bootstrapping refreshes them all, unroll a short body just enough to stop wasting levels, and lower each bootstrapping target level to the minimum needed (bootstrapping latency grows with target level).
3. On seven machine-learning programs with flat and nested loops, HALO runs 27 percent faster than the state-of-the-art unrolling compiler and its optimizations give a 2.39 times speedup over the correctness-only type-matched loop, while keeping the loop rolled makes compilation about 209 times faster and code up to 11 times smaller. It is specific to RNS-CKKS on an MLIR stack, its optimizations are heuristic balances, and correctness depends on the type-matching analysis.

Check yourself

Check your understanding

1. Why does an FHE program need bootstrapping, and why is placing it hard?
2. Why could the prior compiler not handle real loops, and what does HALO do instead?
3. What is the single largest optimization HALO uses to cut bootstrapping cost in a loop?
4. What were HALO's results and what are its limits?

Sources

The paper is “HALO: Loop-aware Bootstrapping Management for Fully Homomorphic Encryption” by Seonyoung Cheon, Yongwoo Lee, Hoyun Youm, Dongkwan Kim, Sungwoo Yun, Kunmo Jeong (Yonsei University), Dongyoon Lee (Stony Brook University), and Hanjun Kim (Yonsei University), published at ASPLOS 2025 (Volume 1), DOI 10.1145/3669940.3707275.

This explainer is written from the full text of the authors’ copy of the paper. Everything above comes from the paper’s own sections: the introduction and background on the RNS-CKKS scheme (ciphertext levels consumed by multiplication, the finite level budget, and bootstrapping as the level-restoring but most expensive operation, with the evaluation’s maximum level after bootstrapping); the motivation that prior compilers either omit bootstrapping (limiting them to small programs) or, in DaCapo’s case, support only simple control flow by fully unrolling loops, and that no FHE compiler supported loops with dynamic iteration counts; the challenge that loop-carried ciphertexts must keep a consistent encryption status and level across iterations because the statically compiled loop body is reused each iteration (with the paper’s Challenge A-1 status-mismatch and A-2 level-mismatch examples, and Challenge B-1 on bootstrapping overhead amplified by iteration count and unused levels); HALO’s type-matching via loop peeling and bootstrapping placement to build a type-matched loop; the three bootstrapping-aware optimizations (packing loop-carried variables into a single ciphertext, level-aware unrolling of short bodies to avoid wasted levels, and target-level tuning given that bootstrap latency is proportional to target level); the implementation on MLIR with a Python frontend; and the evaluation on seven machine-learning programs with flat and nested loops, reporting a 27 percent speedup over DaCapo, a 2.39 times geometric-average improvement from the loop optimizations over a type-matched baseline, and geometric-mean reductions of 209.12 times in compilation time and up to 11.0 times in code size.