Low-Rank Masking for Single-Server Matrix Multiplication
Abstract
We study the statistical privacy of outsourcing matrix multiplication over a finite field 𝔽q to a single server using additive masks of rank at most r. For independent uniform n× n inputs, we show that uniform \emph{rank-ball masks} and products of independent uniform factors give maximal-correlation secrecy of at most q−r against the complete server view, with O(n2r) field operations for encoding and decoding. This secrecy captures how effectively the server is prevented from estimating functions of the inputs. We prove an asymptotically matching lower bound of this secrecy measure for r=o(n), showing that both sampling methods are asymptotically optimal among input-independent additive masks of rank at most r, even when secret invertible transformations are allowed. We also characterize the posterior distribution for uniform rank-ball masks under arbitrary joint input distributions and prove approximate individual security for rows and columns under independent uniform inputs. Finally, we show that every input-independent additive mask of rank at most r=o(n) requires δ→1 in entry-level (ε,δ)-differential privacy for fixed field size q and bounded ε.
Related
- Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
- The rank of 3x3 matrix multiplication over F2 is 23
- Approximate Matrix Multiplication through Joint Leverage Score Sampling
- Tensor Degenerations for Matrix Multiplication
- Bi-Oriented Interlaced Matrix Multiplication and an Operator Factorisation of the Quantum Harmonic Oscillator
BibTeX
@misc{cohen2026lowrank,
title = {{Low-Rank Masking for Single-Server Matrix Multiplication}},
author = {Alejandro Cohen and Rafael G. L. D'Oliveira and Alex Sprintson},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.18876},
eprint = {2609.18876},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.18876},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Low-Rank Masking for Single-Server Matrix Multiplication
AU - Alejandro Cohen
AU - Rafael G. L. D'Oliveira
AU - Alex Sprintson
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.18876
UR - https://arxiv.org/abs/2609.18876
AB - We study the statistical privacy of outsourcing matrix multiplication over a finite field 𝔽_q to a single server using additive masks of rank at most r. For independent uniform n× n inputs, we show that uniform \emph{rank-ball masks} and products of independent uniform factors give maximal-correlation secrecy of at most q^−r against the complete server view, with O(n^2r) field operations for encoding and decoding. This secrecy captures how effectively the server is prevented from estimating functions of the inputs. We prove an asymptotically matching lower bound of this secrecy measure for r=o(n), showing that both sampling methods are asymptotically optimal among input-independent additive masks of rank at most r, even when secret invertible transformations are allowed. We also characterize the posterior distribution for uniform rank-ball masks under arbitrary joint input distributions and prove approximate individual security for rows and columns under independent uniform inputs. Finally, we show that every input-independent additive mask of rank at most r=o(n) requires δ→1 in entry-level (ε,δ)-differential privacy for fixed field size q and bounded ε.
ER -