Improved Security Distributed Matrix Multiplication via Root of Unity and Grid Partitioning

Distributed matrix multiplication (DMM) has broad applications in data analytics, machine learning, and scientific simulation, but faces critical challenges such as data privacy concerns, server straggling, and Byzantine node failures. To address these issues, this paper proposes three novel secure distributed matrix multiplication (SDMM) schemes. The first scheme utilizes Reed-Solomon (RS) codes and their duals to achieve resilience against stragglers, security against Byzantine servers and information-theoretic privacy against colluding servers. By leveraging the orthogonality of roots of unity, it supports flexible grid partitioning for matrices A and B. To the best of our knowledge, this is the first root-of-unity-based SDMM construction that offers general straggler resilience under grid partitioning and achieves a significantly lower recovery threshold than prior schemes. To further enhance communication efficiency, the second scheme employs subspace polynomials to reduce the per-server download cost by a factor of $\frac{s}{\ell}$ while preserving the same privacy guarantees; subsequently, a lower bound on the download cost for communication efficiency (CE)-SDMM schemes is derived. Finally, inspired by RS codes over cyclic polynomial rings, the third scheme replaces costly finite-field multiplications with simple cyclic shifts and XOR operations over the rings, thereby reducing the computational complexity. Moreover, it can be efficiently implemented using the developed fast Fourier transform (FFT) algorithms, further reducing the overall encoding and decoding complexity.