Source-linked AI summary
Low-Rank Masking for Single-Server Matrix Multiplication
Alejandro Cohen, Rafael G. L. D'Oliveira, Alex Sprintson
TL;DR
Outsourcing matrix multiplication to a single server raises the question of how much statistical privacy additive low-rank masks can provide. The paper analyzes rank-ball masks and independent uniform factors, showing maximal-correlation secrecy at most q^-r and an asymptotically matching lower bound. It also characterizes rank-ball posteriors, establishes approximate individual security, and identifies a differential-privacy limitation.
Problem
The paper asks how to limit what a single server learns about matrix inputs while outsourcing their product without client encoding and recovery costs approaching local computation.
Source: §1 · p. 1Method
It analyzes uniform rank-ball masks and products of independent uniform factors, including their posterior distributions and privacy guarantees.
Source: §2.2 · p. 2Results
For independent uniform square inputs, both sampling methods achieve maximal-correlation secrecy at most q^-r against the complete server view, with an asymptotically matching lower bound for rank-constrained masks.
Source: §1 · pp. 1–2Takeaways & Limitations
Both methods are asymptotically optimal among input-independent additive masks of rank at most r, even with secret invertible transformations.
Source: §1 · pp. 1–2When r=o(n), the rank constraint prevents input-independent masks from providing useful differential privacy.
Source: §2.3 · p. 2
Abstract
from arXiv · showhide
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 $\delta\to1$ in entry-level $(\varepsilon,\delta)$-differential privacy for fixed field size $q$ and bounded $\varepsilon$.
1. INTRODUCTION
The paper studies statistical privacy for single-server matrix multiplication using low-rank additive masks, seeking to limit server knowledge without making client encoding and recovery as costly as local multiplication. It analyzes two mask-sampling methods and their privacy guarantees, including maximal-correlation secrecy, individual security, and differential privacy.
1. INTRODUCTION
- The single-server setting asks how to protect inputs while outsourcing A · B without client encoding and recovery costs approaching local computation.Related approaches include computationally based cryptographic protocols and multi-server information-theoretic schemes.Source: §1 · p. 1
- Rank-at-most-r masks factor into n×r and r×n matrices, enabling O(n^2r) client encoding and recovery while the server performs one matrix multiplication.The paper studies products of independent uniform factors and masks sampled uniformly from the rank ball.Source: §1 · p. 1
- For fixed q, bounded ε, and r=o(n), every input-independent rank-at-most-r mask requires δ→1 for entry-level (ε, δ)-differential privacy.The limitation follows from the rank bound.Source: §1 · p. 1
- Uniform rank-ball masks preserve the relative probabilities of compatible inputs under arbitrary joint priors, while both methods provide approximate individual security for rows and columns under independent uniform inputs.A rank-ball upload rules out inputs more than rank distance r away; the individual-security result is approximate.Source: §1 · p. 1
- For independent uniform square inputs, both sampling methods achieve maximal-correlation secrecy at most q^-r against the complete server view and are asymptotically optimal among input-independent rank-at-most-r additive masks, even with secret invertible transformations.The lower bound matches asymptotically for fixed q and r=o(n).Source: §1 · pp. 1–2
1.1. Related Work
- Prior work also studies adjustable security, noisy low-rank schemes, numerical stability, and privacy–accuracy tradeoffs; individual secrecy has been studied in network coding, storage, and multi-secret sharing.Unlike the noisy scheme discussed here, this setting recovers the finite-field product exactly and studies uncertainty about the inputs.Source: §1.1 · p. 2
2. MAIN RESULTS
The section presents a single-server protocol using independent additive masks of rank at most r, then characterizes its privacy through posterior distributions, differential privacy, individual security, and maximal correlation.
2.1. Low-Rank Masking
- For n×n inputs, the user's computation is quadratic in n for constant r and o(n^3) when r=o(n).Decoding uses 4n^2r multiplications; encoding uses O(n^2) additions.Source: §2.1 · p. 2
2.2. Privacy within Rank Balls
- With uniform rank-ball masks and any joint input distribution, the posterior is the prior restricted to inputs within rank distance r of each upload, then normalized.The uploads preserve relative probabilities among compatible inputs, but can identify an input if it is the only compatible input with positive prior probability.Source: §2.2 · p. 2
2.3. Limits on Differential Privacy
- For fixed q and r=o(n), every input-independent rank-at-most-r mask requires δ→1 for bounded ε, and no such mask gives pure differential privacy for finite ε.The result applies to every input-independent mask distribution.Source: §2.3 · p. 3
2.4. Approximate Individual Security
- For |T|≤r, both methods provide approximate T-individual security for jointly selected rows or columns; the Factors error decreases exponentially with r−|T| for fixed q.The stated total-variation bounds are q^(|T|−r) for Factors and q^-1 + β_n,r for rank-ball masks.Source: §2.4 · p. 3
2.5. Maximal-Correlation Secrecy
- For independent uniform square inputs, both mask-sampling methods give maximal correlation at most q^-r against the complete server view, with equality for Low-Rank Factors.The server's computed product is determined by the uploads, and the complete-view bound is stated for T = (X, Y, Z).Source: §2.5 · p. 3
- For fixed q and r=o(n), a matching lower bound makes both methods asymptotically optimal among input-independent additive masks, even with secret invertible transformations.For r≤n−2, the methods are within a factor of two of the optimum.Source: §2.5 · pp. 3–4
- For nonuniform or correlated inputs, the guessing-improvement bound depends on joint-input concentration, which is zero for independent uniform inputs.For either method, the improvement for a fixed function is at most 2^Δ/2 q^-r, and half this for a binary function.Source: §2.5 · p. 4
3. PROOFS
The proofs establish the maximal-correlation bound for both mask samplers, derive an asymptotically matching converse, and analyze posterior and individual security. They also prove the cost bound and the entry-level differential-privacy constraint.
Posterior distribution
- Uniform rank-ball masks assign constant likelihood to compatible inputs and zero elsewhere, so Bayes’ rule yields the posterior statements.The sampler chooses rank t with probability Cd,e(t)/Vd,e(r) and constructs a uniform rank-t mask from full-rank factors, padded to width r.Source: §3 · p. 4
Protocol cost
- Computing RS as U((VQ)W) establishes the user-side cost bound, while decoding follows from Z=AB+AS+RB+RS.The proof uses r ≤ min{m,n,p}.Source: §3 · p. 4
Differential privacy
- The differential-privacy proof lower-bounds mask entropy using conditional entry entropy and upper-bounds it by counting factor pairs, yielding the paper’s constraint on δ.The proof also shows that when δ=0, support invariance under every entry translation forces full support, contradicting r<n.Source: §3 · p. 4
Approximate individual security
- For independent uniform inputs, the row-security proof reduces the distance to uniform to the distance of R_T from uniform, bounded by 1−pk,r for full-rank factors.Mixing lower ranks adds at most βn,r; transposition gives the column bound.Source: §3 · p. 4
Maximal-correlation secrecy
- q^-r bounds maximal correlation for both mask samplers; the proof uses additive characters, and the rank-ball bound follows from invariance and a rank-counting argument.For Low-Rank Factors, averaging gives q^-r rank(H); for Low-Rank Ball, the proof bounds the character sum by q^r Cn−1(r) and uses Vn(r) ≥ q^2r Cn−1(r).Source: §3 · p. 4
- For independent inputs and masks, the joint coefficients multiply, yielding the same maximal correlation for (A, B) against the complete server view (X, Y, Z).The proof identifies this with ρm(A; X).Source: §3 · p. 4
Converse
- The converse proof correlates kernel sizes g(A)=q^(n−rank(A)) and g(A+K), deriving a lower bound for masks K with rank at most r.For r ≤ n−2, the proof uses 2q^-n ≤ q^-r/2 as its second bound.Source: §3 · p. 4
5. COMPLIANCE WITH ETHICAL STANDARDS
The work is theoretical and involved no human or animal subjects; no ethical approval was required.
5. COMPLIANCE WITH ETHICAL STANDARDS
- The work is theoretical, involved no human or animal subjects, and required no ethical approval.Source: §5 · p. 5