Function Tables for Secure Distributed Matrix Multiplication

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\ge 3$, 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\ge KL+K+L$ and $N\ge \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\}\ge 2T$. 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\ge \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\ge 2$ it matches the best known worker count while requiring only an element of order $KL+K+L$.