HALO: Loop-aware Bootstrapping Management for Fully Homomorphic Encryption

Paper Title: HALO: Loop-aware Bootstrapping Management for Fully Homomorphic Encryption
Review Form: The Guardian

Summary

The authors introduce HALO, a compiler intended to automate and optimize bootstrapping for FHE programs containing loops, a notable limitation in prior work. The system first generates a "type-matched" loop by ensuring encryption status and levels of loop-carried variables are consistent across iterations, inserting bootstraps as needed for correctness. It then applies a series of optimizations: (1) packing multiple loop-carried variables into a single ciphertext to reduce the number of bootstraps, (2) partially unrolling short loops to better utilize the levels restored by bootstrapping, and (3) adjusting the target level of bootstrapping to match the consumption needs of the loop body, thereby reducing bootstrap latency. The authors evaluate HALO against their prior work, DaCapo, on seven machine learning benchmarks, claiming a 27% average execution speedup, alongside significant reductions in compilation time and code size.

Strengths

1. Problem Significance: The paper addresses a well-known and critical limitation in existing FHE compilers—the lack of native support for loops. Automating bootstrapping management within loops is a necessary step for making FHE practical for a broader class of algorithms.

2. Pragmatic Optimizations: The proposed optimizations (packing, unrolling, target level tuning) are sensible and directly target the primary overheads associated with naive bootstrapping in loops. The idea of reducing the bootstrap target level (Challenge B-3, page 5) is a particularly practical insight into the performance characteristics of the bootstrapping operation itself.

3. Compile-Time and Code-Size Improvements: The paper convincingly demonstrates that avoiding full loop unrolling leads to dramatic, order-of-magnitude reductions in compilation time and final code size (Table 6, page 10 and Table 7, page 11). This is a clear and undeniable benefit for developer productivity and resource management, especially for programs with a large number of iterations.

Weaknesses

1. The Baseline Comparison Is a Strawman: The central claim of a 27% performance speedup is predicated on a comparison with DaCapo, a compiler that is explicitly defined as lacking loop support and therefore must fully unroll the loop. This is not a fair or insightful comparison. Of course, a specialized loop-aware compiler has the potential to outperform a generic compiler forced to operate on a massive, unrolled block of straight-line code. The unrolled code presents an explosion of candidate points for bootstrapping, making optimization a much harder problem for the baseline system. The authors fail to justify why this is the appropriate state-of-the-art for this specific problem, rather than, for instance, a comparison against manually optimized loops which represent the practical alternative for an expert FHE programmer today.

2. Superficial Analysis of Performance Inconsistencies: The evaluation reveals that HALO is not universally superior. In the K-means benchmark (Figure 4e, page 10), DaCapo significantly outperforms HALO (by up to 12.4%). The paper dismisses this with a brief, unsubstantiated explanation: "DaCapo performs better than HALO because it optimizes the fully unrolled code... allowing the compiler to adapt the bootstrapping placement to the exact level of consumption." This is insufficient. A rigorous analysis would require a deep dive into the program structure of K-means, the specific bootstrapping decisions made by both compilers, and a clear, evidence-based explanation for why the unrolled approach is superior in this specific instance. Without this, the 27% average speedup figure appears to be a product of cherry-picked benchmarks that favor the authors' approach.

3. Insufficient Detail and Scrutiny of Optimization Heuristics: The description of the optimization strategies lacks depth. For example, "Level-aware Loop Unrolling" (Section 6.2, page 8) appears to be based on a simple heuristic comparing the multiplicative depth of the loop body (depth_used) to the maximum available depth (depth_limit). This seems overly simplistic and may not be robust. The paper does not discuss limitations, such as handling loops with internal control flow or more complex data dependencies that might complicate depth analysis. The novelty of these optimizations is also questionable, as packing and unrolling are well-known techniques; the contribution is their automation, but the sophistication of this automation is not clearly established.

4. Weak and Unsubstantiated Claims in the PCA Case Study: In the nested-loop case study (Section 7.4, page 11), the authors claim that for the (8,4) iteration count, DaCapo's performance degrades because its "filtering of the optimization space... filters out the better solution." This is a strong claim made without a shred of evidence. To substantiate this, the authors would need to show the set of candidate bootstrap points DaCapo considered, explain the filtering mechanism that led to a suboptimal choice, and demonstrate what the optimal choice was and why HALO's loop-based structure inherently finds it. As presented, it reads as a post-hoc justification for an observed result rather than a rigorous analysis.

5. Lack of Sensitivity Analysis: The entire evaluation is conducted using a single set of FHE parameters (Table 1, page 2). The performance trade-offs in FHE, particularly the cost of bootstrapping relative to other operations, are highly sensitive to the choice of parameters (e.g., security level, polynomial modulus degree, plaintext precision). The conclusions drawn in this paper may not hold under different parameter sets. A robust evaluation would demonstrate the impact of varying these parameters on the relative performance of HALO and the baseline.

Questions to Address In Rebuttal

1. Please justify the selection of "DaCapo on a fully unrolled loop" as the state-of-the-art baseline. Why is this a more valid comparison than comparing against a manually optimized FHE loop, which is what a practitioner would otherwise write?

2. Provide a detailed analysis of the K-means benchmark result (Figure 4e). What specific characteristics of this benchmark's computational graph allow the unrolled version to be optimized more effectively by DaCapo than HALO's loop-centric approach?

3. Regarding the PCA case study (Figure 5, Section 7.4), can you provide concrete evidence for the claim that DaCapo's heuristic "filters out the better solution"? Please detail the specific bootstrap insertion points considered and discarded by DaCapo that led to the observed performance degradation.

4. The loop unrolling strategy described in Section 6.2 appears to be based on a simple depth comparison. How does this heuristic handle loops with conditional branches or variable multiplicative depths per iteration? What are the precise limitations of this approach?

5. How would the performance advantage of HALO change if FHE parameters corresponding to a higher security level (e.g., 192-bit) were used, which would significantly alter the relative cost of bootstrapping? Please provide data or a well-reasoned argument on the sensitivity of your results to the core FHE parameters.

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper introduces HALO, a compiler for Fully Homomorphic Encryption (FHE) designed to address a critical, and largely unsolved, problem in the field: the efficient management of bootstrapping within programmatic loops. The authors correctly identify that prior state-of-the-art compilers, such as DaCapo, handle loops by fully unrolling them, leading to extreme inefficiencies in compilation time, code size, and an inability to support loops with dynamic iteration counts.

HALO's core contribution is a compilation strategy that treats loops as first-class citizens. It ensures correctness by matching the encryption status and noise levels of loop-carried variables across iterations. Furthermore, it introduces a suite of novel, loop-aware optimizations to mitigate the high cost of bootstrapping: (1) packing multiple loop-carried variables into a single ciphertext to reduce the number of bootstrap operations, (2) selectively unrolling short loops to better utilize the "recharged" levels post-bootstrapping, and (3) tuning the target level of bootstrapping to avoid unnecessary computational overhead. The empirical evaluation shows significant improvements over the unrolling-based approach, demonstrating a 27% average performance speedup in execution time, and, more dramatically, a geometric mean reduction of 209x in compilation time and 11x in code size.

Strengths

1. High Significance and Timeliness: The work addresses a fundamental bottleneck in the practical application of FHE. As the community moves from cryptographic primitives to building complex applications, the lack of robust support for control flow, particularly loops, has been a major barrier. HALO represents a conceptual leap from viewing FHE programs as static dataflow graphs (requiring full unrolling) to handling them as genuine, iterative programs. This is a crucial step towards making FHE programming more accessible and scalable.

2. Clear Problem Articulation: The authors do an excellent job in Section 3 ("Challenges," page 575) of distilling the core issues. The distinction between correctness challenges (type and level mismatches of loop-carried variables) and performance challenges (overhead from excessive or inefficient bootstrapping) is clear and compelling. The illustrative examples in Figures 2 and 3 effectively communicate the subtleties of the problem to a broader audience.

3. Elegant and Multi-faceted Solution: The proposed solution is not a single trick but a well-integrated set of techniques that address the identified challenges systematically.

   • The core idea of enforcing type and level consistency for loop-carried variables is a direct and necessary solution for correctness.
   • The optimization of packing loop-carried variables is particularly insightful. It correctly identifies that the number of bootstraps is a primary driver of overhead and provides a direct method to reduce it, transforming a per-variable cost into a single, shared cost.
   • The combination of level-aware unrolling and target-level tuning shows a sophisticated understanding of the performance trade-offs within the FHE execution model.

4. Strong Connection to the Broader Compiler Landscape: At its heart, this work is about applying classic compiler theory (data-flow analysis, loop-carried dependencies, loop optimizations) to the unique, resource-constrained domain of FHE. It successfully bridges these two fields, demonstrating how well-established compilation principles can be adapted to solve modern cryptographic challenges.

5. Impressive Empirical Results: The evaluation is thorough and the results are compelling. The comparison against DaCapo, the direct state-of-the-art, is the correct one. While the 27% execution speedup is significant, the orders-of-magnitude improvements in compilation time and code size are the most striking result. These metrics directly prove the unsustainability of the full-unrolling approach for any reasonably complex iterative program and validate HALO's methodology as the more viable path forward. The PCA nested-loop case study (Section 7.4, page 582) further strengthens the claim of generality.

Weaknesses

While the core contribution is strong, the paper could be strengthened by discussing the boundaries and limitations of the proposed approach.

1. Scope of Control Flow Support: The paper primarily focuses on for loops where the iteration count, even if large, is known or can be parameterized. The current design does not seem to accommodate more complex control flow, such as while loops that terminate based on a data-dependent condition or loops with early exits (break). These constructs are common in many iterative algorithms (e.g., convergence loops) and represent the next logical frontier for FHE compilers. Acknowledging this limitation and discussing the potential challenges (e.g., evaluating a condition on a ciphertext) would provide valuable context.

2. Generality of the Packing Optimization: The variable packing technique is a key strength, but its applicability may be constrained. The paper does not discuss the scenario where the number of loop-carried variables exceeds the packing capacity of a single ciphertext (determined by the polynomial degree N). A discussion on how HALO would handle such cases (e.g., creating multiple packed ciphertexts) and the performance implications thereof would make the analysis more complete.

3. Details of the Optimization Heuristics: The paper describes what optimizations are performed (e.g., unrolling, target level tuning) but provides limited insight into how the compiler decides when and how to apply them. For instance, how is the optimal unroll factor determined? Is there a cost model that weighs the benefit of utilizing more levels against the overhead of a larger loop body? While a full exploration is likely beyond the scope of one paper, a brief discussion of the decision-making logic would be beneficial.

Questions to Address In Rebuttal

1. Could the authors clarify the current limitations of HALO's loop analysis? Specifically, can it handle while loops or loops with conditional break statements? If not, what are the primary challenges to extending the framework to support such control flow structures?

2. Regarding the loop-carried variable packing optimization, how does HALO scale when the number of variables is too large to fit into a single ciphertext? Does it partition them into multiple packed ciphertexts, and what is the expected performance impact?

3. Could you elaborate on the decision-making process within the HALO compiler for applying the level-aware unrolling and target level tuning optimizations? Is this guided by a performance model, or is it based on a set of pre-defined heuristics?

Reviewer: The Innovator (Novelty Specialist)

Summary

This paper introduces HALO, a compiler for Fully Homomorphic Encryption (FHE) that provides, for the first time, automated bootstrapping management for programs containing loops without resorting to full loop unrolling. The central claim of novelty is this loop-aware compilation strategy. To achieve this, the authors propose several techniques: (1) a type-matching system to ensure correctness by unifying the encryption status and level of loop-carried variables across iterations; (2) a set of optimizations to reduce the high cost of bootstrapping within loops, namely packing multiple loop-carried variables into a single ciphertext to minimize the number of bootstrap operations, level-aware unrolling to better utilize the "level budget" granted by a bootstrap, and tuning the target level of the bootstrap operation to avoid unnecessary computational overhead. The authors evaluate HALO against a state-of-the-art FHE compiler (DaCapo) that relies on full unrolling, demonstrating significant improvements in compilation time and code size, as well as a notable performance speedup.

Strengths

The primary strength of this paper lies in its novel approach to a well-defined and critical problem in FHE usability.

1. Addressing a Fundamental Limitation: The prior art in FHE compilers, such as DaCapo [13] and HECO [59], is largely limited to programs with simple control flow or loops that can be fully unrolled. This severely restricts the complexity of programs that can be practically developed and compiled. HALO's core proposal—to generate a compact, single loop body that is valid for an arbitrary number of iterations—is a genuinely new and significant contribution to the field of FHE compilers. It moves the state-of-the-art from handling straight-line code (or what can be converted to it) to handling general iterative structures.

2. Novel Application of Existing Primitives for Optimization: While the constituent optimization ideas are inspired by well-known concepts, their application to the unique resource management problem of FHE loops is novel and insightful.

   • Packing Loop-Carried Variables (Section 4.2): Standard FHE schemes have long used packing to enable SIMD operations on data. However, applying this technique to aggregate multiple distinct loop-carried variables into a single ciphertext with the specific goal of reducing N bootstraps to one per iteration is a clever and previously unexplored optimization strategy in this context.
   • Level-Aware Unrolling (Section 6.2): Loop unrolling is a classic compiler optimization. HALO re-purposes it in a novel way: not for instruction-level parallelism, but as a tool to amortize the high fixed cost of bootstrapping. The heuristic of unrolling just enough to fully utilize the levels restored by a bootstrap is a new, domain-specific application of the technique tailored to FHE's unique execution model.
   • Bootstrap Target Level Tuning (Section 6.3): The observation that bootstrapping to a lower level is faster (Table 3) is known, but incorporating this as an automated compiler pass that analyzes the level consumption within the loop body to select an optimal, non-maximal target level appears to be a new contribution compared to the baseline established by DaCapo [13].

Weaknesses

From a novelty perspective, the weaknesses are less about flaws and more about the nature of the contribution.

1. Engineering Novelty over Foundational Novelty: The paper's contribution is primarily one of systems engineering and clever synthesis. The underlying primitives—the CKKS FHE scheme, bootstrapping, packing, and loop unrolling—are all pre-existing. The novelty lies in being the first to assemble and adapt these pieces to solve the specific problem of FHE loops. This is a valuable and non-trivial contribution, but it is not a new fundamental algorithm or cryptographic primitive.

2. Adaptation of Standard Compiler Theory: The correctness requirement of matching the "type" of loop-carried variables between iterations (Section 3.1) is an application of standard data-flow analysis principles found in any modern compiler textbook. The challenge and novelty here are not in the abstract concept but in defining the FHE-specific "type system" (i.e., encryption status and level) and building the analysis to handle it, which the paper correctly identifies.

Questions to Address In Rebuttal

1. The optimization of packing loop-carried variables to reduce bootstrap count is compelling. To solidify the claim of novelty, could the authors confirm if any prior work, perhaps in manual FHE program optimization or in different FHE compiler frameworks, has proposed or implemented a similar strategy for managing loop-carried state?

2. The paper contrasts its dynamic bootstrap target level tuning against DaCapo [13], which is claimed to use a fixed maximum level. While this establishes a delta against the most direct competitor, is this concept entirely new to the FHE space? Has the idea of selecting a lower bootstrap level to save latency been discussed in the context of other FHE libraries or optimization frameworks, even if not automated within a compiler?

3. The level-aware unrolling heuristic appears effective. Was this the first heuristic considered? The paper presents it as a solution to "wasted levels" (Challenge B-2, page 5). Did the authors explore alternative approaches to managing this waste, and if so, why was level-aware unrolling chosen as the most promising path? This would help clarify the design space and the novelty of the chosen solution.