Coded Distributed (Batch) Matrix Multiplication Over Galois Ring via RMFE

Yi Kuang

doi:10.1109/TIT.2025.3605210

2025-11-01

PRE

DOI：10.1109/TIT.2025.3605210

原文链接

原文求助

摘要

En 中文

Coded Distributed Matrix Multiplication (CDMM) is a distributed matrix multiplication (DMM) for large-scale matrices through a coding scheme such that any R worker nodes among all N worker nodes can recover the final product, where N corresponds to the length of the code and R <= N is called the recovery threshold. The state-of-the-art CDMM schemes, such as EP codes for Single DMM and GCSA codes for batch DMM, are defined over a Galois field GF(q) of size q >= N . These are inefficient for small Galois fields such as GF(2) and the integer residue ring Z(p)(l) due to the lack of invertible elements for interpolation. DMM over Z(p)(l) (such as Z(2)(64) ) is well-motivated in practice due to its direct compatibility with hardware. In this work, we construct an efficient CDMM over the Galois ring GR(p(l),d) which is an extension ring over Z(p)(l) of degree d, particularly, GR(p,d)=GF(p(d)) is the Galois field and GR(p(l),1)=Zp(l). We first give a general CDMM framework for the batch of n matrix multiplications via the famous RMFE (Cascudo et al., Crypto'18). Compared with GCSA, our construction has a smaller recovery threshold by a factor of 1/n . Next, we optimize EP codes via batch preprocessing of the input matrices. We give two types of Single CDMM, which can achieve almost the same performance as EP codes over a Galois field with size q >= N . Finally, we present the experimental analysis of our CDMM on Galois rings.

Keyword:

Codes

Galois fields

Polynomials

Encoding

Costs

Complexity theory

Interpolation

Decoding

Measurement

Vectors

Matrix multiplication