GASP Codes for Secure Distributed Matrix Multiplication

DOI10.1109/TIT.2020.2975021MaRDI QIDQ5124414zbMATH OpenOpenAlexWikidataFDO

Authors Rafael G. L. D'Oliveira, Salim El Rouayheb, David A. Karpuk

Publication date 29 September 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1812.09962

zbMATH Keywords

GASP (Gap Additive Secure Polynomial) codespolynomial codes for SDMM

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15) Cryptography (94A60)

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 combinatorial problem on a special type of addition table, which we call the degree table. The codes are based on arithmetic progressions, and are thus named GASP (Gap Additive Secure Polynomial) Codes. GASP Codes are shown to outperform all previously known polynomial codes for secure distributed matrix multiplication in terms of download rate.

Cited in

(2)

• Codes from A_m-invariant polynomials
• Near-optimal fault tolerance for efficient batch matrix multiplication via an additive combinatorics lens

This page was built for publication: GASP Codes for Secure Distributed Matrix Multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5124414)