Degree Tables for Secure Distributed Matrix Multiplication

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

doi:10.1109/ITW44776.2019.8989092

Degree Tables for Secure Distributed Matrix Multiplication

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

Information Theory

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Scientific › peer-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 GASP_r (Gap Additive Secure Polynomial codes) parametrized by an integer r. GASP_r outperforms all previously known polynomial codes for SDMM. We also present lower bounds on N and show that GASP_r achieves the lower bounds in the case of no server collusion.

Original language	English
Title of host publication	2019 IEEE Information Theory Workshop, ITW 2019
Publisher	IEEE
Pages	414-418
ISBN (Electronic)	9781538669006
DOIs	https://doi.org/10.1109/ITW44776.2019.8989092
Publication status	Published - 1 Aug 2019
MoE publication type	A4 Article in a conference publication
Event	IEEE Information Theory Workshop - Visby, Sweden Duration: 25 Aug 2019 → 28 Aug 2019

Workshop

Workshop	IEEE Information Theory Workshop
Abbreviated title	ITW
Country/Territory	Sweden
City	Visby
Period	25/08/2019 → 28/08/2019

Keywords

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

Access to Document

10.1109/ITW44776.2019.8989092

OpenUrl availability

Full text

Cite this

@inproceedings{72561130ca3e4241b990d9e5ebbd435c,

title = "Degree Tables for Secure Distributed Matrix Multiplication",

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.",

keywords = "additive combinatorics, degree table, polynomial codes, Secure distributed matrix multiplication, sumsets.",

author = "{Rafael D'Oliveira}, {G. L.} and Rouayheb, {Salim El} and Daniel Heinlein and David Karpuk",

year = "2019",

month = aug,

day = "1",

doi = "10.1109/ITW44776.2019.8989092",

language = "English",

pages = "414--418",

booktitle = "2019 IEEE Information Theory Workshop, ITW 2019",

publisher = "IEEE",

address = "United States",

note = "IEEE Information Theory Workshop, ITW ; Conference date: 25-08-2019 Through 28-08-2019",

}

TY - GEN

T1 - Degree Tables for Secure Distributed Matrix Multiplication

AU - Rafael D'Oliveira, G. L.

AU - Rouayheb, Salim El

AU - Heinlein, Daniel

AU - Karpuk, David

PY - 2019/8/1

Y1 - 2019/8/1

N2 - 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.

AB - 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.

KW - additive combinatorics

KW - degree table

KW - polynomial codes

KW - Secure distributed matrix multiplication

KW - sumsets.

UR - http://www.scopus.com/inward/record.url?scp=85081057619&partnerID=8YFLogxK

U2 - 10.1109/ITW44776.2019.8989092

DO - 10.1109/ITW44776.2019.8989092

M3 - Conference contribution

SP - 414

EP - 418

BT - 2019 IEEE Information Theory Workshop, ITW 2019

PB - IEEE

T2 - IEEE Information Theory Workshop

Y2 - 25 August 2019 through 28 August 2019

ER -

Degree Tables for Secure Distributed Matrix Multiplication

Abstract

Workshop

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Construction and Classification of Discrete Mathematic Structures

Cite this

Degree Tables for Secure Distributed Matrix Multiplication

Abstract

Workshop

Keywords

Access to Document

OpenUrl availability

Other files and links

Fingerprint

Projects

Construction and Classification of Discrete Mathematic Structures

Cite this