Low-Rank Masking for Single-Server Matrix Multiplication
Researchers prove rank-r additive masks for outsourced matrix multiplication achieve maximal-correlation secrecy of at most q^-r, with a matching lower bound.
An arXiv paper analyzes statistical privacy for outsourcing matrix multiplication over a finite field to a single server using additive masks of rank at most r. Uniform rank-ball masks and products of independent uniform factors yield maximal-correlation secrecy bounded by q^{-r}, with encoding and decoding costing O(n^2 r) field operations. The authors prove an asymptotically matching lower bound for r=o(n), showing these samplers are optimal among input-independent additive masks even with secret invertible transformations. They also show every such mask requires delta approaching 1 in entry-level (epsilon, delta)-differential privacy for fixed field size.
- Uniform rank-ball masks and products of independent uniform factors achieve maximal-correlation secrecy of at most q^-r against complete server views.
- Matching lower bound proves asymptotic optimality among input-independent additive masks of rank at most r for r=o(n).
- Encoding and decoding cost O(n^2 r) field operations for independent uniform inputs.
- Every input-independent rank-r mask requires delta approaching 1 in entry-level (epsilon, delta)-differential privacy at fixed field size.
Full article172 words · extracted from arxiv.org · click to collapse
We study the statistical privacy of outsourcing matrix multiplication over a finite field ${\mathbb F_q}$ to a single server using additive masks of rank at most $r$. For independent uniform $n\times 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 $δ\to1$ in entry-level $(\varepsilon,δ)$-differential privacy for fixed field size $q$ and bounded $\varepsilon$.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2609.18876