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.