Secure Distributed Matrix Multiplication
Rafael D’Oliveira – Clemson University
Matrix multiplication is, oftentimes, the most expensive computational task in an algorithm. It is the computational bottleneck for training many of the now well-celebrated learning algorithms, for example. To speed up the algorithm, the data can be distributed on many machines to perform the computations in parallel. This sharing of the data, however, raises security concerns when the data is sensitive and has to remain private, such as financial or medical data. Secure distributed matrix multiplication (SDMM) studies how to parallelize matrix multiplication while keeping the data secure.
In this talk, we present a combinatorial tool, called the degree table, and show how to utilize it to construct codes for SDMM which are currently the best performing for their parameters. I will also show lower bounds for this technique and characterize the total time complexity for SDMM codes, showing that if the parameters of the code are not chosen carefully, the total time might be larger than simply performing the computation locally.