Presentation
Sparsee: Unlocking Sparsities in Encrypted Sparse Matrix Multiplication via Hardware-Software Co-Design
DescriptionSparse Matrix Multiplication (SpMM) incurs prohibitive performance overheads in Privacy-Preserving computing based on Fully Homomorphic Encryption (FHE), since the encryption of the sparse matrix hides its inherent sparsity pattern, leading to dense matrix computations. To overcome this, we propose SparseE, a hardware-software co-design framework that enables efficient, sparsity-aware SpMM under FHE. Our novel algorithm recasts SpMM into a secure Scatter-Gather-Apply paradigm, using a homomorphic permutation network to perform the critical data gathering based on encrypted indices. This approach ties the computational cost directly to the number of non-zero elements while protecting the sparsity pattern. To further bridge this performance gap, we co-design a dedicated hardware accelerator. Its Homomorphic Permutation Engine adapts the network to a hardware-friendly Benes topology, enabling a deeply pipelined Radix-k MDC architecture that resolves the on-chip bandwidth bottleneck. Concurrently, its Homomorphic Expansion Engine performs on-the-fly decompression of compressed selector ciphertexts, mitigating the massive storage bottleneck. Experimental results demonstrate that SparseE achieves an average speedup of 401.8× and an average energy reduction of 2594.3× compared to state-of-the-art solutions.
Event Type
Research Manuscript
TimeWednesday, July 294:06pm - 4:18pm PDT
LocationMtg Room 202C
Similar Presentations