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 contributionScientificpeer-review

Abstract

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
PublisherIEEE
Pages414-418
ISBN (Electronic)9781538669006
DOIs
Publication statusPublished - 1 Aug 2019
MoE publication typeA4 Article in a conference publication
EventIEEE Information Theory Workshop - Visby, Sweden
Duration: 25 Aug 201928 Aug 2019

Workshop

WorkshopIEEE Information Theory Workshop
Abbreviated titleITW
CountrySweden
CityVisby
Period25/08/201928/08/2019

Keywords

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

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

Cite this