Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 8 min ago
PreprintarXiv licencearXiv

Improved Degree Tables for Secure Distributed Matrix Multiplication

  • John Byrne
  • Rafael G. L. D'Oliveira
  • Michael Tait
Open at sourcePDFDOICite

Abstract

In secure distributed matrix multiplication, a user wishes to compute the product of two matrices with the assistance of servers, in such a way that any T colluding servers learn nothing about either matrix. Degree tables are a combinatorial tool for constructing polynomial codes for this problem and underlie several state-of-the-art schemes, including GASPr, GASPr,s, and DOGr,s. We introduce a periodic-gap framework for constructing degree tables that contains these three families as special cases and leads to two new constructions, SHIFTr,s and COVERr. We determine their exact recovery thresholds and show that, in many cases, they outperform the current state of the art. We also prove a new lower bound on the recovery threshold of ordinary integer degree tables. In the balanced case, in which the partitioning parameters and the security parameter are equal, we sharpen this bound to match SHIFTr,s up to lower-order terms, showing that it is asymptotically optimal among degree-table constructions.

Related

  1. Function Tables for Secure Distributed Matrix Multiplication
    Rafael G. L. D'Oliveira, Giulia Gaggero, Arturo Jaramillo Gil +3
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. Low-Latency Coded Tensor--Matrix Multiplication for Distributed Signal Processing Systems
    Ahmad Tanha, Ali Khalesi
    arXivPreprintCC BY-NC-ND 4.0Full textNumerical analysis & scientific computingarXiv
  3. An improved minimum degree threshold for fractional clique decompositions in partite graphs
    Sean Longbrake, Michael Simkin, Liana Yepremyan +1
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. A Two-regime Khintchine Inequality and an Improved Bound on the Degree-1 Fourier Weight for Linear Threshold Functions
    Xuan Fang, Tianyu Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  5. Improved Lp maximal estimates for higher-degree Weyl sums
    Xuezhi Chen, Changxing Miao, Jiye Yuan +1
    arXivPreprintarXiv licenceFull textAlgebra & number theoryAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{byrne2026improved,
  title = {{Improved Degree Tables for Secure Distributed Matrix Multiplication}},
  author = {John Byrne and Rafael G. L. D'Oliveira and Michael Tait},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.06789},
  eprint = {2609.06789},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.06789},
}
RIS
TY  - UNPB
TI  - Improved Degree Tables for Secure Distributed Matrix Multiplication
AU  - John Byrne
AU  - Rafael G. L. D'Oliveira
AU  - Michael Tait
PY  - 2026
DA  - 2026/09/06
PB  - arXiv
DO  - 10.48550/arxiv.2609.06789
UR  - https://arxiv.org/abs/2609.06789
AB  - In secure distributed matrix multiplication, a user wishes to compute the product of two matrices with the assistance of servers, in such a way that any T colluding servers learn nothing about either matrix. Degree tables are a combinatorial tool for constructing polynomial codes for this problem and underlie several state-of-the-art schemes, including GASP_r, GASP_r,s, and DOG_r,s. We introduce a periodic-gap framework for constructing degree tables that contains these three families as special cases and leads to two new constructions, SHIFT_r,s and COVER_r. We determine their exact recovery thresholds and show that, in many cases, they outperform the current state of the art. We also prove a new lower bound on the recovery threshold of ordinary integer degree tables. In the balanced case, in which the partitioning parameters and the security parameter are equal, we sharpen this bound to match SHIFT_r,s up to lower-order terms, showing that it is asymptotically optimal among degree-table constructions.
ER  -