GPU Acceleration of Sparse Fully Homomorphic Encrypted DNNs Lara D’Agata1 , Carlos Agulló-Domingo2 , Óscar Vera-López2 , Kaustubh Shivdikar4 , Ardhi W. B. Yudha4 , Ferhat Yaman4 , David Kaeli3 , José L. Abellán2 , Ian Colbert4 , José Cano1 University of Glasgow, UK1 University of Murcia, Spain2 Northeastern University, USA3 AMD4
arXiv:2604.11659v1 [cs.CR] 13 Apr 2026
Abstract Fully homomorphic encryption (FHE) has recently attracted significant attention as both a cryptographic primitive and a systems challenge. Given the latest advances in accelerated computing, FHE presents a promising opportunity for progress, with applications ranging from machine learning to information security. We target the most computationally intensive operation in deep neural networks from a hardware perspective, matrix multiplication (matmul), and adapt it for execution on AMD GPUs. We propose a new optimized method that improves the runtime and complexity of ciphertext matmul by using FIDESlib, a recent open-source FHE library designed specifically for GPUs. By exploiting sparsity in both operands, our sparse matmul implementation outperforms its CPU counterpart by up to 3.0× and reduces the time complexity from cubic to semi-linear, demonstrating an improvement over existing FHE matmul implementations. Keywords: Fully Homomorphic Encryption, DNN Acceleration, Secure Computation, Sparse Matrix Multiplication.
1
Introduction
Fully homomorphic encryption (FHE) allows arbitrary computations on encrypted data without the need for decryption, generating the same result as operations on plaintexts [15], and therefore holds significant promise for secure data processing in privacy-preserving computing. This process is outlined in Figure 1, where in a system with FHE support, a request sent over the internet is processed while still encrypted, meaning the only encryption and decryption performed are within the private trusted environment. Being in ciphertext form, the data is difficult to operate on as it does not always conform to standard operation requirements [27]; encrypted data can be much larger than plaintext data, as FHE computations involve very large polynomials. For instance, achieving a 128-bit security level could mean that 𝑛 = 217 and 𝑙 = 35, implying a total ciphertext size of roughly 73.4 MB. Since most hardware platforms have a cache of around 40-50 MB, the ciphertext itself would be too large to fit within the cache during an FHE operation [1]. If we also consider the key switching operation keys, with each occupying hundreds of MB, the only possibility of performing FHE operations on a modern hardware platform is through many frequent accesses to main memory. Given the
Figure 1. Visualization of a request to a third-party cloud environment with and without FHE; with FHE, data remains encrypted throughout processing. large size of ciphertexts, it also follows that the computational resources it takes to perform operations on this type of data is very large in terms of both time and space. When multiplying square matrices using FHE, the runtime can be 106 × higher compared to a multiplication with unencrypted (plaintext) data [14]. FHE schemes such as BGV [6] and CKKS [9] have made strides in balancing encryption complexity with computational efficiency, but despite their advancements, these schemes all face scalability challenges due to the complexity of their core operations. This computational burden poses a barrier to the widespread adoption of FHE schemes, especially in time-sensitive applications. Recently conducted experiments attempt to address the bottlenecks of matrix multiplication (matmul) in FHE [3, 14, 25, 26, 31, 32], where the problem of accelerating this process is addressed either through algorithmic improvements, such as the exploitation of sparsity, or through the creation of dedicated hardware. Sparse matrix-matrix multiplication (SpMSpM) in FHE, particularly with the CKKS scheme, faces several practical limitations. Homomorphic multiplications
D’Agata et al.
introduce noise that accumulates throughout the computation. Since SpMSpM involves many multiply-accumulate operations, noise can grow rapidly, potentially requiring expensive bootstrapping to maintain correctness [19]. Moreover, CKKS arithmetic introduces approximation errors, which can also accumulate across many operations [9]. The state-of-the-art (SoTA) FHE SpMSpM approaches are limited by a few core weaknesses, including rotation and keyswitching dominance, poor sparsity exploitation under packing constraints, and memory-bound execution. Even with algorithmic improvements, ciphertext rotations and rescaling dominate costs. Sparsity is difficult to leverage efficiently because SIMD (Single Instruction, Multiple Data) packing forces structured data layouts that introduce padding and redundant operations. Dedicated hardware reduces latency but is constrained by massive ciphertext sizes and memory traffic. A GPU implementation would address many of these issues, as it would benefit from massive parallelism for independent ciphertext operations, high memory bandwidth for large polynomial buffers, and efficient batched Number Theoretic Transform (NTT) acceleration, significantly reducing rotation-heavy SpMSpM latency. In this paper, we aim to address the most computationally intensive deep neural network (DNN) operation, matmul [16, 18, 24], and devise a more efficient version of current implementations by exploiting sparsity. DNNs combined with sparsity have become a recent trend in FHE acceleration, particularly on GPUs, because they align well with both homomorphic computation and parallel hardware. DNN inference primarily consists of matmul operations, which map naturally to SIMD-style packed operations in schemes such as CKKS. These operations rely heavily on polynomial arithmetic and number-theoretic transforms, which GPUs can efficiently accelerate due to their support for parallelism [29]. Sparsity further reduces the number of costly ciphertextciphertext multiplications, thus lowering computation time, memory usage, and noise growth [14]. To the best of our knowledge, our new implementation represents the first FHE SpMSpM tailored for GPU usage. The contributions of this paper are as follows:
• A new optimized method for encrypted matrix-matrix multiplication that exploits sparsity in both operands, implemented specifically for GPUs; • A comparison of the runtime performance of the proposed approach with naïve and SoTA solutions on multiple high-performance AMD GPUs; • A comparison of our GPU implementation against a CPU baseline built with OpenFHE [4], a widely used FHE library for CPUs. Our approach achieves exponential speedups over a naïve dense implementation and delivers approximately 2.5× to 3× performance improvements compared to the CPU-based baseline.
2
Background & Related Work
2.1
CKKS
Matrix multiplication for machine learning typically involves floating-point values and requires a large number of operations, particularly additions and multiplications, which makes efficiency and noise management critical. Given that CKKS [9] supports ciphertext packing, this dramatically reduces the number of ciphertexts and homomorphic operations required during a matmul. Although capable of packing ciphertexts, other schemes such as BFV [12] and BGV [6] are constrained by integer-only computation and are more susceptible to rapid noise growth and larger ciphertext sizes when dealing with real-valued or high-precision data. Moreover, CKKS is specifically designed for computations on real or complex numbers using approximate arithmetic, which is closely aligned with the needs of many machine learning, signal processing, and numerical computing applications. One of the distinguishing features of CKKS is its trade-off between accuracy and computational efficiency, due to its use of approximation encoding. It employs techniques such as rescaling to control noise growth [9], ensuring computations remain feasible within the scheme’s precision limits: this process adds complexity as the depth of computations increases. Unlike exact FHE schemes, CKKS does not guarantee bit-perfect correctness, but this trade-off is acceptable for many practical uses requiring real-number computations. Therefore, CKKS is especially suitable for applications such as machine learning, data analytics, and scientific computations, where inexact floating-point operations are standard. 2.2
FIDESlib
To implement our sparsity-exploiting algorithm, we use FIDESlib [2], a new open-source FHE library built for working with CKKS-encrypted data on GPUs. The general software architecture of existing libraries inherently sacrifices cutting-edge performance in favor of generality, due to the many abstraction layers needed for such flexibility [2]. However, FIDESlib designs software architectures tailored to specific GPU architectures to enhance performance. Most SoTA GPU-compatible CKKS libraries are not open-source [13, 22], making FIDESlib the first openly available library built for this purpose. Moreover, we use a new HIP-compatible version of FIDESlib which makes it possible to test the algorithm on AMD GPUs. 2.3
Sparsity in FHE
When working with large matrices, especially in high dimensional problems such as deep learning, scientific computing, and graph analytics, both memory usage and computational cost become major bottlenecks. In general, sparse processing addresses this challenge by storing and operating only on non-zero values (NZVs), thereby avoiding unnecessary arithmetic and reducing memory traffic. This improves cache
GPU Acceleration of Sparse Fully Homomorphic Encrypted DNNs
dense-sparse multiplications and do not address the fully sparse-sparse setting of the operation. A recent study [10] proposes a new CSR-based method for handling matrix sparsity for communications in the encrypted domain, which shows promising advancements in the acceleration of FHE operations but does not investigate the effects of sparsity on matrix multiplication. Figure 2. Example of a matrix represented in the CSR sparsity representation format. utilization, reduces I/O pressure and the overall runtime compared to dense representations. Common efficient sparse formats include compressed sparse row (CSR), compressed sparse column (CSC), and block-based formats, which balance storage overhead and access efficiency depending on the access pattern. An example of CSR in shown in Figure 2. In the context of FHE, sparsity becomes even more important due to ciphertext expansion. After encoding and encryption in CKKS, a single plaintext value is transformed into a large polynomial ciphertext, leading to significantly increased memory and bandwidth requirements. Consequently, dense encrypted matrices quickly become impractical to store and process. To mitigate this, SIMD-style packing strategies group multiple values into a single ciphertext, enabling parallel slot-wise computation. Combining such packing techniques with sparse representations reduces the number of ciphertext-ciphertext multiplications and rotations, improving memory efficiency and making GPU-accelerated FHE matmul more scalable. By decreasing space requirements, the proposed implementation enables FHE schemes to process larger datasets, making privacy-preserving computing more scalable and cost-effective [1]. Our research is based on continuing our previous work in exploiting unstructured sparsity for matmul operations [14], where we implemented a new sparsity-aware SpMSpM algorithm and compared it with other state-of-the-art FHE matmul implementations. By targeting unstructured sparsity, we were able to more accurately reflect the nature of data encountered in applications such as recommendation systems, graph processing, or natural language processing. This is particularly relevant for accelerating DNNs employing ReLU activations, which frequently induce high levels of unstructured activation sparsity [20]. We found our solution to be more efficient compared to others, being one of the first to exploit sparsity for FHE matmul. Other prior efforts to incorporate sparsity into FHE matmul have typically imposed notable constraints. For instance, some approaches restrict sparsity to linear systems of the form 𝐴𝑥 = 𝑏, where 𝐴 is required to be strictly diagonally dominant [8]. Subsequent works attempt support for general sparse matrix multiplication [7, 11]; however, they do not provide a detailed analysis of how sparsity impacts runtime performance. Moreover, these schemes are limited to
2.4 FHE on GPUs A key motivation for using a GPU is the potential alignment between its architecture and the demands of FHE computation. FHE operations generally exhibit low arithmetic intensity but benefit from massive parallelism, a profile that CPUs may handle less efficiently due to their more limited threadlevel parallelism and memory bandwidth. GPUs can address both constraints by exposing large numbers of compute cores and providing higher memory bandwidth to sustain the data movement these workloads require. Our library is designed to exploit both properties, with the goal of achieving throughput that would be difficult to match on a CPU. Substantial research has explored GPU acceleration and hardware-aware optimizations for FHE. Libraries such as HEonGPU [32] demonstrate promising throughput improvements but lack full support for essential operations such as bootstrapping. Other works investigate microarchitectural GPU extensions and locality-aware scheduling to better support FHE workloads [3, 26, 31], or investigate GPUoptimized sparsity representation formats [21, 30]. Together, these studies highlight that, despite the progress made, there are remaining challenges in achieving efficient, scalable FHE, particularly for sparse linear algebra operations. By implementing our sparse FHE matrix multiplication method on top of FIDESlib, we directly address this gap by combining the throughput advantages of GPU-accelerated CKKS primitives with a sparsity-aware computation strategy, enabling scalable and practically efficient encrypted sparse matmul for GPUs.
3
Proposed Method
We now present our new GPU-optimized matmul implementation using a hybrid CSR (row-wise) and CSC (column-wise) representation. Unlike prior SoTA SpMSpM approaches in FHE, our method exploits complementary sparsity layouts to improve memory locality, reduce redundant rotations, and increase parallel efficiency on bandwidth-intensive accelerators. As demonstrated in Section 4, this design achieves superior performance compared to existing implementations. Key innovation: our method deliberately pairs row-wise and column-wise formats, enabling structured access to NZVs while minimizing ciphertext movement and rotation overhead. By ensuring that the required elements from both operands are pre-aligned within the sparse structure, we can significantly improve cache utilization and reduce key
D’Agata et al.
Algorithm 1 Method for multiplying two 𝑁 × 𝑁 matrices in CSR and CSC formats. 1: for 𝑖 = 0 to N do 2: for 𝑗 = 0 to N do 3: 𝑎_𝑠𝑡𝑎𝑟𝑡 ← 𝑖𝑛𝑑𝑝𝑡𝑟 𝐴 [𝑖 ], 𝑎_𝑒𝑛𝑑 ← 𝑖𝑛𝑑𝑝𝑡𝑟 𝐴 [𝑖 + 1] 4: 𝑏_𝑠𝑡𝑎𝑟𝑡 ← 𝑖𝑛𝑑𝑝𝑡𝑟 𝐵 [ 𝑗 ], 𝑏_𝑒𝑛𝑑 ← 𝑖𝑛𝑑𝑝𝑡𝑟 𝐵 [ 𝑗 + 1] 5: 𝑎_𝑝𝑜𝑠 ← 𝑎_𝑠𝑡𝑎𝑟𝑡 , 𝑏_𝑝𝑜𝑠 ← 𝑏_𝑠𝑡𝑎𝑟𝑡 6: while 𝑎_𝑝𝑜𝑠 < 𝑎_𝑒𝑛𝑑 and 𝑏_𝑝𝑜𝑠 < 𝑏_𝑒𝑛𝑑 do 7: 𝑎_𝑐𝑜𝑙 ← 𝑖𝑛𝑑𝑖𝑐𝑒𝑠𝐴 [𝑎_𝑝𝑜𝑠 ], 𝑏_𝑟𝑜𝑤 ← 𝑖𝑛𝑑𝑖𝑐𝑒𝑠𝐵 [𝑏_𝑝𝑜𝑠 ] 8: if 𝑎_𝑐𝑜𝑙 = 𝑏_𝑟𝑜𝑤 then 9: 𝑣𝐴 ← 𝑐𝑡𝑥𝑡𝐴 , 𝑣𝐵 ← 𝑐𝑡𝑥𝑡𝐵 10: 𝑚𝑖𝑛_𝑝𝑜𝑠 ← 𝑎_𝑝𝑜𝑠 11: if 𝑎_𝑝𝑜𝑠 < 𝑏_𝑝𝑜𝑠 then 12: 𝑣𝐵 ← EvalRotate(𝑣𝐵, 𝑏_𝑝𝑜𝑠 − 𝑎_𝑝𝑜𝑠 ) 13: 𝑚𝑖𝑛_𝑝𝑜𝑠 ← 𝑎_𝑝𝑜𝑠 14: else if 𝑏_𝑝𝑜𝑠 < 𝑎_𝑝𝑜𝑠 then 15: 𝑣𝐴 ← EvalRotate(𝑣𝐴, 𝑎_𝑝𝑜𝑠 − 𝑏_𝑝𝑜𝑠 ) 16: 𝑚𝑖𝑛_𝑝𝑜𝑠 ← 𝑏_𝑝𝑜𝑠 17: FHE_SpMSpM(𝑣𝐴, 𝑣𝐵) 18: 𝑎_𝑝𝑜𝑠 + +, 𝑏_𝑝𝑜𝑠 + + 19: else if 𝑎_𝑐𝑜𝑙 < 𝑏_𝑟𝑜𝑤 then 20: 𝑎_𝑝𝑜𝑠 + + 21: else 22: 𝑏_𝑝𝑜𝑠 + +
switching pressure on the GPU. It is important to note that our implementation performs fully encrypted ciphertextciphertext matmul, whereas most existing FHE SpMSpM systems assume one operand is plaintext. By supporting encrypted-encrypted multiplication, our method enables stronger privacy guarantees compared to plaintext multiplications, making our method well suited for application domains such as secure multi-party computation, privacypreserving model training, and fully encrypted graph neural network layers, where both operands must remain confidential throughout execution. Algorithm 1 shows our method for multiplying two encrypted 𝑁 × 𝑁 matrices, represented in CSR and CSC format respectively. Storing the LHS matrix in a row-wise format and the RHS matrix column-wise offers significant performance and memory advantages, as the layout aligns well with how the matmul process works, especially for algorithms designed to operate efficiently on sparse data [23]. It makes the row-column pairing for dot products more efficient, as the necessary data from both matrices can be accessed quickly without scanning irrelevant zeros. This format pairing also supports better memory locality and cache efficiency. Access patterns become more predictable and localized, reducing memory access overhead. It also avoids the need to transpose either matrix during computation, which is expensive for large matrices. After being loaded at the start, all ciphertexts stay on the GPU, which we leverage by doing all server-side CKKS operations there: this transfer time is only accounted twice at runtime. Therefore, parallelism in FIDESlib is not directly exposed as it is internal to the limb partitions which the ciphertexts end up using.
3.1
SpMSpM in FHE
The SpMSpM flow is detailed in Algorithm 2 and visualized in Figure 3. For each row-column pair: • Alignment: We identify the indices of the target NZVs and rotate one (shown in Algorithm 1). Then we perform the ciphertext-ciphertext multiplication. • Isolation: After multiplication, we apply a plaintext mask to the product. This isolates the specific resulting value within the ciphertext. • Maintenance: We perform the necessary relinearization and rescaling. • Accumulation: The isolated product is rotated to its target coordinate in the result matrix and added. Because of the masking step, this addition safely updates the result matrix without corrupting existing slots. 3.2
Managing FHE constraints and overheads
While the CSR and CSC layouts enable efficient traversal, the opacity of FHE prevents dynamic zero-skipping, which introduces a trade-off between structural privacy and performance. 3.2.1 Metadata Transparency and Security Trade-offs. Since the matrix values are encrypted into a ciphertext object, it is impossible to inspect its contents or execute conditional logic on it. As a result, the computation cannot dynamically skip zero entries unless some structural information about the matrix is available in plaintext [14]. To efficiently exploit sparsity, certain metadata, such as index positions, row pointers, or sparsity masks, must therefore remain unencrypted. This allows us to determine which ciphertext multiplications are necessary without decrypting the underlying values: only the sparsity pattern is exposed, while all numerical entries remain encrypted. For many privacy-preserving DNN inference settings, revealing structural sparsity (e.g., pruned model weights) is acceptable. However, in stricter privacy scenarios, such as when inputs use one-hot encodings, the sparsity pattern itself may leak sensitive information, since the position of nonzeros can reveal the input directly. In cases where exposing sparsity metadata is unacceptable, the server can instead rely on known plaintext model sparsity while keeping all input structure encrypted. This preserves full input privacy but limits the ability to exploit sparsity in both operands, potentially increasing inference time compared to fully sparse-aware multiplication. 3.2.2 Mitigating overhead from intensive operations. When dealing with ciphertexts, it is impossible to retrieve an element at a given index due to the encrypted nature of the object. Therefore, the only way to gain access to a given element within a ciphertext is to use the rotation operation, which shifts the values within the ciphertext by a given amount. This is a distinct feature of FHE computations and
GPU Acceleration of Sparse Fully Homomorphic Encrypted DNNs
Figure 3. Overview of SIMD operations used for the FHE CKKS matmul computation, with example value matrices A and B. The encrypted vectors are represented using a blue outline, the ellipses (...) represent the ciphertext padding. is very time consuming [5], so our goal is to reduce the number of rotations as much as possible. Algorithm 1 checks the positions within the ciphertexts of the two NZVs that we want to multiply: instead of rotating both ciphertexts to the base position, only one of them is rotated to match the other. Moreover, When the position in both ciphertexts is the same, it performs no rotations and multiplies the ciphertexts as they are. In this way, we perform up to two less rotations per matching NZV pair compared to a naïve multiplication [14]. This is similar to the number of rotations in SoTA encrypted matmul methods such as Halevi-Shoup [17] and BSGS [28]. All encoded ciphertexts in CKKS must have a scale factor Δ. The multiplication of two ciphertexts results in the product having a scaling factor of Δ2 . The scaling factor must be reduced to Δ (or very close to it) before the end of the operation, or the scaling factor will eventually grow too much and allow the ciphertext modulus to overflow [1]. This is known as the Rescale operation and if not performed after every multiplication will result in decryption failure. After multiplying two ciphertexts, the result will be encrypted under a larger key 𝑠𝑘 2 instead of the original 𝑠𝑘. To ensure that the product of the multiplication will be decryptable, we require a key switch operation after each multiplication which encrypts the result back under the original secret key 𝑠𝑘. This procedure is more commonly known as relinearization. 3.3
Optimized GPU formats: VCSR
In order to investigate GPU-optimized implementations further, We implemented our method for a new sparsity representation format as well. A recent paper proposes the vertical compressed sparse row (VCSR) format [21], a GPU memoryaware format that focuses on achieving both high threadlevel parallelism and high memory bandwidth utilization, while also minimizing compaction overhead. VCSR is designed to leverage the GPU’s coalescing unit, which can reduce global memory transactions significantly. Given that global memory transactions are the main bottleneck in SpMV,
Algorithm 2 FHE_SpMSpM - Performing FHE operations for ciphertext-ciphertext multiplication. 1: 𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ← EvalMult(𝑣𝐴, 𝑣𝐵) 2: 𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ← Relinearize(𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ) 3: 𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ← Rescale(𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ) 4: 𝑚𝑎𝑠𝑘 ← makeMask(𝑠𝑖𝑧𝑒 2 , 𝑚𝑖𝑛_𝑝𝑜𝑠 ) 5: 𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ← EvalMult(𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑, 𝑚𝑎𝑠𝑘 ) 6: 𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ← Relinearize(𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ) 7: 𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ← Rescale(𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ) 8: 𝑟𝑜𝑡 _𝑖𝑑𝑥 ← 𝑚𝑖𝑛_𝑝𝑜𝑠 − ( 𝑗 + (𝑖 · 𝑠𝑖𝑧𝑒 ) ) 9: 𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 ← EvalRotate(𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑, 𝑟𝑜𝑡 _𝑖𝑑𝑥 ) 10: 𝑟𝑒𝑠𝑢𝑙𝑡 ← EvalAdd(𝑟𝑒𝑠𝑢𝑙𝑡, 𝑑𝑜𝑡 _𝑝𝑟𝑜𝑑 )
the proposed methods accelerate kernel execution significantly. VCSR also addresses format conversion overhead, an issue not addressed by earlier sparse matrix studies. Based on the VCSR format, we propose a new combined format by using VCSR on the LHS and VCSC on the RHS.
4
Evaluation
In order to compare our solution with baseline implementations, we tested our methods against the following: (i) Naïve Dense: it represents the baseline for our comparison, where every element in each matrix operand is multiplied individually; (ii) Naïve Sparse: a recent SoTA method [14] that represents a naïve form of sparsity exploitation, where the multiplication is still element-wise, but skips each computation where both values are zero. Our CSR × CSC approach is referred to as CSR/C, and our VCSR implementation as VCSR/C. We ran tests on the four different methods, all implemented in C++ using the HIP-compatible FIDESlib library. The methods were tested on an AMD Radeon RX 7900 XT GPU and an AMD MI300X GPU.1 All methods were tested on the same randomly generated square matrices of sizes 8 and 16 as a proof of concept, with varying sparsity levels (0-100%). The same benchmark tests were run five times to generate an average which captures performance 1 AMD, AMD Radeon, AMD Instinct (MI Series), and combinations thereof
are trademarks of Advanced Micro Devices, Inc.
D’Agata et al.
Table 1. Overall time (in seconds) and speedup comparison of CSR/C and VCSR/C using FIDESlib vs OpenFHE on the AMD Radeon GPU for 16x16 matrices across sparsity levels. Sparsity 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
Open FHE 101.234 85.261 67.349 49.806 37.413 26.497 17.733 9.151 3.806 0.929 0.002
CSR/C FIDES lib 38.266 31.605 25.025 19.190 13.962 9.432 6.637 3.052 1.522 0.348 0.009
Speed up 2.65× 2.70× 2.69× 2.60× 2.68× 2.81× 2.67× 3.00× 2.50× 2.67× 0.23×
Open FHE 118.151 101.569 82.270 61.147 47.057 32.982 21.843 12.145 4.978 1.637 0.002
VCSR/C FIDES Speed lib up 48.743 2.42 × 40.641 2.50× 32.730 2.51× 26.275 2.33× 18.731 2.51× 12.910 2.55× 9.188 2.38× 4.177 2.91× 2.189 2.27× 0.630 2.60× 0.010 0.19×
variances. The overhead costs from converting the matrices into the appropriate format are not included: accounting for external operations such as conversion, encoding, and encryption would not allow an accurate evaluation of the performance of the matmul method itself. Moreover, our methods were also implemented in OpenFHE to include a CPU-based implementation in our results, given the lack of other GPU-based libraries built for the systems tested on. 4.1
Table 2. Frobenius Norm of the CSR/C and VCSR/C methods comparing plaintext matmul with FIDESlib matmul across sparsity levels for matrix sizes 8x8 and 16x16.
Runtime Performance
In Figure 4a, we observe the different methods running on the same GPU operating on the same matrix operands. The naïve dense method has a consistent runtime independent of the sparsity level: this is expected, as the execution is independent of sparsity. The other three methods all display a near-exponential speedup compared to the naïve dense method, and all have consistently better runtimes starting at 10% sparsity. We can observe that the fastest method is CSR/C, which is the only method whose runtime is faster than the naïve dense method even at 0% sparsity. Something to note in Figure 4a is that the naïve sparse, CSR/C, and VCSR/C methods have similar runtimes. GPUs are naturally designed for parallelism, which allows for faster, more efficient, and memory-aware matrix multiplication processes, which could be the reason for this trend. However, it would be expected for GPU-optimized sparsity formats such as VCSR to perform better than other methods when running operations on a GPU. Ciphertexts behave in complex ways, which can greatly affect the runtime and performance of a computation. Moreover, the performance of VCSR/C is highly dependent on both the sparsity pattern and the degree of sparsity [21]. Further investigation is necessary to understand the behavior of the various methods. In Figure 4b we can see the runtimes of the newly proposed methods implemented in OpenFHE, a non-GPU-specific library, compared to the same methods implemented in FIDESlib. We can see that both the CSR/C and VCSR/C methods exhibit constant improvement throughout each sparsity level.
Sparsity 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100%
8x8 (Error e-10) CSR/C VCSR/C 33.54 38.02 28.47 23.43 22.62 22.98 22.41 15.44 14.93 19.01 8.79 10.73 8.73 8.69 3.45 2.94 1.96 1.70 0.34 0.22 0.00 0.00
16x16 (Error e-10) CSR/C VCSR/C 985.58 1758.36 894.49 526.77 945.95 773.00 591.93 528.83 451.01 267.18 187.34 213.56 162.67 159.47 51.24 144.36 22.76 37.75 8.57 9.08 0.00 0.00
Table 1 clearly displays the data, showing a constant speedup ≈ 2.7 × for CSR/C and ≈ 2.5× for VCSR/C when the methods are run using FIDESlib compared to OpenFHE. Figure 4c shows the runtimes of the CSR/C, VCSR/C, and sparse naïve implementations running on the AMD MI300X GPU. This GPU provides very large bandwidth and an even larger on-package memory, reducing stalls from ciphertext and evaluation key movement, further accelerating each method. Its architecture is optimized for sustained HPC workloads with large working sets, and its large unified memory also helps keep evaluation keys resident on-device. 4.2
Accuracy
The accuracy of the results was calculated by comparing the resultant matrix from the CSR/C and VCSR/C methods to a baseline correct solution generated by multiplying the same matrices in plaintext form. The matrices were then compared by calculating the Frobenius norm, which is defined as the square root of the sum of the absolute squares of its elements. The difference between two matrices 𝐴 and 𝐵 can be calculated as follows: ||𝐴 − 𝐵|| 𝐹 =
√︄∑︁
(𝐴𝑖 𝑗 − 𝐵𝑖 𝑗 ) 2
(1)
𝑖,𝑗
As shown in Table 2, both methods produce highly accurate results. Larger approximation errors are observed when multiplications are performed between larger matrices, and overall the accuracy increases with the the sparsity level. At 100% sparsity, both matrices only have zero values, therefore no computations are happening, and the error is zero. 4.3
Time Complexity
The proposed optimized implementation benefits from an extremely efficient lookup time, due to the combination of row-wise and column-wise formats. Given that the algorithm iterates over all pairs of rows and columns, the number of outer iterations is O (𝑁 2 ) for multiplying two 𝑁 ×𝑁 matrices. However, since the algorithm only performs computational work if the indices match, the actual work performed in
GPU Acceleration of Sparse Fully Homomorphic Encrypted DNNs
(a) FIDESlib on Radeon.
(b) OpenFHE vs FIDESlib on Radeon.
(c) FIDESlib on Radeon vs MI300.
Figure 4. Runtime comparison of the different algorithms used to multiply two 16x16 matrices on (a) an AMD Radeon RX 7900 GPU, (b) a comparison with OpenFHE on the AMD Radeon GPU, and (c) runtimes of each method on the AMD Radeon and AMD MI300 GPUs. The matrix sparsity is represented as a fraction, and the runtimes are normalized. the inner loop depends on the number of non-zero values (NZVs) present in each matrix. Let 𝑘𝐴 and 𝑘𝐵 denote the total number of NZVs in matrices 𝐴 and 𝐵, respectively. For each of the 𝑁 row–column index positions iterated in the inner loop, the number of matching operations scales with 𝑘𝑁𝐴 and 𝑘𝐵 𝑁 (the average NZVs per row and column, respectively), giving an overall time complexity of:
5
Conclusion
where 𝑘 = 𝑘𝐴 + 𝑘𝐵 . This expression makes the degenerate cases explicit: in the fully dense case, 𝑘𝐴 = 𝑘𝐵 = 𝑁 2 , so 𝑘 = 2𝑁 2 and the complexity correctly recovers to O (𝑁 3 ), matching the naïve dense algorithm. Conversely, when the matrices are highly sparse and 𝑘 ≪ 𝑁 2 , the complexity is substantially reduced. Therefore, the complexity of the optimization scales linearly with 𝑁 and 𝑘: this represents a large improvement compared to the naïve implementations whenever the matrices are sparse. Compared to SoTA approaches, our implementation is similar, with time complexities rang√ ing from O ( 𝑁 ) to O (𝑁 2 ) [17, 28].
We proposed a new GPU-optimized implementation of encrypted sparse matrix-matrix multiplication in FHE. Our implementation uses a new CSR-based sparsity representation format to reduce the complexity of the procedure, as well as a more advanced version by employing the recently proposed VCSR format. Our proposed matmul implementation was found to run at least 2.4× and up to 3.0× faster when implemented for GPUs. The CSR/C and VCSR/C methods are not just better for sparse matrices: the new algorithm is a generalized and efficient way to multiply packed encrypted matrices, regardless of sparsity. Our experiments are the first to exploit sparsity in a matrix multiplication with FHE-encrypted ciphertexts on GPUs. We show that it is possible to achieve significant speedup even when encrypting a matrix in a GPU-optimized format like VCSR/C. Although there is room for further exploration, the speedup shown in our experiments exposes the potential of running sparse-optimized FHE computations on GPUs. As future work, we aim to demonstrate sparsity utilization with larger matrices and extend the current approach to jointly co-design sparsity-inducing training or compression techniques tailored to FHE constraints.
4.4
Acknowledgments
𝑘𝐴 𝑘 𝐵 O 𝑁 · + 𝑁 𝑁 2
= O (𝑁 · (𝑘𝐴 + 𝑘𝐵 )) = O (𝑁 · 𝑘)
(2)
Discussion
While modern DNNs that use smooth activations (e.g., GELU in Transformer models such as BERT) exhibit little intrinsic activation sparsity, practical sparsity in these workloads typically arises from weight pruning, structured sparsity, or model compression techniques, often reaching 50–90% sparsity in practice for many deployment scenarios and production settings under typical workloads. Moreover, in the FHE setting, polynomial approximations of nonlinearities further reduce activation sparsity, making weight and operand sparsity the primary and realistic source of acceleration. In this work, we therefore focused on exploiting operand sparsity within FHE-based matmul.
This work was supported in part by Advanced Micro Devices, Inc., and the AMD AI & HPC Cluster Program. It was also funded through the grant CNS2023-144241 from MICIU/AEI/10.13039/501100011033 and by the European Union NextGenerationEU/PRTR. Additionally, this research was conducted within the context of the grant RYC2021-031966-I funded by MICIU/AEI/10.13039/501100011033 and by the European Union NextGenerationEU/PRTR.
D’Agata et al.
References [1] Rashmi Agrawal and Ajay Joshi. 2023. On Architecting Fully Homomorphic Encryption-based Computing Systems. Springer Cham. [2] Carlos Agulló-Domingo, Óscar Vera-López, Seyda Guzelhan, Lohit Daksha, Aymane El Jerari, Kaustubh Shivdikar, Rashmi Agrawal, David Kaeli, Ajay Joshi, and José L. Abellán. 2025. FIDESlib: A Fully-Fledged Open-Source FHE Library for Efficient CKKS on GPUs. arXiv:2507.04775 [3] Nir Ailon, Akhiad Bercovich, Yahel Uffenheimer, and Omri Weinstein. 2025. Changing Base Without Losing Pace: A GPU-Efficient Alternative to MatMul in DNNs. arXiv:2503.12211 [4] Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. 2022. OpenFHE: Open-Source Fully Homomorphic Encryption Library. In 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography (WAHC’22). 53–63. [5] Pedro Alves, Jheyne Ortiz, and Diego Aranha. 2023. Performance of hierarchical transforms in homomorphic encryption: a case study on logistic regression inference. J. of Cryptographic Engineering (2023). [6] Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2014. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Trans. Comput. Theory 6, 3, Article 13 (July 2014), 36 pages. [7] Chaochao Chen, Jun Zhou, Li Wang, Xibin Wu, Wenjing Fang, Jin Tan, Lei Wang, Alex X. Liu, Hao Wang, and Cheng Hong. 2021. When Homomorphic Encryption Marries Secret Sharing: Secure Large-Scale Sparse Logistic Regression and Applications in Risk Control. In 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. [8] Xiaofeng Chen, Xinyi Huang, Jin Li, Jianfeng Ma, Wenjing Lou, and Duncan S. Wong. 2015. New Algorithms for Secure Outsourcing of Large-Scale Systems of Linear Equations. IEEE Transactions on Information Forensics and Security 10, 1 (2015), 69–78. [9] Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017. Homomorphic Encryption for Arithmetic of Approximate Numbers. In Advances in Cryptology – ASIACRYPT 2017. 409–437. [10] Moontaha Nishat Chowdhury, André Bauer, and Minxuan Zhou. 2025. Efficient Privacy-Preserving Recommendation on Sparse Data using Fully Homomorphic Encryption. In 2025 IEEE International Conference on eScience (eScience). 1–9. [11] Jinming Cui, Chaochao Chen, Lingjuan Lyu, Carl Yang, and Wang Li. 2021. Exploiting Data Sparsity in Secure Cross-Platform Social Recommendation. In Advances in Neural Information Processing Systems. [12] Junfeng Fan and Frederik Vercauteren. 2012. Somewhat Practical Fully Homomorphic Encryption. Cryptology Archive, 2012/144. [13] Shengyu Fan, Zhiwei Wang, Weizhi Xu, Rui Hou, Dan Meng, and Mingzhe Zhang. 2023. TensorFHE: Achieving Practical Computation on Encrypted Data Using GPGPU. In 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA). 922–934. [14] Aidan Ferguson, Perry Gibson, Lara D’Agata, Parker McLeod, Ferhat Yaman, Amitabh Das, Ian Colbert, and José Cano. 2025. Exploiting Unstructured Sparsity in Fully Homomorphic Encrypted DNNs. In 5th Workshop on Machine Learning and Systems (EuroMLSys ’25). 31–38. [15] Craig Gentry. 2010. Computing arbitrary functions of encrypted data. Commun. ACM 53, 3 (March 2010), 97–105. [16] Perry Gibson, Jose Cano, Elliot Crowley, Amos Storkey, and Michael O’boyle. 2025. DLAS: A Conceptual Model for Across-Stack Deep Learning Acceleration. ACM Trans. Archit. Code Optim. (2025).
[17] Shai Halevi and Victor Shoup. 2015. Bootstrapping for HElib. In Advances in Cryptology – EUROCRYPT 2015. Springer Berlin Heidelberg. [18] Jude Haris, Rappy Saha, Wenhao Hu, and José Cano. 2024. Designing Efficient LLM Accelerators for Edge Devices. arXiv:2408.00462 [19] Ming-Chien Ho, Yu-Te Ku, Yu Xiao, Feng-Hao Liu, Chih-Fan Hsu, Ming-Ching Chang, Shih-Hao Hung, and Wei-Chao Chen. 2025. Invited Paper: Efficient Design of FHEW/TFHE Bootstrapping Implementation with Scalable Parameters. In 43rd IEEE/ACM International Conference on Computer-Aided Design. [20] Hengyuan Hu, Rui Peng, Yu-Wing Tai, and Chi-Keung Tang. 2016. Network Trimming: A Data-Driven Neuron Pruning Approach towards Efficient Deep Architectures. arXiv:1607.03250 [21] Elmira Karimi, Nicolas Bohm Agostini, Shi Dong, and David Kaeli. 2022. VCSR: An Efficient GPU Memory-Aware Sparse Format. IEEE Trans. Parallel Distrib. Syst. 33, 12 (Dec. 2022), 3977–3989. [22] Jongmin Kim, Wonseok Choi, and Jung Ho Ahn. 2024. Cheddar: A swift fully homomorphic encryption library for cuda gpus. arXiv:2407.13055 [23] Francisco Muñoz Martínez, Raveesh Garg, Michael Pellauer, José L. Abellán, Manuel E. Acacio, and Tushar Krishna. 2023. Flexagon: A Multi-dataflow Sparse-Sparse Matrix Multiplication Accelerator for Efficient DNN Processing. In 28th ACM Int. Conference on Architectural Support for Programming Languages and Operating Systems. [24] Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Levskaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. 2022. Efficiently Scaling Transformer Inference. arXiv:2211.05102 [25] T Thammi Reddy, Silpakesav Velagaleti, BVV Satyanarayana, and G Prasanna Kumar. 2025. Hardware efficient arithmetic reconfigurable fully homomorphic encryption (ARFHE) accelerator of low power IoT based RISC-V processor. Analog Integrated Circuits and Signal Processing 124, 1 (2025), 20. [26] Kaustubh Shivdikar, Yuhui Bao, Rashmi Agrawal, Michael Shen, Gilbert Jonatan, Evelio Mora, Alexander Ingare, Neal Livesay, José L. Abellán, John Kim, Ajay Joshi, and David Kaeli. 2023. GME: GPU-based Microarchitectural Extensions to Accelerate Homomorphic Encryption. In 56th Annual IEEE/ACM International Symposium on Microarchitecture. [27] Emmanuel Vintimilla-Tapia, Alexander Rojas, Marco Sigüenza, Andrea Paulina Rodríguez Zúñiga, and Priscila Cedillo. 2026. A Systematic Literature Review on the Security Weaknesses of Fully Homomorphic Encryption Schemes. In Information and Communication Technologies. Springer Nature Switzerland, Cham, 312–328. [28] Qingfeng Wang and Li-Ping Wang. 2025. A Novel Asymmetric BSGS Polynomial Evaluation Algorithm under Homomorphic Encryption. In 20th ACM Asia Conference on Computer and Communications Security. [29] Yannan Nellie Wu, Po-An Tsai, Saurav Muralidharan, Angshuman Parashar, Vivienne Sze, and Joel Emer. 2023. HighLight: Efficient and Flexible DNN Acceleration with Hierarchical Structured Sparsity. In 56th Annual IEEE/ACM International Symposium on Microarchitecture. [30] Weizhi Xu, Yintai Sun, Shengyu Fan, Hui Yu, and Xin Fu. 2023. Accelerating Convolutional Neural Network by Exploiting Sparsity on GPUs. ACM Trans. Archit. Code Optim. 20, 3, Article 36 (July 2023). [31] Keren Zhou, Karthik Ganapathi Subramanian, Po-Hsun Lin, Matthias Fey, Binqian Yin, and Jiajia Li. 2024. FASTEN: Fast GPU-accelerated Segmented Matrix Multiplication for Heterogenous Graph Neural Networks. In 38th ACM International Conference on Supercomputing. [32] Ali Şah Özcan and Erkay Savaş. 2024. HEonGPU: a GPU-based Fully Homomorphic Encryption Library 1.0. Cryptology Archive, 2024/1543.