Modular Polynomial Codes for Secure and Robust Distributed Matrix Multiplication

David Karpuk, Razane Tajeddine*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)

Abstract

We present Modular Polynomial (MP) Codes for Secure Distributed Matrix Multiplication (SDMM). The construction is based on the observation that one can decode certain proper subsets of the coefficients of a polynomial with fewer evaluations than is necessary to interpolate the entire polynomial. We also present Generalized Gap Additive Secure Polynomial (GGASP) codes. Both MP and GGASP codes are shown experimentally to perform favorably in terms of recovery threshold when compared to other polynomials codes for SDMM which use the grid partition. Both MP and GGASP codes achieve the recovery threshold of Entangled Polynomial Codes for robustness against stragglers, but MP codes can decode below this recovery threshold depending on the set of worker nodes which fails. The decoding complexity of MP codes is shown to be lower than other approaches in the literature, due to the user not being tasked with interpolating an entire polynomial.

Original languageEnglish
Pages (from-to)4396-4413
Number of pages18
JournalIEEE Transactions on Information Theory
Volume70
Issue number6
DOIs
Publication statusPublished - 1 Jun 2024
MoE publication typeA1 Journal article-refereed

Keywords

  • Data privacy
  • data security
  • distributed computing
  • interpolation
  • polynomials

Fingerprint

Dive into the research topics of 'Modular Polynomial Codes for Secure and Robust Distributed Matrix Multiplication'. Together they form a unique fingerprint.

Cite this