A Communication-Efficient Distributed Matrix Multiplication Scheme with Privacy, Security, and Resiliency

Abstract

Secure distributed matrix multiplication (SDMM) schemes are crucial for distributed learning algorithms where extensive data computation is distributed across multiple servers. Inspired by the application of repairing Reed–Solomon (RS) codes in distributed storage and secret sharing, we propose SDMM schemes with reduced communication overhead through the use of trace polynomials. Specifically, these schemes are designed to address three critical concerns: (i) ensuring information-theoretic privacy against collusion among servers; (ii) providing security against Byzantine servers; and (iii) offering resiliency against stragglers to mitigate computing delays. To the best of our knowledge, security and resiliency are being considered for the first time within trace polynomial-based approaches. Furthermore, our schemes offer the advantage of reduced sub-packetization and a lower server-count requirement, which diminish the computational complexity and download cost for the user.

Keywords

• secure distributed matrix multiplication
• trace polynomials
• Reed–Solomon codes
• interleaved codes