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

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference contribution › Scientific › vertaisarvioitu

Abstrakti

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.

Alkuperäiskieli	Englanti
Otsikko	2019 IEEE Information Theory Workshop, ITW 2019
Kustantaja	IEEE
Sivut	414-418
ISBN (elektroninen)	9781538669006
DOI - pysyväislinkit	https://doi.org/10.1109/ITW44776.2019.8989092
Tila	Julkaistu - 1 elokuuta 2019
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	IEEE Information Theory Workshop - Visby, Ruotsi Kesto: 25 elokuuta 2019 → 28 elokuuta 2019

Workshop

Workshop	IEEE Information Theory Workshop
Lyhennettä	ITW
Maa	Ruotsi
Kaupunki	Visby
Ajanjakso	25/08/2019 → 28/08/2019

Pääsy asiakirjaan

10.1109/ITW44776.2019.8989092

Link to publication in Scopus

Sormenjälki Sukella tutkimusaiheisiin 'Degree Tables for Secure Distributed Matrix Multiplication'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Projektit

1 Päättynyt

Konstruktion och klassificering av diskreta matematiska strukturer

Kokkala, J., Laaksonen, A., Heinlein, D., Ganzhinov, M., Östergård, P. & Szollosi, F.

01/09/2015 → 24/09/2019

Projekti: Academy of Finland: Other research funding

Siteeraa tätä

Rafael D'Oliveira, G. L., Rouayheb, S. E., Heinlein, D., & Karpuk, D. (2019). Degree Tables for Secure Distributed Matrix Multiplication. teoksessa 2019 IEEE Information Theory Workshop, ITW 2019 (Sivut 414-418). [8989092] IEEE. https://doi.org/10.1109/ITW44776.2019.8989092

@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 -