HAWK: Fully Homomorphic Encryption Accelerator with Fixed-Word Key Decomposition Switching

---

Review Form

Reviewer: The Guardian (Adversarial Skeptic)

Summary

The authors present HAWK, a hardware accelerator for Fully Homomorphic Encryption (FHE) based on the CKKS scheme. The paper's primary assertion is that the recently proposed Key Decomposition Switching (KDS) method [36], despite its superior asymptotic complexity, is impractical for existing fixed-word-length hardware accelerators. The authors identify challenges including high computational cost at small word lengths, substantial memory expansion of the evaluation key, and the need for a hardware-unfriendly rounding operation. To address these, they propose the Fixed-Word KDS (FW-KDS) method, which unifies the operational word length. They augment this with several optimizations, including a "Half-RConv" strategy to reduce ring conversions in H-IDFT and a novel rounding circuit claimed to be error-free. The resulting HAWK architecture is presented as an evolution of the SHARP accelerator, reportedly achieving up to a 1.45x performance improvement with a 4% area increase.

Strengths

1. Problem Identification: The paper provides a thorough and valuable analysis of the practical implementation costs of the KDS method in Section 3. The empirical data presented in Figures 3 and 4 (page 5) effectively illustrates the performance crossover points with HKS and the significant evaluation key bloat, which are non-obvious from the original theoretical presentation of KDS. This analysis is a solid contribution in its own right.
2. Clear Baseline: The work is evaluated against SHARP [34], a state-of-the-art FHE accelerator. Using a strong, recent, and relevant baseline allows for a more credible assessment of the claimed performance improvements.
3. Multi-faceted Approach: The authors address the identified problems from multiple angles: algorithmic modification (FW-KDS), procedural optimization (Half-RConv), and microarchitectural design (the new rounding circuit). This demonstrates a comprehensive approach to co-design.

Weaknesses

My primary concerns with this submission revolve around the framing of the core problem, the attribution of performance gains, and the rigor of key claims.

1. Potentially Circular Problem Framing: The central premise is that KDS is "incompatible" with fixed-word accelerators. However, the theoretical advantage of KDS stems precisely from its ability to use a converted modulus H composed of larger primes h_i than the ciphertext modulus primes q_i. The proposed "Fixed-Word" KDS forces wd(h_i) = wd(q_i), constraining KDS to an operating point that the authors' own analysis in Figure 3 (page 5) demonstrates is computationally inferior to HKS. The paper then presents optimizations to mitigate the performance loss of this self-imposed constraint. This framing is questionable; it appears less like an inherent flaw in KDS and more like a problem created by forcing the algorithm into an unsuitable architectural model.

2. Conflated and Misleading Attribution of Performance Gains: The headline claim is a 1.45x speedup, and the paper is titled and framed around "Fixed-Word Key Decomposition Switching." However, the ablation study in Figure 12(b) (page 12) tells a different story. The transition from the HKS baseline to using FW-KDS yields a performance improvement of approximately 1.11x-1.15x. The subsequent application of the "Half-RConv" technique provides the remaining, and more substantial, jump to the final ~1.45x performance. This suggests that Half-RConv is the dominant optimization, yet it is presented as a secondary improvement. The paper's focus on FW-KDS as the main contributor is therefore misleading.

3. Insufficient Justification for the "Error-Free" Rounding Circuit: In Section 6.3 (page 11), the authors claim their new rounding circuit "completely eliminates the rounding computational error." This is a very strong claim. The proof relies on Lemma 6.1, which requires the rounding offset to be less than 1/4. The authors assert that their modulus selection H > 4 * 2 * B_d guarantees this condition. However, the derivation in Section 7.7 (page 14) that q_i > dnum * 2N is sufficient to meet this larger bound is terse. A more rigorous and formal proof is required to substantiate the claim that this condition holds universally for all valid CKKS parameter sets and that the rounding is truly "error-free" in all cases, rather than just having an error bounded below the precision of the system.

4. Ambiguous Cost Analysis: The abstract claims a "4% area increase," which seems modest for the added capabilities and memory. Table 2 (page 12) shows the on-chip memory capacity of HAWK is 212 MB (192+20), while for SHARP it is 198 MB (180+18). This constitutes a 7.1% increase in on-chip memory. Given that on-chip SRAM is a dominant contributor to the area and power budget of FHE accelerators, it is unclear how a 7.1% increase in memory results in only a 4.25% (186.4/178.8) increase in total chip area. The authors must provide a detailed area breakdown of the logic components (NTTU, EWU, EBConvU) and memory for both HAWK and their SHARP baseline to validate this claim. Without it, the 4% figure is not credible.

Questions to Address In Rebuttal

The authors must provide clear and concise answers to the following questions:

1. Your core premise is the impracticality of KDS on fixed-word hardware. Please justify why forcing KDS into a suboptimal, fixed-word configuration (FW-KDS) and then optimizing it is a superior approach to designing a more flexible architecture that could properly leverage the variable-word-length nature of the original KDS method. Is the problem truly with KDS, or with the inflexibility of the target architecture?
2. According to your ablation study (Figure 12(b)), the Half-RConv optimization appears to contribute more to the final performance gain than the FW-KDS method. Please justify the paper's title and narrative focus on FW-KDS. Provide a performance breakdown for the bootstrapping workload that precisely isolates the speedup from FW-KDS alone versus Half-RConv alone.
3. Regarding the rounding circuit in Section 6.3, please provide a formal proof that your modulus selection strategy guarantees that the rounding offset | [A]_H / H | is strictly less than 1/4 for all valid and secure CKKS parameter configurations, not just the specific ones tested in this work.
4. Please reconcile the discrepancy between the 7.1% increase in on-chip memory capacity and the claimed 4% total area increase over the SHARP baseline. Provide a detailed area breakdown for all major components (functional units, memory, NoC, etc.) for both your HAWK design and the SHARP baseline to substantiate your overall area claim.

---

Review Form

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper presents HAWK, an FHE accelerator designed around a novel algorithm-hardware co-design principle. The work's central focus is to make the recent and theoretically promising Key Decomposition Switching (KDS) algorithm practical for hardware implementation. The authors first provide an insightful analysis (Section 3) identifying the key barriers to deploying KDS on existing fixed-word FHE accelerators: (1) its requirement for divergent word-lengths, (2) a significant inflation of evaluation key memory, and (3) a hardware-unfriendly rounding operation.

The core contribution is a new method, Fixed-Word Key Decomposition Switching (FW-KDS), which elegantly resolves the primary challenge by constructing the temporary conversion modulus H from the set of existing RNS primes q_i. This unifies the operational word length, making KDS compatible with established accelerator designs. Building on this foundation, the authors introduce further algorithmic and architectural co-optimizations, including a technique to halve the expensive ring conversions in bootstrapping (Half-RConv) and a novel, hardware-efficient circuit for the exact base conversion that completely eliminates rounding errors. The resulting system, HAWK, demonstrates up to a 1.45x performance improvement over a state-of-the-art baseline with a negligible area increase, effectively bridging the gap between a new cryptographic theory and its practical hardware realization.

Strengths

1. Excellent Problem Identification and Positioning: The paper's primary strength lies in its clear identification of a critical gap in the field. The KDS algorithm [36] was a recent advance from the cryptography community with superior asymptotic complexity, yet its practical utility for the hardware architecture community was unproven and, as the authors show, deeply problematic. This work serves as an essential bridge between these two domains. The analysis in Section 3 is one of the most valuable parts of the paper, as it clearly articulates the practical hurdles that a purely theoretical analysis would miss.

2. Elegant and Impactful Core Idea: The proposed FW-KDS method is a beautifully simple and effective solution to the main challenge of divergent word lengths. The idea of reusing existing RNS primes for the converted modulus H (Section 4.1) is not a brute-force fix but an insightful co-design choice that unlocks a cascade of subsequent benefits, including reduced computational complexity (Section 4.3) and smaller memory footprints (Section 4.4). This represents a significant conceptual advance over the original KDS formulation for any fixed-word implementation.

3. Strong System-Level Co-Design: This work goes far beyond a simple algorithmic tweak. The authors have considered the full system impact of their choices. The "Half-RConv" optimization (Section 5.1.1) is a clever insight into the dataflow of iterative bootstrapping routines, showing a deep understanding of the application structure. Furthermore, the development of a new hardware-friendly rounding method (Section 6.3, Figure 11e) demonstrates a commitment to solving the problem across the entire stack, from algorithm to circuit level. This holistic approach is commendable.

4. Opening a New Design Space: Prior to this work, FHE accelerator research had largely converged on optimizing the Hybrid Key-Switching (HKS) method. HAWK fundamentally challenges this consensus by demonstrating a practical and superior alternative. It effectively provides a blueprint for a new generation of FHE accelerators built on a more efficient primitive. This has the potential to shift the focus of future research and unlock further performance gains.

Weaknesses

While the paper is strong, its context and implications could be further enriched.

1. Under-explored Trade-off Characterization: The paper pragmatically settles on a hybrid strategy: using FW-KDS for high and medium levels and falling back to HKS for low levels. This is a sound engineering decision, but the underlying trade-offs could be more deeply explored. Figure 14b provides a glimpse, but a more explicit characterization of the performance/memory crossover point between HKS and FW-KDS as a function of key FHE parameters (e.g., polynomial degree N, number of levels L, RNS prime size log q_i) would be invaluable for future designers seeking to apply this work.

2. Interaction with Orthogonal Optimizations: The FHE literature contains other powerful optimization techniques, most notably hoisting [27], which trades a significant increase in memory for a large reduction in H-(I)DFT computation. The authors rightly follow the path of recent accelerators like ARK [35] and SHARP [34] in forgoing hoisting to manage on-chip memory. However, the paper would be more complete with a short discussion on how FW-KDS might interact with hoisting in a different design context (e.g., a GPU-based system with vast memory). Does the reduced key size of FW-KDS make hoisting more tenable? Or do its benefits primarily apply to memory-constrained systems?

3. Generalizability Beyond CKKS: The discussion in Section 8.2 touches upon adapting the method to other RLWE-based schemes like BGV and BFV. This is a crucial point for assessing the work's broad impact. This section could be strengthened by briefly explaining why the key-switching mechanisms are similar enough to expect this adaptation to be successful, thereby giving the reader more confidence in the claimed generalizability.

Questions to Address In Rebuttal

1. The proposed exact rounding method in Section 6.3 is a novel and important contribution for making KDS practical. Could you quantify the area and/or power savings of your proposed circuit (Figure 11e) compared to the "traditional" high-precision implementation (Figure 11d) it replaces? This would more concretely establish the benefit of this specific optimization.

2. Regarding the dual-mode HKS/FW-KDS strategy, could the authors elaborate on the crossover point where FW-KDS becomes more efficient than HKS? How sensitive is this point to FHE parameters like N, L, or the decomposition base alpha? A clearer characterization of this trade-off space would be valuable.

3. This work successfully demonstrates a new, superior key-switching primitive for accelerators, which likely shifts the overall system bottlenecks. After applying your (M)FW-KDS optimizations, what becomes the next dominant bottleneck in the bootstrapping process? Is it still the (I)NTT operations, or has the problem shifted more towards data movement or other element-wise operations within the EWU?

---

Review Form

Reviewer: The Innovator (Novelty Specialist)

Summary

This paper presents HAWK, a hardware accelerator for Fully Homomorphic Encryption (FHE) that centers on a novel adaptation of the recently proposed Key Decomposition Switching (KDS) algorithm. The authors identify that the original KDS method is incompatible with mainstream fixed-word-length FHE accelerators due to its requirement for large, variable-width moduli (hi) to achieve its theoretical efficiency.

The central claim of novelty is the Fixed-Word Key Decomposition Switching (FW-KDS) method. This method modifies the KDS algorithm by constructing the temporary conversion modulus H using primes from the existing FHE parameter set (qi), thereby forcing all operations into a single, fixed word length. The paper further proposes two supporting contributions: a hardware-friendly integer-based method for the exact rounding operation required by KDS, and a dataflow optimization named Half-RConv to reduce redundant computations during bootstrapping. The authors claim this is the first work to successfully deploy the KDS method in a fixed-word hardware accelerator.

Strengths

1. Core Contribution's Novelty: The primary contribution, FW-KDS, appears to be genuinely novel. The KDS algorithm (Kim et al., CRYPTO 2023 [36]) is very recent, and to my knowledge, no prior work has systematically analyzed its hardware implementation challenges, let alone proposed a concrete algorithmic modification to resolve the critical word-length incompatibility issue. While the problem of fixed vs. variable word length is well-understood in the FHE accelerator community (e.g., SHARP [34]), the authors' proposed solution—constructing the temporary modulus H from the existing prime set D (Section 4.1, page 6)—is a simple but clever algorithmic trick that directly addresses this problem. This is a clear and novel advancement over the prior art.

2. Novelty in Supporting Contributions: The paper contains secondary contributions that are also novel in their specific context:

   • Hardware-Friendly Rounding (Section 6.3, page 11): The standard method for exact base conversion relies on high-precision arithmetic that is hostile to hardware. The authors replace this with a technique based on Lemma 6.1, which maps the problem to a fixed-point multiplication and bit truncation. While using fixed-point tricks to implement rounding is a known concept in DSP, its application to solve the specific ExactBConv problem from Halevi et al. [24] within an FHE accelerator is a new and valuable piece of algorithm-hardware co-design. It eliminates a significant implementation barrier for KDS.
   • Half-RConv Optimization (Section 5.1.1, page 8): This dataflow optimization, which defers the ring conversion for one of the key-switch outputs, is a novel observation specific to the iterative structure of bootstrapping's giant-step when combined with a KDS-like method. It arises directly from the introduction of the temporary ring RH, a feature absent in prior HKS-based accelerators. Therefore, this optimization is a novel contribution in the context of accelerating KDS.

3. Systematic Problem Formulation: The paper does an excellent job of deconstructing the KDS algorithm and identifying its practical weaknesses for hardware (Section 3, pages 4-6). This clear motivation, which precedes the solution, establishes that the authors are not just porting an algorithm but are thoughtfully re-engineering it based on a deep understanding of hardware constraints.

Weaknesses

1. Incremental Nature of the Core Idea: While novel, the core idea of FW-KDS is ultimately an engineering compromise born of a hardware constraint. The authors' own analysis (Figure 3, page 5) clearly shows that their proposed FW-KDS (with wd(hi) forced to 36 bits) is computationally inferior to the original KDS algorithm running at its optimal, larger word length (e.g., 64 bits). The novelty lies in making KDS practical for fixed-word hardware, but it does so by sacrificing some of the algorithm's intrinsic asymptotic advantage. The paper should be more upfront that FW-KDS is a "hardware-constrained KDS" rather than an unequivocally superior version.

2. Limited Scope of Novelty for Rounding Technique: The mathematical basis for the rounding optimization (Lemma 6.1, page 11) is a known principle in number theory and fixed-point arithmetic: if a value is known to be very close to an integer, its integer part can be found efficiently. The contribution is the application of this principle, not the invention of it. The framing could be more precise to reflect this.

3. The Delta Over Prior Art is Primarily an Integration Effort: The paper's main achievement is integrating the ideas of KDS into a state-of-the-art accelerator architecture template (largely derived from SHARP [34]). The architectural changes themselves (e.g., the EBConvU) are direct consequences of supporting the new algorithm, rather than fundamental architectural innovations. The novelty is therefore more algorithmic and co-design-focused than purely architectural.

Questions to Address In Rebuttal

1. The fundamental premise of FW-KDS is the constraint of a fixed-word architecture. How does the performance of HAWK using FW-KDS compare to a hypothetical, albeit more complex, accelerator designed with native support for multiple word lengths (e.g., 36-bit and 64-bit ALUs) that could execute the original KDS algorithm optimally? This would help quantify the performance cost of the fixed-word design choice.

2. The proposed rounding method relies on the condition H > 4 * 2Bd. In Section 7.7 (page 14), you argue this condition is easily met. Can you provide a more rigorous analysis? Are there any FHE parameter sets for different security levels (e.g., 192-bit) where this constraint becomes difficult to satisfy or forces a sub-optimal choice for the modulus H, thereby negatively impacting performance?

3. The Half-RConv optimization is presented as a key contribution. Could the authors clarify if the novelty lies in the observation that this specific dataflow is amenable to optimization, or if the technique of deferring basis conversion in this manner is itself a fundamentally new concept?