Secure distributed matrix multiplication optimized for fewer workers
Function Tables for Secure Distributed Matrix Multiplication
Information Theory
Summary
This paper studies how to multiply big blocks of numbers safely using many computers without any group of them learning private data. The authors introduce a new way to describe the computations involved that makes it easier to analyze privacy and accuracy. They find exact limits on how many worker computers are needed depending on the number of data blocks and privacy level. The results also show how these limits depend on the math used behind the scenes, like properties of error-correcting codes. This helps design more efficient, secure systems for distributed computing.
What this means in practice
- •For cloud infrastructure teams: Design secure distributed matrix multiplication systems using fewer compute nodes under given privacy constraints.
- •For data center security engineers: Implement privacy-preserving matrix operations while minimizing the number of collaborating servers, due to proven lower bounds.
A theory result. No direct application yet.
Authors
Rafael G. L. D'Oliveira, Giulia Gaggero, Arturo Jaramillo Gil, Hiram H. López, Cecilia Martínez-Reyes, Divyesh Vaghasiya
Abstract
We introduce function tables, an entrywise representation of the coefficient functions that appear in the worker responses of a secure distributed matrix multiplication (SDMM) scheme. We work under the outer-product partition, with $K$ row blocks, $L$ column blocks, and privacy against any $T$ colluding workers, in the general model of linear encoding and linear decoding. In this representation, privacy is a rank condition on the data and mask coefficients, and decodability is linear independence of the desired entries modulo the nuisance space. Degree tables, cyclic-addition tables, and algebraic-geometry constructions are the special cases obtained by restricting the coefficient functions to a structured family; we impose no such restriction, so our converses bind every linear scheme. For $T=1$, we determine the exact optimum over every finite field $\mathbb{F}_q$: it is $KL+K+L$ when $q\geq3$, and $KL+K+L+1$ over $\mathbb{F}_2$, where the identity $z^2=z$ forces one more worker. For arbitrary $T$, we prove $N\geq KL+K+L$ and $N\geq\max\{K,L\}+T$ with no MDS hypothesis on the masks; the first is stronger than the previously known bound $KL+\max\{K,L\}+2T-1$ whenever $\min\{K,L\}\geq2T$. We then reduce field feasibility exactly to MDS existence: a scheme exists over $\mathbb{F}_q$ if and only if an $[\max\{K,L\}+T,T]$ linear MDS code does, and whenever it does, a Cartesian construction attains $N=(K+T)(L+T)$ over that same field. For $T=2$ this makes $q\geq\max\{K,L\}+1$ necessary and sufficient, and we give a projective-line construction with $N=KL+K+L+2$ whenever $KL+K+L$ divides $q-1$; for $K,L\geq2$ it matches the best known worker count while requiring only an element of order $KL+K+L$.