Metraipolis › archive › dc_0ff656f5641d

Improved Degree Tables for Secure Distributed Matrix Multiplication — arXiv:2609.06789

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.06789
License (as archived)
CC0-1.0
Archived
2026-10-16T14:49:18.701Z
SHA-256 of the archived text
39fd073b65ba082f4d7420749107ff682f9b02f9f20b1f723ce07c9addcd91d5
Stable URL of this page
https://metraipolis.com/documento/dc_0ff656f5641d

How to cite

Improved Degree Tables for Secure Distributed Matrix Multiplication — arXiv:2609.06789 — arXiv (en), https://arxiv.org/abs/2609.06789 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0ff656f5641d (Metraipolis archive dc_0ff656f5641d, sha256 39fd073b65ba082f4d7420749107ff682f9b02f9f20b1f723ce07c9addcd91d5)
BibTeX
@misc{dc0ff656f5641d,
  title = {Improved Degree Tables for Secure Distributed Matrix Multiplication — arXiv:2609.06789},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.06789},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0ff656f5641d; sha256 39fd073b65ba082f4d7420749107ff682f9b02f9f20b1f723ce07c9addcd91d5},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.06789. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathsf{GASP}_r$, $\mathsf{GASP}_{r,s}$, and $\mathsf{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, $\mathsf{SHIFT}_{r,s}$ and $\mathsf{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 $\mathsf{SHIFT}_{r,s}$ up to lower-order terms, showing that it is asymptotically optimal among degree-table constructions.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-09 in math.CO).
Categorie arXiv: Information Theory (cs.IT) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.06789 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T14:32:29.921Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).