FAST:An FHE Accelerator for Scalable-parallelism with Tunable-bit

Reviewer: The Guardian

---

Summary

The paper proposes FAST, a novel hardware accelerator for Fully Homomorphic Encryption (FHE) based on the CKKS scheme. The central thesis is that existing accelerators are too rigid, relying on a single key-switching method (e.g., Hybrid) and failing to leverage recent cryptographic optimizations such as the gadget decomposition key-switching method (KLSS) and hoisting. To address this, the authors introduce a versatile framework, Aether-Hemera, to dynamically select the optimal key-switching method based on the ciphertext level. The core hardware innovation is a Tunable-Bit Multiplier (TBM) designed to efficiently execute both 36-bit operations (optimal for Hybrid) and 60-bit operations (optimal for KLSS). The authors claim their design achieves a significant 1.8x average speedup over state-of-the-art accelerators.

Strengths

1. Sound Motivation: The paper correctly identifies a critical gap in the FHE accelerator landscape. The observation that the computational trade-offs between different key-switching methods (Hybrid vs. KLSS) vary with ciphertext level (l) is insightful and provides a strong motivation for a more flexible hardware architecture.
2. Novel Architectural Concept: The idea of a tunable-precision datapath, embodied by the Tunable-Bit Multiplier (TBM), is a clever architectural response to the divergent computational requirements of modern FHE algorithms. Supporting both 36-bit and 60-bit operations within a unified multiplier is a non-trivial design contribution.
3. Analysis of Algorithmic Trade-offs: The analysis presented in Section 3, particularly in Figures 2 and 3, provides a valuable characterization of the performance landscape for different key-switching methods and the impact of hoisting. This analysis effectively grounds the hardware design choices in concrete algorithmic behavior.

Weaknesses

Despite its interesting premise, the paper suffers from several critical weaknesses related to its evaluation methodology, internal consistency, and substantiation of claims. These issues undermine the credibility of the reported performance improvements.

1. Questionable and Potentially Unfair Baselines: The primary performance comparison is against SHARP [20] and several enhanced variants (SHARPLM, SHARP8C, SHARPLM+8C) that the authors appear to have modeled rather than implemented. Footnote 2 on page 11 states, "We also model performance under large memory conditions by comparing the effects of reduced computational workload." This is not a substitute for a rigorous, cycle-accurate simulation of a modified baseline. It is highly likely that this "modeling" approach optimistically estimates the baseline's performance, thereby artificially inflating FAST's relative speedup. Similarly, the claim that SHARPLM "integrates direct hoisting technology" is not substantiated with implementation details. Without a fair and rigorously simulated baseline, the central performance claims of the paper are suspect.

2. Conflation of Algorithmic and Architectural Gains: The paper's core contribution is presented as a new architecture, yet a substantial portion of the performance gain stems from employing a superior algorithm (KLSS) that the baseline (SHARP) was never designed to support. The evaluation fails to disentangle these two effects. The "Efficiency Study" in Section 7.6 compares FAST (with TBM) to "FAST with a 36-bit ALU," which is still the authors' own architecture. A proper ablation study would compare FAST to a baseline like SHARP when both are limited to running the same algorithm (i.e., the Hybrid method). As it stands, it is impossible to determine how much of the speedup is due to the novel TBM and flexible architecture versus simply using a better algorithm.

3. Contradiction in On-Chip Memory Requirements: The authors claim in Section 5.6 (page 10) that the designed on-chip memory of 245MB is "enough to support the KLSS method." However, their own analysis in Figure 3b (page 5) clearly shows that the working set size for KLSS can reach nearly 295MB at the highest ciphertext levels. This is a direct contradiction. If FAST cannot support KLSS at the very levels where Figure 2a suggests it is most beneficial, the entire premise of the Aether-Hemera dynamic selection framework is compromised. The paper does not address how this memory shortfall is handled.

4. Vague Description of the Aether-Hemera Framework: The Aether analysis tool is described as "preprocessing on the server side" (Section 4.1.1, page 6) that takes an "FHE operation flow" to generate a configuration file. This description is superficial. It is unclear if this requires a full pre-simulation of the application or if it is a simple static analysis. Its ability to handle dynamic or data-dependent control flow is not discussed, limiting its generality. The complexity of managing two distinct sets of evaluation keys (for 36-bit and 60-bit moduli) and the potential hardware reconfiguration overheads are mentioned as challenges but are not adequately addressed in the description of Hemera's online management.

5. Unsupported Hardware Claims: The paper claims the TBM achieves its flexibility with "only 28% area overhead relative to conventional 60-bit multipliers" (Section 4.2, page 8). The definition of a "conventional" 60-bit multiplier is not provided; a fair comparison would be against a well-optimized, potentially composed, 60-bit modular multiplier, not necessarily a monolithic one. Furthermore, the assertion that "existing accelerators will struggle to integrate these capabilities" is a strong claim made without any supporting evidence or detailed reasoning.

Questions to Address In Rebuttal

1. Please provide a detailed methodology for how the enhanced SHARP baselines (SHARPLM, SHARP8C) were created. Was a cycle-accurate model of the SHARP architecture modified to include larger memory and support for hoisting, or was performance estimated by simply adjusting operation counts? The validity of the 1.8x speedup claim hinges on the fairness of this comparison.

2. Please address the apparent contradiction between the stated on-chip memory size of 245MB and the peak working set requirement of ~295MB for KLSS shown in your own Figure 3b. Does this memory limitation prevent the use of KLSS at high ciphertext levels? If so, how does this impact the effectiveness of the Aether-Hemera framework and the overall performance results?

3. To isolate the architectural contribution of FAST, can you provide performance data for your architecture against a baseline like SHARP when both systems are restricted to executing only the Hybrid key-switching method? This would provide a direct, apples-to-apples comparison of the hardware's efficiency.

4. Could you elaborate on the offline analysis process of the Aether tool? What are its computational complexity and limitations? Specifically, does it require a full trace or simulation of the target application, and how would it handle applications with non-static computation graphs?

5. Regarding the TBM's 28% area overhead claim, what specific design was used as the "conventional 60-bit multiplier" baseline? Please provide details on its implementation to justify the comparison.

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper presents FAST, a novel hardware accelerator for Fully Homomorphic Encryption (FHE) based on the CKKS scheme. The central contribution lies in its co-designed software/hardware architecture that dynamically adapts to the changing computational requirements of an FHE application. The authors' core insight is that different key-switching algorithms—specifically the traditional hybrid method and the more recent KLSS method—exhibit superior performance at different ciphertext levels. Furthermore, these methods have disparate precision requirements (36-bit for hybrid vs. 60-bit for KLSS).

To exploit this, FAST introduces two key innovations:

1. Aether-Hemera Framework: A software layer where "Aether" performs offline analysis to determine the optimal key-switching strategy (including the use of hoisting) at each stage of the computation, and "Hemera" manages the corresponding evaluation keys at runtime.
2. Tunable-Bit Multiplier (TBM): A versatile hardware multiplier unit that can be dynamically configured to perform either two 36-bit multiplications in parallel or a single 60-bit multiplication, thereby efficiently supporting both key-switching methods without the significant area overhead of dedicated datapaths.

By integrating these concepts, FAST is the first accelerator architecture, to my knowledge, to systematically support and switch between multiple state-of-the-art key-switching primitives within a single FHE program execution. The evaluation demonstrates a significant average speedup of 1.8x over existing state-of-the-art FHE accelerators.

Strengths

1. Excellent Core Insight and Motivation: The paper's primary strength is its foundational observation, clearly articulated in the Motivation section (Section 3, pages 4-6). The analysis presented in Figure 2, which shows the performance crossover between the hybrid and KLSS key-switching methods as a function of ciphertext level, is compelling. This insight elevates the work from being "just another accelerator" to one that addresses a fundamental, dynamic property of FHE computations. It correctly identifies that a one-size-fits-all hardware design is suboptimal.

2. Bridging Cryptographic Theory and Hardware Architecture: This work does an admirable job of connecting recent advances in cryptographic methods (KLSS, hoisting) with concrete hardware design. Many accelerator papers optimize for established, sometimes outdated, cryptographic primitives. By explicitly designing for the latest techniques described in papers like Kim et al. [22] and Chen et al. [10], the authors ensure their architecture is relevant and pushes the state-of-the-art forward. This is a crucial contribution to the community, demonstrating how architects must co-evolve their designs with the underlying algorithms.

3. Elegant Hardware/Software Co-Design: The proposed solution is not purely a hardware effort. The Aether-Hemera framework is a clever software abstraction that manages the complexity of the dynamic decision-making process. It allows the hardware (specifically the TBM) to be flexible but relatively simple, while the intricate logic of when to switch precision and algorithms is handled offline. This separation of concerns is a hallmark of good system design.

4. Novel and Practical Hardware Primitive (TBM): The Tunable-Bit Multiplier is an elegant solution to the multi-precision problem identified in Section 3.2. Instead of brute-forcing the issue with separate 36-bit and 60-bit datapaths, the TBM offers a reconfigurable unit that maximizes parallelism for the common 36-bit case while still efficiently supporting the demanding 60-bit case. This demonstrates a deep understanding of hardware design trade-offs.

Weaknesses

While the core idea is strong, the paper could be improved by further exploring the implications and limitations of its approach.

1. Generality of the Aether Analysis: The Aether tool is presented as a key enabler, but its inner workings and generality are not fully detailed. It seems to function as a profile-guided optimization tool. How dependent is this analysis on specific FHE parameter sets (e.g., ring degree N, initial modulus Q)? If an application or its security parameters change, does the entire analysis need to be re-run? A discussion on the robustness and potential overhead of this offline stage would strengthen the paper.

2. Sensitivity to On-Chip Memory: The design relies on a very large (245MB) on-chip memory to support the significant evaluation key storage requirements of KLSS and hoisting (as shown in Figure 3b). This is a major factor in the total chip area (Table 3). While the authors perform a sensitivity analysis in Figure 13, the discussion could be expanded. The current approach seems tailored for a high-end design point. It would be valuable to understand how the Aether framework's decisions and the overall performance would change under more constrained memory budgets (e.g., 64MB or 128MB), which might be more commercially viable.

3. Complexity of Key Management: The Hemera runtime component must manage multiple sets of evaluation keys for different algorithms and potentially different hoisting factors. While the paper states this is handled, the true complexity and potential for pipeline stalls or memory bank conflicts during key loading and switching are not deeply analyzed. A more detailed examination of the runtime overhead of this dynamic management would be beneficial.

Questions to Address In Rebuttal

1. Could the authors elaborate on the automation and generality of the Aether analysis tool? For a new FHE application not benchmarked in this paper, what is the process and computational cost required for Aether to generate the optimal execution plan? Is any manual intervention or application-specific tuning required?

2. The 245MB on-chip memory is substantial. Could you comment on the performance trade-offs if the memory is constrained to a more modest size, say 128MB? How would the Aether tool adapt its strategy, and what would be the anticipated performance degradation on a benchmark like bootstrapping? Would it simply fall back to using the hybrid method more often?

3. The core idea of dynamic algorithm selection is powerful. Have you considered extending this concept beyond key-switching? For example, could different NTT algorithms or base conversion strategies be dynamically selected depending on the computational context? This work seems to open a new avenue for FHE accelerator design, and I would be interested to hear your perspective on its broader applicability.

Reviewer: The Innovator (Novelty Specialist)

---

Summary

The authors present FAST, a hardware accelerator for the CKKS Fully Homomorphic Encryption (FHE) scheme. The paper's central claim to novelty rests on being the first hardware architecture to incorporate and dynamically manage multiple recent cryptographic optimizations that have, until now, primarily been explored in software. Specifically, the work claims novelty in three areas:

1. The co-integration and hardware support for two distinct key-switching methods: the traditional hybrid method and the more recent gadget decomposition (KLSS) method.
2. The creation of a software/hardware framework (Aether-Hemera) to analyze workload characteristics (e.g., ciphertext level) and dynamically select the optimal key-switching method during a single application's execution.
3. The design of a "Tunable-Bit Multiplier" (TBM) architecture capable of dynamically switching between performing dual 36-bit multiplications or a single 60-bit multiplication, thereby efficiently supporting the differing precision requirements of the two key-switching methods.

The core idea is not a new fundamental cryptographic primitive, but rather a novel system-level co-design that synthesizes existing, but disparate, software-level optimizations into a cohesive and reconfigurable hardware architecture.

---

Strengths

From the perspective of novelty, the paper's primary strengths are:

1. Novel Synthesis of Existing Art: The core contribution is the architectural synthesis of very recent cryptographic optimizations. The KLSS method (Kim et al., 2023) and hoisting techniques have been proposed to improve FHE performance on CPUs/GPUs, but prior accelerator designs (e.g., SHARP, ARK) have not incorporated them. FAST appears to be the first to build a custom microarchitecture specifically to exploit them. This synthesis is non-trivial and represents a tangible advancement.

2. Novel Problem Identification and Motivation: The analysis in Section 3.1 (page 5, Figure 2) is a key contribution in its own right. The observation that the computational advantage shifts between the hybrid and KLSS methods depending on the ciphertext level (l) is a crucial insight. This provides a strong, novel motivation for a dynamic, multi-method architecture, moving beyond the static "one-size-fits-all" approach of prior work.

3. Purpose-Built Reconfigurable Hardware: The Tunable-Bit Multiplier (TBM) presented in Section 4.2 (page 8) is a clever hardware solution to the problem identified. While reconfigurable or multi-precision arithmetic units are not fundamentally new concepts in digital design, the TBM is a purpose-built unit whose design is directly motivated by the specific precision dichotomy (36-bit vs. 60-bit) of the two targeted key-switching methods. Its novelty lies in its specific application and tight integration to solve a unique FHE acceleration challenge.

---

Weaknesses

My critique is focused on the precise boundaries of the novelty presented:

1. Contribution is Primarily in Synthesis, Not Invention: It must be stated clearly that the constituent parts of the proposed system are not new. The KLSS algorithm, hoisting, and Karatsuba-style multiplication (which the TBM is a variant of) are all pre-existing concepts. The paper's novelty rests entirely on being the first to combine them in a hardware accelerator. While this is a valid contribution, the paper could be more precise in delineating its system-level synthesis contribution from the underlying, previously-published algorithmic work.

2. Limited Scope of the Dynamic Framework: The Aether-Hemera framework is presented as a solution for choosing between the hybrid and KLSS methods. However, the work does not explore whether this framework represents a more general, extensible principle for FHE accelerator design. Is this a point solution for these two specific methods, or a paradigm that could incorporate future, as-yet-unknown FHE primitives and optimizations? The novelty would be significantly stronger if the latter were demonstrated or at least convincingly argued.

3. Complexity vs. Benefit Justification: The proposed architecture introduces significant complexity: a dual-method management framework, more intricate key management for two different key types, and a more complex multiplier unit with added control logic. While the authors show a notable performance gain (avg. 1.8x over SHARP), the performance-per-area gain is more modest (1.13x). This suggests that the novel techniques add nearly as much hardware cost as they provide in performance benefit. A deeper analysis on whether this trade-off is fundamentally advantageous across a wider range of parameters would strengthen the claim. For instance, how does this trade-off change if on-chip memory is more constrained?

---

Questions to Address In Rebuttal

1. The core novelty appears to be the system-level co-design of previously separate software optimizations. Beyond being "the first," what is the fundamental architectural insight or principle that future designers can learn from FAST? Is it simply "support more algorithms," or is there a deeper principle about reconfigurability in FHE that you are proposing?

2. Regarding the Tunable-Bit Multiplier (TBM): The use of three smaller multipliers to construct one larger multiplier is a well-known technique (e.g., Karatsuba). Please clarify how the TBM's design is novel beyond a direct hardware mapping of this principle to solve the specific 36/60-bit requirement. Was a broader design space of multi-precision units explored?

3. The Aether-Hemera framework makes decisions based on ciphertext level and hoisting opportunities. Could the authors elaborate on its extensibility? If a new key-switching algorithm with different precision requirements and performance characteristics were proposed next year, how much of the Aether-Hemera decision logic and the underlying FAST hardware would need to be redesigned? This speaks directly to the durability of the novel contribution.