Secure Sparse Matrix Multiplications and their Applications to Privacy-Preserving Machine Learning

• URL: http://arxiv.org/abs/2510.14894v1
• Date: Thu, 16 Oct 2025 17:12:18 GMT
• Title: Secure Sparse Matrix Multiplications and their Applications to Privacy-Preserving Machine Learning
• Authors: Marc Damie, Florian Hahn, Andreas Peter, Jan Ramon,
• Abstract summary: Multi-party computation (MPC) enables executing Machine Learning (ML) algorithms on secret-shared or encrypted data.<n>MPC frameworks are not optimized for sparse data.<n>We propose MPC algorithms to multiply secret sparse matrices.
• Score: 3.0966075492209715
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: To preserve privacy, multi-party computation (MPC) enables executing Machine Learning (ML) algorithms on secret-shared or encrypted data. However, existing MPC frameworks are not optimized for sparse data. This makes them unsuitable for ML applications involving sparse data, e.g., recommender systems or genomics. Even in plaintext, such applications involve high-dimensional sparse data, that cannot be processed without sparsity-related optimizations due to prohibitively large memory requirements. Since matrix multiplication is central in ML algorithms, we propose MPC algorithms to multiply secret sparse matrices. On the one hand, our algorithms avoid the memory issues of the "dense" data representation of classic secure matrix multiplication algorithms. On the other hand, our algorithms can significantly reduce communication costs (some experiments show a factor 1000) for realistic problem sizes. We validate our algorithms in two ML applications in which existing protocols are impractical. An important question when developing MPC algorithms is what assumptions can be made. In our case, if the number of non-zeros in a row is a sensitive piece of information then a short runtime may reveal that the number of non-zeros is small. Existing approaches make relatively simple assumptions, e.g., that there is a universal upper bound to the number of non-zeros in a row. This often doesn't align with statistical reality, in a lot of sparse datasets the amount of data per instance satisfies a power law. We propose an approach which allows adopting a safe upper bound on the distribution of non-zeros in rows/columns of sparse matrices.

Related papers

• Slicing Is All You Need: Towards A Universal One-Sided Algorithm for Distributed Matrix Multiplication [0.0]
  This paper presents a universal one-sided algorithm for distributed matrix multiplication.<n>Our algorithm supports all combinations of partitionings and replication factors.<n>We implement our algorithm using a high-level C++-based PGAS programming framework.
  arXiv  Detail & Related papers  (2025-10-10T00:11:39Z)
• Fast Plaintext-Ciphertext Matrix Multiplication from Additively Homomorphic Encryption [0.0]
  Plaintext-ciphertext matrix multiplication is an indispensable tool in privacy-preserving computations.<n>We propose an efficient PC-MM from unpacked additively homomorphic encryption schemes.<n>Our proposed approach achieves up to an order of magnitude speedup compared to state-of-the-art for large matrices with relatively small element bit-widths.
  arXiv  Detail & Related papers  (2025-04-20T05:28:46Z)
• Practical Secure Delegated Linear Algebra with Trapdoored Matrices [1.3965477771846408]
  Most heavy computation occurs on servers owned by a second party.<n>This reduces data privacy, resulting in interest in data-oblivious computation.<n>We state the natural efficiency and security desiderata for fast and data-oblivious delegated linear algebra.
  arXiv  Detail & Related papers  (2025-02-18T17:05:17Z)
• Scalable Private Partition Selection via Adaptive Weighting [66.09199304818928]
  In a private set union, users hold subsets of items from an unbounded universe.<n>The goal is to output as many items as possible from the union of the users' sets while maintaining user-level differential privacy.<n>We propose an algorithm for this problem, MaxDegree (MAD), which adaptively reroutes weight from items with weight far above the threshold needed for privacy to items with smaller weight.<n>Our algorithms provide the best results among parallel algorithms and scale to datasets with hundreds of billions of items, up to three orders of magnitude larger than those analyzed by prior algorithms.
  arXiv  Detail & Related papers  (2025-02-13T01:27:11Z)
• Masked Matrix Multiplication for Emergent Sparsity [1.4786952412297807]
  Transformer models exhibit emergent sparsity in which computations perform selective sparse access to dense data. We build a vectorized and parallel matrix-multiplication system A X B = C that eliminates unnecessary computations.
  arXiv  Detail & Related papers  (2024-02-21T20:36:08Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Asymmetric Scalable Cross-modal Hashing [51.309905690367835]
  Cross-modal hashing is a successful method to solve large-scale multimedia retrieval issue. We propose a novel Asymmetric Scalable Cross-Modal Hashing (ASCMH) to address these issues. Our ASCMH outperforms the state-of-the-art cross-modal hashing methods in terms of accuracy and efficiency.
  arXiv  Detail & Related papers  (2022-07-26T04:38:47Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  In this paper, we propose to approximate a large square matrix with a product of sparse full-rank matrices. In the approximation, our method needs only $N(log N)2$ non-zero numbers for an $Ntimes N$ full matrix. We show that our method gives a better approximation when the approximated matrix is sparse and high-rank.
  arXiv  Detail & Related papers  (2021-09-16T18:42:21Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Lossless Compression of Efficient Private Local Randomizers [55.657133416044104]
  Locally Differentially Private (LDP) Reports are commonly used for collection of statistics and machine learning in the federated setting. In many cases the best known LDP algorithms require sending prohibitively large messages from the client device to the server. This has led to significant efforts on reducing the communication cost of LDP algorithms.
  arXiv  Detail & Related papers  (2021-02-24T07:04:30Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. We show that our approach obtains small error and is efficient in both space and time.
  arXiv  Detail & Related papers  (2020-02-23T03:07:31Z)

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.