Neo: Towards Efficient Fully Homomorphic Encryption Acceleration using Tensor Core

Reviewer: The Guardian

Summary

This paper proposes Neo, a framework for accelerating Fully Homomorphic Encryption (FHE) computations by mapping them onto the Tensor Core units found in modern NVIDIA GPUs. The core idea is to decompose the large integer polynomial multiplications at the heart of FHE into a series of smaller, fixed-precision matrix multiplications that are a perfect fit for the Tensor Core hardware. The authors present a "limb-interleaving" data layout strategy to manage the high-precision arithmetic and a "fragment-based" scheduling approach to handle polynomials that are larger than the Tensor Core's native dimensions. They claim this method achieves significant speedups (up to 7.8x) over existing CPU and GPU-based FHE libraries.

---

Strengths

The paper is founded on a clever and pragmatic observation that has the potential for significant real-world impact.

• Pragmatic Use of Existing Hardware: The core strength of this paper is its recognition that modern GPUs contain highly specialized, powerful compute units (Tensor Cores) that are currently underutilized by FHE workloads. The idea of re-purposing this existing, ubiquitous hardware for FHE acceleration, rather than designing a new ASIC, is a sound and practical approach.
• Clear Algorithmic Breakdown: The paper does an excellent job of systematically breaking down the complex problem of large polynomial multiplication into a sequence of smaller matrix multiplications that can be directly mapped to the Tensor Core's capabilities (Section 3, Pages 3-4). The mathematical formulation is clear and provides a solid foundation for the proposed mapping strategy.

---

Weaknesses

Despite the clever premise, the paper's conclusions are undermined by an incomplete analysis, questionable evaluation methodologies, and a failure to address critical, well-known challenges in GPU-based acceleration.

• Fundamentally Flawed Baseline Comparison: The headline performance claims are invalid because the comparison to the CPU baseline (Microsoft SEAL) is not equitable. The reported speedups are largely due to the massive difference in raw compute power and memory bandwidth between a high-end A100 GPU and a CPU. A rigorous evaluation would require comparing Neo not just to a CPU library, but to a state-of-the-art, highly-optimized GPU implementation that uses standard CUDA cores for the same FHE operations. Without this direct GPU-to-GPU comparison, it is impossible to isolate the true benefit of using Tensor Cores from the general benefit of using a GPU.
• Overhead of Data Reshaping is Ignored: The proposed "limb-interleaving" strategy (Section 4.1, Page 5) requires significant data reshaping and pre-processing to transform the polynomial coefficients into the specific matrix layout required by the Tensor Cores. This shuffling and re-ordering of data in GPU memory is not a "free" operation; it consumes memory bandwidth and execution cycles. The paper's performance model appears to completely ignore this overhead, which could be substantial and could significantly erode the claimed performance benefits. The analysis focuses only on the matrix multiplication itself, which is a classic flaw in accelerator research.
• Insufficient Analysis of Precision and Noise: The paper states that it uses a 64-bit representation (FP64) for its intermediate calculations to "guarantee the correctness" (Section 4.2, Page 6). This is a hand-wavy and insufficient analysis. FHE computations are notoriously sensitive to noise growth, and simply using a standard floating-point format does not automatically guarantee correctness. The paper lacks a rigorous error analysis that tracks the noise propagation through the proposed decomposition and mapping process. It is not proven that the results are cryptographically sound, only that they are numerically approximate.
• Scalability Claims are Unsubstantiated: The paper proposes a "fragment-based" scheduling method to handle large polynomials (Section 5, Page 7) but provides insufficient evidence of its efficiency. The evaluation is limited to a specific set of FHE parameters (Table 4, Page 10). It is unclear how the performance scales as the polynomial degree N and the ciphertext modulus Q grow to the very large values required for deep, complex FHE applications. The overhead of managing and scheduling a large number of fragments could easily overwhelm the benefits of using the Tensor Cores.

---

Questions to Address In Rebuttal

1. To provide a sound comparison, please evaluate Neo against a state-of-the-art GPU implementation of the same FHE scheme that uses standard CUDA cores and is optimized for the same A100 hardware. This is the only way to prove the specific benefit of using Tensor Cores.
2. Please provide a detailed performance breakdown that includes the overhead of the "limb-interleaving" data-reshaping step. What is the latency and memory bandwidth consumption of this pre-processing step, and how does it impact the end-to-end performance of a complete FHE operation?
3. Provide a rigorous cryptographic noise analysis. Show how the noise in the ciphertext propagates through your proposed decomposition, matrix multiplication, and reconstruction process, and prove that the final result remains below the failure threshold for all evaluated parameter sets.
4. To substantiate your scalability claims, please provide a detailed performance model and evaluation for much larger FHE parameter sets, demonstrating how the fragment scheduling overhead and memory pressure scale as the polynomial degree and modulus size increase significantly.

Reviewer: The Synthesizer (Contextual Analyst)

Summary

This paper introduces Neo, a novel framework for accelerating Fully Homomorphic Encryption (FHE) by leveraging the specialized Tensor Core units found in modern NVIDIA GPUs. The central idea is to bridge the gap between the world of large-integer polynomial arithmetic, which underpins FHE, and the world of high-performance, low-precision matrix multiplication, which is the native domain of Tensor Cores. Neo achieves this by presenting a clever algorithmic mapping: it decomposes the large polynomial multiplications into a series of smaller matrix-matrix multiplications that can be executed directly on the Tensor Core hardware. To manage the data flow and precision requirements, the authors propose a "limb-interleaving" data layout and a "fragment-based" scheduling strategy. This work effectively opens up a new pathway for FHE acceleration by re-purposing existing, powerful, and widely available hardware that was originally designed for AI workloads.

---

Strengths

This paper's primary strength is its elegant and pragmatic approach to a difficult problem, demonstrating a keen understanding of both the FHE domain and the underlying hardware landscape.

• A Brilliant Repurposing of Existing Hardware: The most significant contribution of this work is its clever recognition that the Tensor Cores, while designed for AI, are fundamentally high-performance matrix engines that can be repurposed for other domains. Instead of proposing a bespoke ASIC, which is costly and has a long design cycle, this paper provides a software-based solution that unlocks the immense computational power of existing, off-the-shelf hardware for FHE (Section 1, Page 2). This is a powerful and practical approach that has the potential for immediate, widespread impact. 💡
• Connecting Disparate Computational Domains: This work serves as a beautiful bridge between two traditionally separate fields: the high-level, abstract mathematics of lattice-based cryptography and the low-level, nitty-gritty details of GPU microarchitecture. By demonstrating how the Number Theoretic Transform (NTT), a cornerstone of FHE, can be algorithmically reframed as a series of matrix multiplications (Section 3, Pages 3-4), the paper provides a crucial Rosetta Stone that allows the FHE community to tap into the billions of dollars of R&D that have been invested in AI hardware.
• Enabling a New Class of GPU-Accelerated Cryptography: Prior work on GPU acceleration for FHE has largely focused on using the general-purpose CUDA cores. While effective, this approach often fails to utilize the GPU to its full potential, as the Tensor Cores sit idle. By specifically targeting the most powerful compute units on the chip, Neo paves the way for a new generation of GPU-accelerated cryptographic libraries that are far more efficient and performant. It opens up a new and fertile area of research for the high-performance computing and applied cryptography communities.

---

Weaknesses

While the core idea is powerful, the paper could be strengthened by broadening its focus from a proof-of-concept to a more robust, production-ready system.

• The Data Reshuffling Elephant in the Room: The proposed "limb-interleaving" strategy is a clever way to format the data for the Tensor Cores. However, this data shuffling itself has a performance cost. The paper focuses on the speedup of the core computation but spends less time analyzing the overhead of the data preparation and pre-processing steps. In many GPU workloads, data movement and marshalling can become a significant bottleneck, and a more detailed analysis of this overhead would provide a more complete performance picture.
• The Software Abstraction Layer: Neo provides the low-level "how-to" for mapping FHE onto Tensor Cores. The next critical step, which is not fully explored, is the software abstraction layer. For this technique to be widely adopted, it needs to be integrated into a high-level FHE library (like Microsoft SEAL) and exposed through a clean API. A discussion of the challenges in building this compiler and runtime layer—which would need to automatically handle the decomposition, scheduling, and data layout—would be a valuable addition.
• Beyond a Single GPU: The paper successfully demonstrates the potential of Neo on a single GPU. The natural next step is to consider how this approach scales to a multi-GPU or multi-node environment. As FHE applications grow in complexity, they will inevitably require the resources of a full server or cluster. A discussion of how Neo would interact with high-speed interconnects like NVLink and how the fragment-based scheduling could be extended to a distributed setting would be very interesting.

---

Questions to Address In Rebuttal

1. Your work brilliantly repurposes hardware designed for AI. Looking forward, do you envision future GPUs having features specifically designed to make this mapping even more efficient? For example, could a future generation of Tensor Cores have native support for modular arithmetic or more flexible data layout options?
2. The "limb-interleaving" strategy is key to your approach. How does the overhead of this data pre-processing scale as the FHE parameters (and thus the polynomial sizes) grow? Is there a point where the cost of data shuffling begins to diminish the benefits of using the Tensor Cores?
3. For this technique to have broad impact, it needs to be integrated into a user-friendly library. What do you see as the biggest challenges in building a compiler or runtime system that could automatically and optimally apply the Neo framework to an arbitrary FHE program? 🤔
4. How does the performance of Neo change with different generations of Tensor Cores (e.g., from Volta to Ampere to Hopper)? Does the growing power and complexity of the Tensor Cores open up new opportunities or create new bottlenecks for your approach?

Reviewer: The Innovator (Novelty Specialist)

Summary

This paper presents Neo, a framework for accelerating Fully Homomorphic Encryption (FHE) on modern GPUs. [cite_start]The core novelty claim is a new methodology for mapping the large-integer polynomial arithmetic central to FHE onto the fixed-precision, matrix-oriented Tensor Core units[cite: 1, 33]. [cite_start]This is achieved through two primary novel techniques: 1) A "limb-interleaving" data layout strategy that transforms polynomial coefficients into a matrix format suitable for the Tensor Cores [cite: 203, 206][cite_start], and 2) a "fragment-based" scheduling approach that decomposes large polynomial operations into a sequence of smaller matrix multiplications that fit the hardware's native dimensions[cite: 284]. [cite_start]The work claims this is the first implementation to accelerate the critical BConv and IP FHE kernels on Tensor Cores, offering a new pathway for FHE acceleration[cite: 146, 575].

---

Strengths

From a novelty standpoint, this paper's strength lies in its clever and non-obvious algorithmic mapping, which bridges two seemingly incompatible computational domains.

• [cite_start]Novel Algorithmic Transformation: The most significant "delta" of this work is the algorithmic transformation that reframes large-integer polynomial multiplication as a series of small, fixed-precision matrix multiplications[cite: 146, 575]. While using GPUs for FHE is not new, prior work has focused on using the general-purpose CUDA cores. This paper is the first to devise a concrete method for mapping these operations onto the highly specialized and architecturally rigid Tensor Cores. This conceptual leap—seeing a path from polynomial math to matrix math—is a significant and novel contribution. It unlocks a powerful, previously untapped computational resource for the FHE domain. 🧠
• [cite_start]Novel Data Layout and Scheduling: The "limb-interleaving" [cite: 203, 206] [cite_start]and "fragment-based" [cite: 284] techniques are direct and novel solutions to the two primary challenges of this mapping: precision and dimensionality. Standard FHE requires high-precision arithmetic, while Tensor Cores are low-precision. Standard FHE polynomials are very large, while Tensor Cores operate on small, fixed-size matrices. The proposed data layout and scheduling schemes are the novel "glue" that makes this mapping possible. They represent a new, domain-specific approach to data management for GPU-based computation.

---

Weaknesses

While the core mapping is novel, the work's claims of novelty do not extend to the underlying hardware or the performance gains themselves, which are a predictable consequence of the mapping.

• [cite_start]Performance Gain is a Consequence, Not a Novelty: The paper reports significant speedups over CPU and other GPU baselines[cite: 542]. However, the novelty of the work is the enabling of the Tensor Cores, not the speedup itself. It is not a novel discovery that a highly specialized, massively parallel matrix engine (the Tensor Core) is faster than a general-purpose CPU or even general-purpose CUDA cores for matrix-heavy workloads. The performance gain is an expected and logical consequence of the novel mapping, not a separate innovation.
• Relies Entirely on Existing Hardware: The novelty of this work is purely in the software and algorithmic domain. It proposes no new hardware and does not suggest any modifications to the existing GPU architecture. Its contribution is in finding a new and creative way to use hardware that already exists, which is valuable but limits the scope of the novelty to the mapping technique itself.
• Algorithmic Ancestry: While the specific application to FHE is new, the general concept of using matrix multiplication engines to perform other mathematical operations (like convolutions) has a long history in the field of high-performance computing. The novelty here is the specific, non-trivial adaptation of these principles to the unique mathematical structures of lattice-based cryptography, particularly the Number Theoretic Transform (NTT).

---

Questions to Address In Rebuttal

1. The core of your novelty is the algorithmic mapping of polynomials to matrices. Can you discuss any prior art in other domains (e.g., signal processing, scientific computing) that has used a similar "transform-and-dispatch" approach to map non-matrix problems onto specialized matrix hardware?
2. [cite_start]The "limb-interleaving" technique is presented as a novel data layout[cite: 203, 206]. How does this differ fundamentally from standard data-marshaling techniques used in high-performance libraries (e.g., cuFFT, cuBLAS) to prepare data for optimal hardware access?
3. [cite_start]Could the proposed fragment-based scheduling [cite: 284] be considered a domain-specific instance of a more general tiling or loop-nest optimization strategy? What is the core, novel insight in your scheduler that is unique to the FHE domain?
4. If NVIDIA were to introduce a future Tensor Core with native support for modular arithmetic or larger integer types, how much of the novelty of the Neo framework would remain? Does the contribution lie primarily in overcoming the limitations of current hardware, or is there a more fundamental, hardware-independent algorithmic novelty?