Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication

Roberto Assis Machado; Rafael G. L. D’Oliveira; Salim El Rouayheb; Daniel Heinlein

doi:10.1109/REDUNDANCY52534.2021.9606447

Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication

Roberto Assis Machado, Rafael G. L. D’Oliveira, Salim El Rouayheb, Daniel Heinlein

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

13 Citations (Scopus)

Abstract

We consider the problem of communication efficient secure distributed matrix multiplication. The previous literature has focused on reducing the number of servers as a proxy for minimizing communication costs. The intuition being that the more servers are used, the higher is the communication cost. We show that this is not the case in general. Our central technique relies on adapting results from the literature on repairing Reed-Solomon codes in which, instead of downloading the whole output of a computing task, a user downloads field traces of it. We present Field Trace Polynomial (FTP) codes, a family of codes, that leverage this technique and characterize regimes for which they outperform existing codes in the literature.

Original language	English
Title of host publication	2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021
Publisher	IEEE
Pages	188-193
Number of pages	6
ISBN (Electronic)	978-1-6654-3308-2
ISBN (Print)	978-1-6654-3309-9
DOIs	https://doi.org/10.1109/REDUNDANCY52534.2021.9606447
Publication status	Published - 29 Oct 2021
MoE publication type	A4 Conference publication
Event	International Symposium Problems of Redundancy in Information and Control Systems - Moscow, Russian Federation Duration: 25 Oct 2021 → 29 Oct 2021 Conference number: 17 https://miem.hse.ru/redundancy2021

Publication series

Name	International Symposium on Problems of Redundancy in Information and Control Systems
ISSN (Electronic)	2694-5215

Conference

Conference	International Symposium Problems of Redundancy in Information and Control Systems
Abbreviated title	REDUNDANCY
Country/Territory	Russian Federation
City	Moscow
Period	25/10/2021 → 29/10/2021
Internet address	https://miem.hse.ru/redundancy2021

Keywords

Reed-Solomon codes
Codes
Costs
Redundancy
Control systems
Servers
Task analysis

Access to Document

10.1109/REDUNDANCY52534.2021.9606447

Cite this

Machado, R. A., D’Oliveira, R. G. L., Rouayheb, S. E., & Heinlein, D. (2021). Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication. In 2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021 (pp. 188-193). Article 9606447 (International Symposium on Problems of Redundancy in Information and Control Systems). IEEE. https://doi.org/10.1109/REDUNDANCY52534.2021.9606447

Machado, Roberto Assis ; D’Oliveira, Rafael G. L. ; Rouayheb, Salim El et al. / Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication. 2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021. IEEE, 2021. pp. 188-193 (International Symposium on Problems of Redundancy in Information and Control Systems).

@inproceedings{24c87342fa4e4d72a8221ef6c3cd0b1d,

title = "Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication",

abstract = "We consider the problem of communication efficient secure distributed matrix multiplication. The previous literature has focused on reducing the number of servers as a proxy for minimizing communication costs. The intuition being that the more servers are used, the higher is the communication cost. We show that this is not the case in general. Our central technique relies on adapting results from the literature on repairing Reed-Solomon codes in which, instead of downloading the whole output of a computing task, a user downloads field traces of it. We present Field Trace Polynomial (FTP) codes, a family of codes, that leverage this technique and characterize regimes for which they outperform existing codes in the literature.",

keywords = "Reed-Solomon codes, Codes, Costs, Redundancy, Control systems, Servers, Task analysis",

author = "Machado, {Roberto Assis} and D{\textquoteright}Oliveira, {Rafael G. L.} and Rouayheb, {Salim El} and Daniel Heinlein",

year = "2021",

month = oct,

day = "29",

doi = "10.1109/REDUNDANCY52534.2021.9606447",

language = "English",

isbn = "978-1-6654-3309-9",

series = "International Symposium on Problems of Redundancy in Information and Control Systems",

publisher = "IEEE",

pages = "188--193",

booktitle = "2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021",

address = "United States",

note = "International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY ; Conference date: 25-10-2021 Through 29-10-2021",

url = "https://miem.hse.ru/redundancy2021",

}

Machado, RA, D’Oliveira, RGL, Rouayheb, SE & Heinlein, D 2021, Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication. in 2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021., 9606447, International Symposium on Problems of Redundancy in Information and Control Systems, IEEE, pp. 188-193, International Symposium Problems of Redundancy in Information and Control Systems, Moscow, Russian Federation, 25/10/2021. https://doi.org/10.1109/REDUNDANCY52534.2021.9606447

Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication. / Machado, Roberto Assis; D’Oliveira, Rafael G. L.; Rouayheb, Salim El et al.
2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021. IEEE, 2021. p. 188-193 9606447 (International Symposium on Problems of Redundancy in Information and Control Systems).

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

TY - GEN

T1 - Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication

AU - Machado, Roberto Assis

AU - D’Oliveira, Rafael G. L.

AU - Rouayheb, Salim El

AU - Heinlein, Daniel

N1 - Conference code: 17

PY - 2021/10/29

Y1 - 2021/10/29

N2 - We consider the problem of communication efficient secure distributed matrix multiplication. The previous literature has focused on reducing the number of servers as a proxy for minimizing communication costs. The intuition being that the more servers are used, the higher is the communication cost. We show that this is not the case in general. Our central technique relies on adapting results from the literature on repairing Reed-Solomon codes in which, instead of downloading the whole output of a computing task, a user downloads field traces of it. We present Field Trace Polynomial (FTP) codes, a family of codes, that leverage this technique and characterize regimes for which they outperform existing codes in the literature.

AB - We consider the problem of communication efficient secure distributed matrix multiplication. The previous literature has focused on reducing the number of servers as a proxy for minimizing communication costs. The intuition being that the more servers are used, the higher is the communication cost. We show that this is not the case in general. Our central technique relies on adapting results from the literature on repairing Reed-Solomon codes in which, instead of downloading the whole output of a computing task, a user downloads field traces of it. We present Field Trace Polynomial (FTP) codes, a family of codes, that leverage this technique and characterize regimes for which they outperform existing codes in the literature.

KW - Reed-Solomon codes

KW - Codes

KW - Costs

KW - Redundancy

KW - Control systems

KW - Servers

KW - Task analysis

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

U2 - 10.1109/REDUNDANCY52534.2021.9606447

DO - 10.1109/REDUNDANCY52534.2021.9606447

M3 - Conference article in proceedings

SN - 978-1-6654-3309-9

T3 - International Symposium on Problems of Redundancy in Information and Control Systems

SP - 188

EP - 193

BT - 2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021

PB - IEEE

T2 - International Symposium Problems of Redundancy in Information and Control Systems

Y2 - 25 October 2021 through 29 October 2021

ER -

Machado RA, D’Oliveira RGL, Rouayheb SE, Heinlein D. Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication. In 2021 17th International Symposium Problems of Redundancy in Information and Control Systems, REDUNDANCY 2021. IEEE. 2021. p. 188-193. 9606447. (International Symposium on Problems of Redundancy in Information and Control Systems). doi: 10.1109/REDUNDANCY52534.2021.9606447

Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

SubspaceCodes: Constructions and Classifications of Subspace Codes and Related Structures for Communication Networks

Cite this

Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Projects

SubspaceCodes: Constructions and Classifications of Subspace Codes and Related Structures for Communication Networks

Cite this