Limits and designs for secure multi-worker matrix multiplication schemes
Function Tables for Secure Distributed Matrix Multiplication
Information Theory
Summary
The paper studies how to safely multiply large matrices using multiple computers without revealing private data, even if some computers cooperate to spy. The authors develop a new way to represent and analyze these schemes called function tables, helping them find exact limits on the number of worker computers needed for different settings. They prove new lower bounds on workers and link the possibility of certain schemes to special error-correcting codes called MDS codes. Their results clarify when these multiplication schemes can work efficiently over different fields and provide constructions that match their theoretical limits.
secure distributed matrix multiplicationfunction tablesprivacylinear encodinglinear decodingouter-product partitionMDS codesfield sizeworker countrank condition
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$.