Single server matrix multiplication secured by low rank additive masks
Low-Rank Masking for Single-Server Matrix Multiplication
Information TheoryCryptography and Security
Summary
This paper looks at how to keep matrix multiplication data private when you send it to one server to do the work. The authors study a way of hiding the data using special masks that have low complexity (low rank). They show these masks are very good at preventing the server from learning anything about the original data, while keeping the process efficient. The authors also prove that their masking approach is as good as it can get, mathematically, for certain settings.
What this means in practice
- •For cloud service developers: Design secure outsourced matrix multiplication protocols that minimize information leakage using low-rank additive masks.
- •For data privacy engineers: Evaluate privacy guarantees of additive masking schemes for protecting matrix data processed on untrusted single servers.
A theory result. No direct application yet.
Authors
Alejandro Cohen, Rafael G. L. D'Oliveira, Alex Sprintson
Abstract
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$.