# Sparse and Private Distributed Matrix Multiplication with Straggler Tolerance

arXiv: https://arxiv.org/abs/2306.15134 · HTML: https://mlsanity.com/paper/2306.15134/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2023.

## Built on by (most cited first, 2 of 2)

- [Adaptive Coded Federated Learning: Privacy Preservation and Straggler Mitigation](https://mlsanity.com/paper/2403.14905/) (2024)
- [Secure Sparse Matrix Multiplications and their Applications to Privacy-Preserving Machine Learning](https://mlsanity.com/paper/2510.14894/) (2025)

## Abstract (arXiv)

This paper considers the problem of outsourcing the multiplication of two private and sparse matrices to untrusted workers. Secret sharing schemes can be used to tolerate stragglers and guarantee information-theoretic privacy of the matrices. However, traditional secret sharing schemes destroy all sparsity in the offloaded computational tasks. Since exploiting the sparse nature of matrices was shown to speed up the multiplication process, preserving the sparsity of the input matrices in the computational tasks sent to the workers is desirable. It was recently shown that sparsity can be guaranteed at the expense of a weaker privacy guarantee. Sparse secret sharing schemes with only two output shares were constructed. In this work, we construct sparse secret sharing schemes that generalize Shamir's secret sharing schemes for a fixed threshold t=2 and an arbitrarily large number of shares. We design our schemes to provide the strongest privacy guarantee given a desired sparsity of the shares under some mild assumptions. We show that increasing the number of shares, i.e., increasing straggler tolerance, incurs a degradation of the privacy guarantee. However, this degradation is negligible when the number of shares is comparably small to the cardinality of the input alphabet.