Field Trace Polynomial Codes for Secure Distributed Matrix Multiplication

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.