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 𝔽q: it is KL+K+L when q≥3, and KL+K+L+1 over 𝔽2, where the identity z2=z forces one more worker. For arbitrary T, we prove N≥ KL+K+L and N≥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}≥2T. We then reduce field feasibility exactly to MDS existence: a scheme exists over 𝔽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≥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≥2 it matches the best known worker count while requiring only an element of order KL+K+L.
Related
- Improved Degree Tables for Secure Distributed Matrix Multiplication
- Low-Latency Coded Tensor--Matrix Multiplication for Distributed Signal Processing Systems
- Approximate Matrix Multiplication through Joint Leverage Score Sampling
- Unbiased Low-Rank Approximation for Repeated Matrix-Vector Multiplication: Stability and Optimal Sampling
- Tensor Degenerations for Matrix Multiplication
BibTeX
@misc{doliveira2026function,
title = {{Function Tables for Secure Distributed Matrix Multiplication}},
author = {Rafael G. L. D'Oliveira and Giulia Gaggero and Arturo Jaramillo Gil and Hiram H. López and Cecilia Martínez-Reyes and Divyesh Vaghasiya},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.08154},
eprint = {2609.08154},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08154},
}
RIS
TY - UNPB
TI - Function Tables for Secure Distributed Matrix Multiplication
AU - Rafael G. L. D'Oliveira
AU - Giulia Gaggero
AU - Arturo Jaramillo Gil
AU - Hiram H. López
AU - Cecilia Martínez-Reyes
AU - Divyesh Vaghasiya
PY - 2026
DA - 2026/09/08
PB - arXiv
DO - 10.48550/arxiv.2609.08154
UR - https://arxiv.org/abs/2609.08154
AB - 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 𝔽_q: it is KL+K+L when q≥3, and KL+K+L+1 over 𝔽_2, where the identity z^2=z forces one more worker. For arbitrary T, we prove N≥ KL+K+L and N≥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}≥2T. We then reduce field feasibility exactly to MDS existence: a scheme exists over 𝔽_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≥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≥2 it matches the best known worker count while requiring only an element of order KL+K+L.
ER -