Exploiting Unstructured Sparsity in Fully Homomorphic Encrypted DNNs

• URL: http://arxiv.org/abs/2503.09184v2
• Date: Thu, 03 Apr 2025 11:45:18 GMT
• Title: Exploiting Unstructured Sparsity in Fully Homomorphic Encrypted DNNs
• Abstract summary: Deep neural networks (DNNs) in privacy-sensitive environments are constrained by computational overheads in fully homomorphic encryption (FHE)<n>This paper explores unstructured sparsity in FHE matrix multiplication schemes as a means of reducing this burden while maintaining model accuracy requirements.<n>We demonstrate that sparsity can be exploited in arbitrary matrix multiplication, providing runtime benefits compared to a baseline naive algorithm at all sparsity levels.
• Score: 0.37570612254620583
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: The deployment of deep neural networks (DNNs) in privacy-sensitive environments is constrained by computational overheads in fully homomorphic encryption (FHE). This paper explores unstructured sparsity in FHE matrix multiplication schemes as a means of reducing this burden while maintaining model accuracy requirements. We demonstrate that sparsity can be exploited in arbitrary matrix multiplication, providing runtime benefits compared to a baseline naive algorithm at all sparsity levels. This is a notable departure from the plaintext domain, where there is a trade-off between sparsity and the overhead of the sparse multiplication algorithm. In addition, we propose three sparse multiplication schemes in FHE based on common plaintext sparse encodings. We demonstrate the performance gain is scheme-invariant; however, some sparse schemes vastly reduce the memory storage requirements of the encrypted matrix at high sparsity values. Our proposed sparse schemes yield an average performance gain of 2.5x at 50% unstructured sparsity, with our multi-threading scheme providing a 32.5x performance increase over the equivalent single-threaded sparse computation when utilizing 64 cores.

Related papers

• Bridging the Gap Between PHE and FHE: A Performance and Trade-off Analysis of The Somewhat Homomorphic BGN Cryptosystem [0.0]
  Homomorphic encryption (HE) enables privacy-preserving data analytics, but practitioners often face a trade-off between lightweight Partially Homomorphic Encryption (PHE) and computationally dominant Fully Homomorphic Encryption (FHE)<n>The Boneh-Goh-Nissim (BGN) cryptosystem bridges this gap as a Somewhat Homomorphic Encryption (SWHE) scheme supporting unlimited additions and one ciphertext multiplication.<n>This paper presents a comparative analysis of BGN against PHE and FHE paradigms through its integration into the lightphe Python framework.
  arXiv  Detail & Related papers  (2026-07-30T12:33:25Z)
• Constrained Decoding for Diffusion Language Models via Efficient Inference over Finite Automata [57.27430779838529]
  We present an exact and tractable algorithm for sampling from the constrained mean-field posterior under any constraint expressible as a finite automaton.<n>The approach guarantees constraint satisfaction by construction, supports both greedy and sampling-based decoding, and is compatible with parallel and block-wise decoding.<n> Empirical evaluations on Dream-7B and LLaDA-8 show substantial accuracy gains across various tasks.
  arXiv  Detail & Related papers  (2026-07-08T05:48:57Z)
• Scaling Parallel Sequence Models to Foundation-Scale Vision Encoders [123.58723804218151]
  Vision foundation models are bottlenecked by the quadratic cost of self-attention.<n>We present C-GSPN based on 2D spatial propagation propagation.
  arXiv  Detail & Related papers  (2026-05-30T14:29:43Z)
• No More K-means: Single-Stage Sparse Coding for Efficient Multi-Vector Retrieval [51.43543998583709]
  Single-stage Sparse Retrieval (SSR) is a paradigm shift that replaces expensive clustering with efficient sparse coding.<n>It reduces indexing time by 15x compared to ColBERTv2, halves retrieval latency, and simultaneously improves retrieval performance.
  arXiv  Detail & Related papers  (2026-05-28T15:53:34Z)
• Binary-Gaussian: Compact and Progressive Representation for 3D Gaussian Segmentation [83.90109373769614]
  3D Gaussian Splatting (3D-GS) has emerged as an efficient 3D representation and a promising foundation for semantic tasks like segmentation.<n>We propose a coarse-to-fine binary encoding scheme for per-Gaussian category representation, which compresses each feature into a single integer via the binary-to-decimal mapping.<n>We further design a progressive training strategy that decomposes panoptic segmentation into a series of independent sub-tasks, reducing inter-class conflicts and thereby enhancing fine-grained segmentation capability.
  arXiv  Detail & Related papers  (2025-11-30T15:51:30Z)
• Efficient In-Memory Acceleration of Sparse Block Diagonal LLMs [1.5099440840283813]
  Structured sparsity enables deploying large language models (LLMs) on resource-constrained systems.<n>We present a framework with novel mapping and scheduling strategies to accelerate sparse LLM inference on CIM accelerators.<n>Our approach improves CIM utilization by over 50%, achieving more than 4x reduction in both memory footprint and the number of required floating-point operations.
  arXiv  Detail & Related papers  (2025-10-13T09:25:48Z)
• Cost-Effective Optimization and Implementation of the CRT-Paillier Decryption Algorithm for Enhanced Performance [0.0]
  We propose an eCRT-Paillier decryption algorithm that shortens the decryption computation chain.<n>These two improvements reduce 50% modular multiplications and 60% judgment operations in the postprocessing of the CRT-Paillier decryption algorithm.<n>A high- throughput and efficient Paillier accelerator named MESA was implemented on the Xilinx Virtex-7 FPGA for evaluation.
  arXiv  Detail & Related papers  (2025-06-22T08:06:36Z)
• iFlame: Interleaving Full and Linear Attention for Efficient Mesh Generation [49.8026360054331]
  iFlame is a novel transformer-based network architecture for mesh generation. We propose an interleaving autoregressive mesh generation framework that combines the efficiency of linear attention with the expressive power of full attention mechanisms. Our results indicate that the proposed interleaving framework effectively balances computational efficiency and generative performance.
  arXiv  Detail & Related papers  (2025-03-20T19:10:37Z)
• Accelerating spherical K-means clustering for large-scale sparse document data [0.7366405857677226]
  This paper presents an accelerated spherical K-means clustering algorithm for large-scale and high-dimensional sparse document data sets. We experimentally demonstrate that our algorithm efficiently achieves superior speed performance in large-scale documents compared with algorithms using the state-of-the-art techniques.
  arXiv  Detail & Related papers  (2024-11-18T05:50:58Z)
• UNETR++: Delving into Efficient and Accurate 3D Medical Image Segmentation [93.88170217725805]
  We propose a 3D medical image segmentation approach, named UNETR++, that offers both high-quality segmentation masks as well as efficiency in terms of parameters, compute cost, and inference speed. The core of our design is the introduction of a novel efficient paired attention (EPA) block that efficiently learns spatial and channel-wise discriminative features. Our evaluations on five benchmarks, Synapse, BTCV, ACDC, BRaTs, and Decathlon-Lung, reveal the effectiveness of our contributions in terms of both efficiency and accuracy.
  arXiv  Detail & Related papers  (2022-12-08T18:59:57Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  We propose a novel algorithm that uses a random feature approximation (RFA) of the Neural Network Gaussian Process (NNGP) kernel. Our algorithm provides at least a 100-fold speedup over KIP and can run on a single GPU. Our new method, termed an RFA Distillation (RFAD), performs competitively with KIP and other dataset condensation algorithms in accuracy over a range of large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-21T15:56:13Z)
• Efficient Pruning for Machine Learning Under Homomorphic Encryption [2.2817485071636376]
  Privacy-preserving machine learning (PPML) solutions are gaining widespread popularity. Many rely on homomorphic encryption (HE) that offers confidentiality of the model and the data, but at the cost of large latency and memory requirements. We introduce a framework called HE-PEx that comprises new pruning methods, on top of a packing technique called tile tensors, for reducing the latency and memory of PPML inference.
  arXiv  Detail & Related papers  (2022-07-07T15:49:24Z)
• Quantized Neural Networks via {-1, +1} Encoding Decomposition and Acceleration [83.84684675841167]
  We propose a novel encoding scheme using -1, +1 to decompose quantized neural networks (QNNs) into multi-branch binary networks. We validate the effectiveness of our method on large-scale image classification, object detection, and semantic segmentation tasks.
  arXiv  Detail & Related papers  (2021-06-18T03:11:15Z)
• VersaGNN: a Versatile accelerator for Graph neural networks [81.1667080640009]
  We propose textitVersaGNN, an ultra-efficient, systolic-array-based versatile hardware accelerator. textitVersaGNN achieves on average 3712$times$ speedup with 1301.25$times$ energy reduction on CPU, and 35.4$times$ speedup with 17.66$times$ energy reduction on GPU.
  arXiv  Detail & Related papers  (2021-05-04T04:10:48Z)
• Memristive Stochastic Computing for Deep Learning Parameter Optimization [1.6344851071810071]
  Computing (SC) is a computing paradigm that allows for the low-cost and low-power of various arithmetic operations using bit streams and digital logic. We demonstrate that in using a 40-nm Complementary Metal Oxide Semiconductor (CMOS) process our scalable architecture occupies 1.55mm$2$ and consumes approximately 167$mu$W when optimizing parameters of a Convolutional Neural Network (CNN) while it is being trained for a character recognition task, observing no notable reduction in accuracy post-training.
  arXiv  Detail & Related papers  (2021-03-11T07:10:32Z)
• Sparse Systolic Tensor Array for Efficient CNN Hardware Acceleration [14.958793135751149]
  Convolutional neural network (CNN) inference on mobile devices demands efficient hardware acceleration of low-precision (INT8) general matrix multiplication (GEMM) Exploiting data sparsity is a common approach to further accelerate GEMM for CNN inference, and in particular, structural sparsity has the advantages of predictable load balancing and very low index overhead. We address a key architectural challenge with structural sparsity: how to provide support for a range of sparsity levels while maintaining high utilization of the hardware.
  arXiv  Detail & Related papers  (2020-09-04T20:17:42Z)
• EfficientFCN: Holistically-guided Decoding for Semantic Segmentation [49.27021844132522]
  State-of-the-art semantic segmentation algorithms are mostly based on dilated Fully Convolutional Networks (dilatedFCN) We propose the EfficientFCN, whose backbone is a common ImageNet pre-trained network without any dilated convolution. Such a framework achieves comparable or even better performance than state-of-the-art methods with only 1/3 of the computational cost.
  arXiv  Detail & Related papers  (2020-08-24T14:48:23Z)
• PERMDNN: Efficient Compressed DNN Architecture with Permuted Diagonal Matrices [35.90103072918056]
  Deep neural network (DNN) has emerged as the most important and popular artificial intelligent (AI) technique. The growth of model size poses a key energy efficiency challenge for the underlying computing platform. This paper proposes PermDNN, a novel approach to generate and execute hardware-friendly structured sparse DNN models.
  arXiv  Detail & Related papers  (2020-04-23T02:26:40Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.