Degree Tables for Secure Distributed Matrix Multiplication

G. L. Rafael D'Oliveira, Salim El Rouayheb, Daniel Heinlein, David Karpuk

Research output: Chapter in Book/Report/Conference proceedingConference article in proceedingsScientificpeer-review


We consider the problem of secure distributed matrix multiplication (SDMM) in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. We construct polynomial codes for SDMM by studying a recently introduced combinatorial tool called the degree table. Maximizing the download rate of a polynomial code for SDMM is equivalent to minimizing N, the number of distinct elements in the corresponding degree table. We propose new constructions of degree tables with a low number of distinct elements. These new constructions lead to a general family of polynomial codes for SDMM, which we call GASPr (Gap Additive Secure Polynomial codes) parametrized by an integer r. GASPr outperforms all previously known polynomial codes for SDMM. We also present lower bounds on N and show that GASPr achieves the lower bounds in the case of no server collusion.

Original languageEnglish
Title of host publication2019 IEEE Information Theory Workshop, ITW 2019
ISBN (Electronic)9781538669006
Publication statusPublished - 1 Aug 2019
MoE publication typeA4 Conference publication
EventIEEE Information Theory Workshop - Visby, Sweden
Duration: 25 Aug 201928 Aug 2019


WorkshopIEEE Information Theory Workshop
Abbreviated titleITW


  • additive combinatorics
  • degree table
  • polynomial codes
  • Secure distributed matrix multiplication
  • sumsets.


Dive into the research topics of 'Degree Tables for Secure Distributed Matrix Multiplication'. Together they form a unique fingerprint.

Cite this